백준 일지 (3.13~3.19)

3/13

이분 매칭으로 룩 / 나이트의 움직임의 최대 매칭을 계산할 수 있는데, 시도해보자!

• 그래프
  • 이분 매칭
    • https://boj.kr/1017 소수 쌍 (P3)
      • 소수 쌍 이분매칭으로 구하기.. 미리 한개 고정해놓고 하는 느낌? 얘는 구현 하면 그냥 바로 되네
    • https://boj.kr/9525 룩 배치하기 (P3)
      • 룩의 움직임은 결국 가로먹기 + 세로먹기의 이분 매칭이다.. 미친 풀이.. 진짜 개똑똑하다 사람들. 구현을 어떻게 할지가 고민되긴 하네..
      • 깔끔하게 쪼개려고하면 조금 신경쓸게 있었지만, 그냥 앞끝 / 뒤끝만 신경면서 가로로 순회한번, 세로로 순회한번 돌면 처리되는 영역이었다.
      • 근데 그거조차 귀찮아서 그냥 다음줄 넘어갈때 / X 만날때 번호 1씩 계속 늘려줘서, 최대 MX는 5000에서 10000으로 두배쯤 커졌지만, 시간에는 문제 없이 돌아가네.
      • 다행히 가로줄과 세로줄이 겹치는 경우가 없어서, 있는지 없는지 판별이라든지 안해주고 그냥 매칭만 해버려도 됐다. 그 뒤는 일반 이분탐색과 동일. 아이디어 떠올리는거는 진짜 어려울듯.
  • 탐색
    • https://boj.kr/1525 퍼즐 (G2)
      • 처음 봤을때 상당히 당황했다. 대충 최대 25~30번은 움직일거같은데, 대충 3^25번의 경우의수?!?! 이러면서.. 슬라이딩퍼즐이 막 A*알고리즘 써가면서 어렵게 증명된다는 사실을 알았던게 독이 된듯.
      • 근데 생각해보니까, 3*3 퍼즐이면 결국 경우의수는 9! = 36만개정도밖에 없다! 이정도면 넣을만 하지. 저장은 어떻게하지? 편하게하겠다고 순열, 비트마스킹 쓰다보면 배보다 배꼽이 더 커지는듯.
      • 그러면? 그냥 해시맵 박아버리자! 그러면 그냥 BFS돌리면 된다. C++에서 해시맵을 돌리는게 익숙하지 않아서 조금 걸렸지만. 구현은 할만했고 한번에 돌아갔다. C++는 string에서도 swap이 된다는걸 배웠다. 파이썬은 string이 불변이라 그런거 안되는데.

3/14

• 그래프
  • https://boj.kr/9576 책 나눠주기 (G2)
    • 그리디도 될거같긴한데 숫자 크기도 그렇고 보자마자 이분매칭 생각나니까 이분매칭 때리기
    • 말곤 별거없다
  • https://boj.kr/1867 돌멩이 제거 (P3)
    • 돌 하나는 가로달리기 or 세로달리기로 제거될 수 있다.
    • 결국 N*N의 격자판에서 가로달리기 N개와 세로달리기 N개가 연결된 간선이 있고, 이 간선은 돌멩이 하나를 의미한다.
    • 최소한의 정점(달리기)를 선택해서 모든 간선(돌멩이)를 제거해야한다
    • -> 최소 버텍스 커버!
    • 쾨닉의 정리에 의해, 이분 그래프에서의 경우 이는 최대 매칭의 개수와 같음이 알려져있다.
    • 따라서 이분매칭만 잘 만들고 식세우면 끝
• 세그트리
  • https://boj.kr/22876 츠바메가에시 (P4)
    • 예전에 신촌지역 알고리즘 캠프 랜덤디펜스때 나왔던 문제,. 이제 다시 풀어봤다
    • 구현량이 꽤나 많지만 일단 핵심은 최댓값 2개 가지고있는 세그 만들기
    • 거의 처음으로 C++로 세그트리 구현한거같다! 잘 돼서 기쁘다. pair<int, int>로 하면 그냥 편하게 할수있구나. 파이썬이었으면 차원추가된다고 메모리 엄청먹었겟지..
    • 사람들 풀이를 보니 multiset?을 쓰네. 이걸 쓰면 훨씬 쉽다고? 감이 안오네.. 공부해봐야겠다.

3/15

• 그래프
  • 이분 매칭
    • https:/boj.kr/2570 비숍2 (P2)
      • 예전에 다른 백트래킹? 비숍문제 풀고 덤볐다가 털렸던문제
      • 이분매칭 쓰니까 훨씬 빠르고 더 쉽네..
      • 신기하게도 대각선으로 순회하는걸 어렵지 않게 해냈다. 괜히 범위 맞추는거보다 약간 삐져나가면 걔네 막는게 더 쉬운듯

3/16

• 그래프
  • https://boj.kr/10473 인간 대포 (G2)
    • 플로이드 워셜로 그냥 보이길래 풀었다.. 2차원 기하도 실수하다니 크억 기하싫어

