kthng

boj 1298 : 노트북의 주인을 찾아서boj 2188 : 축사 배정 https://www.acmicpc.net/problem/1298https://www.acmicpc.net/problem/2188 두 문제 모두 이분매칭의 1번문제이다.이분매칭 문제를 모든 경우를 고려할 경우 시간복잡도는 N!로 N이 웬만큼 작지 않으면 해결할 수 없다."네트워크플로우 -> 이분매칭" 으로 이어지는 공부 과정을 거쳐야 풀수 있는 문제이다. 이분매칭 문제는 위와같이 단순한 형태의 네트워크 플로우 모형으로 바뀌고, 동시에 "가장 매칭쌍이 많으면 몇개일까?" 라는 질문은 "source에서 sink로 최대 얼마나 흘려줄 수 있을까?" 라는 질문으로 바뀐다. 이후 포드 퍼커슨 알고리즘을 이용하여 네트워크 플로우의 최대 흐름을 ..

boj 2672 : 여러 직사각형의 전체 면적 구하기 https://www.acmicpc.net/problem/2672 풀었던 문제 중 제일 많이 틀렸습니다!! 인 것 같다.ㅜㅜ... 처음 접근은1. 사각형의 넓이를 다 더한다.2. 두 사각형이 겹치는 넓이를 뺀다. 이렇게였는데, 틀렸다.위와같은 방법으로 접근하려면 1.사각형의 넓이를 다 더한다.2. 두 사각형이 겹치는 넓이를 뺀다.3. 세 사각형이 겹치는 넓이를 더한다.4. 네 사각형이 겹치는 넓이를 뺀다.5. 다섯 사각형이 겹치는 넓이를 더한다..... 이와같이 접근해야하므로 시간복잡도를 감당할 수 없을 것 같아 포기. 생각을 거듭하다보면, 이런 생각을 떠올릴 수 있다. 위와같은 사각형이 주어졌을 때, 위와같이 영역을 모두 쪼갠다.이후 각 영역이 사각..

boj 1701 : editor(cube editor) https://www.acmicpc.net/problem/1701 내가 풀어낸 해법은 간단하다.하지만 좀더 빠르게 풀려면 뭔가가 필요한 것같다.. 접미사 배열에서 중복제거라던가..KMP라던가 ㅜㅜ 일단 내가 풀어낸 방법은1. 접미사 배열을 모두 뽑아낸다.2. 접미사 배열을 정렬한다.3. 인접한 접미사의 최대 매칭 길이를 구한다.4. 그 길이의 최대값을 출력한다. 2번->3번으로 넘어가는게 생각이 약간 필요하다.생각의 흐름은1. 접미사의 공통된 앞부분은 문자열의 공통된 부분문자열이다.2. 접미사는 정렬되어있다.3. i번째, i+1번째 접미사의 최장부분매칭길이를 구하면 공통된 부분문자열의 최대길이이다. 떠올릴 수 있는 간단한 방법이니만큼 어딘가에 개선의..

boj 2841: GITARA(외계인의 기타연주) https://www.acmicpc.net/problem/2841 문제를 이해하기가 힘들지만, 이해만 하면 풀 수 있는 아이디어를 간단히 떠올릴 수 있다. 7개의 stack을 이용하면 된다.stack의 top이 눌러야할 플렛보다 클경우 모두 pop해주고 눌러야할 플렛을 push해주면 해결된다. 7개의 줄은 모두 독립적으로 처리하면 된다. pop한 횟수와 stack에 push한 횟수만큼이 손가락을 움직이는 횟수이다.

boj 2934 : CVJETICI(LRH 식물) https://www.acmicpc.net/problem/2934 펜윅트리를 이용하여 해결할 수있다.울타리 기둥의 좌표가 주어졌을 때 그 울타리를 가로지르는 팬스의 갯수를 구하는 데 펜윅트리를 이용한다. 먼저 펜윅트리는 구간의 합을 빠르게 구하는 데 쓰인다. 이를 응용하면 좌표가 주어졌을 때 '그 좌표를 포함하는 구간들' 의 갯수를 빠르게 구할 수 있다. 울타리의 left, right가 주어질 때 add(left + 1,1), add(right,-1)이렇게 하면 해당구간을 가로지르는 펜스의 갯수를 누적할 수 있다. 이렇게 하면 sum연산으로 누적되어있는 울타리의 수를 알아낼 수 있다.그렇다면 남은건 이미 피어있는 꽃에 대한 처리는 어떻게해줘야하는가? 에대..

boj 1333 : 부재중 전화 https://www.acmicpc.net/problem/1333 간단해보이지만 그래도 꽤 생각해야하는 문제.공식은 간단하다. 1. 1

boj 3055 : SLIKAR(탈출) https://www.acmicpc.net/problem/3055 물이넘치는것과 비버가 이동하는 것 모두 고려해주어야 해서 풀기 조금 난해하다고 생각되지만, 사실은 2개의 큐로 각각을 따로 처리하면 간단하게 해결할 수 있다.첫번째 queue는 마지막으로 물이 이동한 위치를 넣어준다. 이를 이용해서 맵을 갱신해준다.두번째 queue는 마지막 비버가 있을 수 있는 위치를 입력한다. 만약 비버가 동굴을 만나면 그때까지의 count를 출력하면 된다. 이 두번째 queue가 비었다는 것은 비버가 있을 수 있는 곳이 없다는 것이므로 못간다를 출력하면된다. 중요한건 첫번째 큐를 이용하여 물이 이동하는 것을 먼저 해주고, 두번째 큐를 이동하여 비버가 있을 수 있는 위치를 갱신하는..

boj 2725 : Visible Lattice Points https://www.acmicpc.net/problem/2725 (0,1),(1,0)을 제외한다면 (x,y)가 보인다는 것은 gcd(x,y) 가 1이라는 것이다.이를이용하여 for문 2개로 문제를 해결할 수 있다. for (int i = 2; i

boj 1124 : 언더프라임 https://www.acmicpc.net/problem/1124 1이 아닌 소수 약수의 갯수를 구하면된다.에라토스테레스의 체를 응용하여 구할 수 있다.에라토스테레스의 체에서 바꾼건 i가 소수일 때 i가 j를 나눌 수 있으면 나눌 수 있을 만큼 나누고 나눴던 횟수를 a[j]에 누적한다."i가 소수인가?"는 "a[i]가 0인가?"와 동치이다.그러면 a[a[i]]가 0이면 i는 언더프라임이다.

boj 10836 : 여왕벌 https://www.acmicpc.net/problem/10836 시간을 오래 들여 여러 실험을 해본 문제이다.주어지는 n개의 m*2-1배열이 감소하지 않는 것에 문제의 힌트가 있다.따라서 문제는 m*2-1배열을 읽었을 때 0,1,2만큼 자라는 수가 주어지고, 이를 통해 왼쪽모서리와 위쪽모서리의 애벌레들이 최종적으로 얼마나 자랐는지를 구해낼 수 있다.왼쪽,위쪽 모서리의 에벌레들만 자라고 나면 나머지 에벌레들은 각 열의 맨 윗쪽 모서리 애벌레 크기만큼 자란다. 왜냐하면 주어지는 배열이 감소하지않는 배열이기 때문!그렇다면 문제는 모서리 왼쪽위쪽 애벌레가 모두자랐을 때 크기가 얼마나 되느냐?만 풀면 된다. 총 3가지 방법으로 시도해보았다. 1. 애벌레 크기 다 계산하기.총 2m-..