열심히해보겠씁니다

눈물나는 견우와 직녀의 일화이다. 하필이면 절벽지대에 살아가지고 오작교가 없으면 서로가 만나지 못할 수도 있다. 문제의 조건은 다음과 같다. 1. 한 칸을 이동하는데 1분이 걸린다. 2. 오작교에 적힌 시간의 배수에만 (0포함) 견우가 다리를 건널 수 있다. 3. 절벽이 교차하는 곳에는 오작교를 놓을 수 없다. 4. 오작교는 연속으로 건널 수 없다. 이토록 많은 조건을 뚫고도 견우가 직녀를 만나러 갈 수 있을까? 문제 풀이의 청사진은 다음과 같다. 1. 가장 빨리 도착하는 경우를 구해야하므로 BFS 를 이용하여 경로를 찾아본다. 2. 시간복잡도는 정확하게 계산하기 어렵고, 이럴 일도 없지만 N*N (map의 크기) * N * N (0이 들어갈 경우) * N * N( 완전탐색) = 1백만이므로 여유가 차고..

단어를 정해진 수 K개만 가르쳐주고 N개의 단어를 읽게 하는 잔인한 문제다. N > K; for (int i = 0; i > input; noun.push_back(input); } if (K < 5) { cout

테트리스에서 나오는 블록들을 NxM 종이 위에 올리는데 종이에 적힌 값이 가장 크도록 만들고 싶다. 종이의 크기는 최대 500x500 이므로 25만 정도이므로 N * 400 = 1억이므로 하나의 좌표당 최대 400 개의 연산을 할 수 있다고 보면 될 것 같다. 위 그림에서는 5가지의 형태가 그려져있다. 실제로 종이에 올릴 때는 블록들을 돌리거나 뒤집을 수 있으므로 각 도형에 대해 모두 수행해봐야한다. ㅏㅓㅗㅜ 모양을 제외한 나머지 블록들은 xy 좌표 기준으로 3번의 dfs를 수행하여 고르면 된다. 하지만 ㅏㅓㅗㅜ 는 dfs로 탐색하기 힘드므로 하드하게 코딩하는 방식을 썼다. 구현 방식은 다음과 같다. 1. DFS 방식으로 특정 좌표 x,y 에서 탐색하여 블록을 만들어 그 때의 값을 구한다. 2. 같은 좌..

모래성 문제. 모래성에 파도가 치는데, 모래성이 감당할 수 있는 것보다 큰 파도를 만나면 모래성이 무너진다. 얼마나 많은 시간이 지나야 모래성의 모습이 더이상 변하지 않을까? 우선 특수한 경우가 어떤 것이지부터 파악했다. 1. 가장자리에는 모래성이 없다. 2. 튼튼함이 9인 경우 반드시 무너지지 않는다. 3. 맵의 크기가 백만이므로 완전탐색으로 풀 수 없다. 이 세 가지를 이용해 코드의 방향과 최적화를 잡을 수 있을 것으로 기대한다. 우선 가장 빨리 결과에 도착하는 시간을 찾는 것이기 때문에 BFS 를 생각했다. 맵의 크기가 너무 크기도 해서 DFS 로는 시간 초과가 뜰 것이 분명했기 때문이다. 풀이 방식은 다음과 같다. 1. 초기 상태에서 무너질 수 있는 곳의 좌표를 찾아서 저장한다. 2. 무너질 수 ..

아주아주 간단한 문제다. 보기에는. 하지만 DFS로 풀기에는 좀 까다롭다. 왜냐하면 Floor 가 100만 층이나 되기 때문에 최악의 경우(S 1 G 1,000,000 U 1 같은) 100만번을 쌩으로 돌릴 수도 있기 때문이다. depth 가 너무 깊어지기 때문에 터지기 쉽상이므로 다른 방식을 생각해본다. 가장 먼저 생각한 것은 동적 계획법(Dynamic programming)이다. 프로그램을 돌리면서 과거보다 결과가 좋지 않은 것은 전부 쳐내버리는 방법인데, 가령 길을 찾을 때, 옛날에 지나갔던 길이라면 내가 어떻게 애를 써도 그 시간보다 과거로 가서 길을 지나갈 순 없다. 특히 그곳이 목적지였다면 나는 과거에 도착한 것을 알기 때문에 목적지를 구태여 빙 돌아서 한 번 더 갈 필요는 없다. DP가 딱 ..

NxN 체스판에 N개의 퀸을 두는 문제이다. DFS에서 가장 유명한 문제가 아닐까싶다. DFS가 유용하다는 것을 보이기 위해서 이거만한 문제가 없는 것 같다. 왜냐하면 원래 체스판은 8x8에 불과하기 때문에 손으로도 금방 (92번만하면) 모든 경우를 다 찾을 수 있지만 만약 체스판이 14칸까지 늘어난다면 한참(36만++) 걸릴 것이기 때문이다. 이 문제는 DFS로 접근하되 2가지 최적화를 사용했다. 1. 순수하게 문제 그대로 DFS를 사용하되 퀸을 놔도 되는지 체크하는 함수를 최적화 2. 체스판을 그룹화하여 사용한 그룹을 체크해놓는 look up table 생성 퀸을 놔둔 자리는 Chess[][]에 1로 표시한다. 체스판의 범위는 0부터 N-1 까지로 입력받는다. 1번 방식부터 사용해본다. int che..

연결 리스트를 사용하면 배열을 선언하고 특정 상황에 이용할 때 생기는 문제점들을 해결할 수 있다. 가령 배열의 크기를 넘어가는 입력에 대한 처리 같은 유동적인 할당을 하고 싶을 때 사용하면 좋다. 물론 배열의 크기를 바꾸어 다시 선언하거나 동적 할당을 받았다면 realloc 으로 크기를 늘려도 된다. 하지만 런타임 중 수정하기 어려운 문제가 있고, realloc 의 경우 만드려는 충분한 메모리가 없다면 실패할 수 있고, 복사하는 시간이 추가적으로 들기도 한다. 그렇기 때문에 메모리 상의 남은 공간 아무데나 할당 받아 숫자를 저장하고 주소를 외우는 방식이 편리하기도 하다. 그래서 힙 기반의 링크드 리스트를 살펴본다. Head 는 배열의 가장 앞에 있는 녀석으로 첫 요소의 주소를 가리키는 정보만이 중요하다...

4개의 방향을 확률로 움직이는 미친로봇이다. EWSN 순으로 확률(%)가 입력되고 당연하게도 모든 확률의 합은 1(100%) 이다. 움직인 수 n 이 최대 14까지 늘어나기 때문에 단순히 경우의 수로 계산해보면 4 ^ 14 이므로 탐색에만 약 2억 번의 연산이 필요하다. 하지만 우리가 원하는 것은 경로가 단순하지 않을 확률(혹은 단순할 확률)이므로 중간의 브렌치(분기)들을 자르면서 가면 경우의 수가 확 줄게된다. 예를 들어 E 방향으로 한 칸 갔다가 바로 W 방향을 가는 경우 반드시 단순하지 않은 경로가 되므로 (원점이 아닌) 점에서 갈 수 있는 방향은 3가지로 제한되므로 3^14 로 줄어든다. 이는 기껏해야 백만 단위이므로 충분히 수행할만하다. 그러므로 DFS를 통한 완전탐색으로 문제를 수행한다. DF..

알고리즘에서 정렬은 엄청나게 강력한 도구 중 하나이다.하지만 비슷한 색의 공을 수만개를 한 번에 정렬하려고 하면 어떨까?마치 퍼즐을 안쪽에서부터 맞추는 것처럼 엄청나게 어려울 것이다.이를 위해 우리가 평상시에 어떤 정렬법을 사용하는지, 조금 더 빠른 정렬은 어떤 방식으로 진행되는지 공부한다.log 수준으로 빠르게 작동하는 정렬법은 선형 자료구조를 마치고 다룬다. 1. 버블 정렬 Bubble sort가장 쉽게 떠올릴 수 있고 개념도 직관적이며 이름마저 귀여운 버블 정렬이다.마치 버블이 떠오르듯 차례대로 비교하며 가장 이해하기 쉽다.하지만 O(N^2)의 수행시간을 반드시 가진다. 거품이 올라가듯 차례대로 스왑하는 것이 특징이다.한 번 끝까지 올라갈때마다 최대수가 끝에 정렬되므로, i번 반복할 때 비교횟수는 ..

이 문제는 처음 접근 방식이 중요하다. 결론부터 말하자면 BFS를 이용해 접근하는 것이 가장 효율적인 것으로 생각된다. 하지만 처음 접근할 때는 홈페이지에 있는 예시만 보고 접근했기 때문에 반례들을 생각 못하고 무작정 짰다. 내 가장 큰 습관 중 하나는, 문제를 보고 원리가 파악된다면 그걸 '그대로' 구현하려고 한다는 것이다. 예를 들어서, 줄 가장 뒤에 있는 아이를 맨 앞으로 보냈을 때 최종 순위가 어떻게 되는가? 하는 문제가 있다면 당연히 가장 뒤에 있는 아이를 앞에 아이와 SWAP을 모두 한 후 출력하면 된다고 접근할 것이다. 하지만 조금 더 빠른 동작을 위해서 각 아이들의 순위를 모두 +1하고 가장 뒤의 아이만 1로 만들어도 충분할 것이다. 먼저 생각해볼만한 것은, 1. 이분 그룹은 유일하지 않다..