3/17

• 그래프
  • 최대 유량
    • https://boj.kr/5651 완전 중요한 간선 (P1)
      • 이제 이분매칭도 좀 익숙해졌으니 최대유량 공부하자.
      • 디닉 알고리즘을 새로 공부했는데, 이게 에드몬트카프나 포드풀커슨보다 직관적인것같다! 앞으로 이걸로 써먹어야지.
      • 용량을 줄이고도 문제가 없으려면, u->v의 레벨그래프가 있어야되니까!
    • https://boj.kr/1420 학교 가지마! (P2)
      • 벽으로 바꾼다.. 못가게 막는다.. 최소컷이네?
      • 유량 그래프에서의 최대 유량은 가중치 그래프에서의 최소 컷과 같다.
      • 최대유량 최소 컷 정리
      • 근데 여기선 정점을 막는거니까.. 같은 정점->정점의 유량을 1로 잡고 그래프를 만들자.
      • 와 근데 단순하게 점이 10000개니까.. 분할해서 때리니 20000*20000배열.. 안되네.. 이생각을 못했네..
      • BFS느낌으로 인접리스트처럼 접근하자!
      • 이부분이 약간 막막해서 아이디어를 얻으려고 찾아봤는데, https://justicehui.github.io/ps/2019/09/10/BOJ1420/ 에서 디닉 알고리즘 기반으로 {a, b} map으로 처리해버리는 방법이?!?!?
      • unordered_map은 pair<int, int>를 인수로 가지지 못한다! 이래서 map으로 하는거였구나.
      • 이런 상황에서 역간선 추가가 상당히 헷갈린다. 역간선 추가하는거 자체를 함수로 만들어서 관리하는게 실수할 확률이 현저히 적어지는듯. 이렇게 map으로 푸는 경우에는 그렇게 하는게 좋겠다.
    • https://boj.kr/1014 컨닝 (P4), https://boj.kr/11014 컨닝 2(P2)
      • 컨닝 관계들을 생각해보면, 바로 이분그래프임이 눈에 보인다
      • 컨닝하는 관계를 간선, 사람(좌석)을 정점이라고 생각하면, 최소한으로 정점을 없애서 간선 다 없애기! -> 최소 버텍스 커버
      • 쾨닉의 정리에 의해, 이분 그래프에서 최소 버텍스 커버의 개수는 최대 매칭과 같다.
      • 따라서 전체 좌석 수에서 매칭의 수를 빼면 정답. 깔끔하다

3/18

• 그래프 이론
  • 2-sat
    • https://boj.kr/3648 아이돌 (P3)
      • 2-sat 문제다. 심사위원 말 둘중 하나만 만족하면 되니까..
      • 근데 1번이 무조건 합격해야하므로 (1 or 1)을 말하는 심사위원이 한명 있다고 하자.
      • 그러면 그래프에 (not 1 -> 1 )간선을 하나 추가한 상태로 SCC를 만들어서, 모순이 있나 확인하면 된다.

3/19

• 기하학
  • 볼록 껍질
    • https://boj.kr/3679 단순 다각형 (P4)
      • 그냥 대충 생각해봤을때.. 못그리는 경우는 없을거같았다
      • 대충 반시계로 돌면서 안에서 바깥쪽으로 슥슥 그려주다가 어느 시점 이후부터는 바깥에서 안쪽으로 슥슥 그려주면 되겠는데? 라고 판단하고 이 기준을 x의 양수여부로 했는데.. 틀리드라..
      • 생각해보니 맨 마지막줄까지는 그냥 그리고 마지막줄만 뒤집어주면 됨
      • CCW로 그것만 검사하면 된다. 반바퀴 돌리는건 심지어 구현하기 헷갈려서 아크탄젠트썼음. 아이고 편하다
    • https://boj.kr/1708 볼록 껍질 (P5)
      • 예전에 파이썬으로 풀었는데, 이젠 C++로 짜는 연습도 해야되니까.
      • jinhan814님의 볼록껍질 코드를 참고했다. y, x 값으로 정렬해서 맨아래 맨왼쪽 찾는 함수 하나, 반시계로 정렬하는 함수 하나 잡고 훑으면서 CCW의 결과값이 음수일때 (반시계 방향일때)만 남기면서 스택에 쌓는다.
      • 이건 외울 자신은 없고... CCW가 잘 안외워진다 ㅠ 팀노트 파듯이 하나 만들어서 FFT CVH 이런거 넣어놔야겠다.
    • https://boj.kr/4225 쓰레기 슈트 (P3)
      • 조금 관찰하다보니 볼록껍질에서 어떤 직선 기준으로 가장 멀리 떨어진 점을 찾고, 각 선분에 대해 이걸 하고 최솟값을 구하면 되는게 바로 보였다!
      • 구현이 좀 막막했지만, 그냥 각 선분마다 다 돌리고, 반복문 세팅하기 헷갈려서 그냥 나머지 써가면서 비볐다. 이게 되네
      • 생각보다 편하게 구현한듯.

이로써 Class 6까지 완료했다!