의식이 흐르는대로 해보는 프로그래밍

접근 치즈가 녹아내리는 문제다. 치즈 안쪽으로는 냉기가 있어서, 바깥쪽부터 녹는다는 아주 현실적인 문제. 중요한 포인트는 두가지다. 치즈 바깥쪽의 공기를 인식하는 것. 외부 공기와 접촉한 치즈만을 판단하는 것. 이 두가지만을 주의하고 문제를 해결하면 쉽게 해결이 가능하다. 해결 치즈 바깥쪽의 공기만을 인식하는 건 어떻게 하면될까? 치즈 내부의 공기를 생각해보자. 치즈 내부의 공기는 치즈로 둘러싸여있을 것이다. 그렇다면, 치즈인 곳은 탐색을 진행할 때 어떤 탐색(dfs, bfs)이든, 넣어주지 않게되면, 치즈 안쪽으로는 절대 탐색이 불가능하게 될 것이다. 그걸 이용해서 치즈 외부공기를 먼저 인식해주자. 그렇게 외부공기를 인식한다음, 그냥 이중 반복문으로 해결해도 되고, 또 효율적인 탐색법을 이용해도 좋으니..

접근 문제 자체는 복잡해보이지 않았다. 지나온 알파벳은 다시 들리지 않는다. 이게 이 문제의 중점이었던 것 같은데, 나는 백트래킹 최적화에 애를 먹어서 몇가지 기억하려고 남기려한다. 해결 사실 백트래킹 방법이 아니라, 충분히 BFS로 풀 수 있어보이지만 그냥 앞서서 N과M 문제 풀다보니, 백트래킹으로 해결하려고 시간을 썼다. 근데... 자꾸만 시간 초과가 나서 몇가지 최적화를 진행했다. 일단 백트래킹에 대해서 잠깐 서술해보자면, 영어 그대로 Back Tracking이다. 백트래킹은 재귀적으로 접근하는 알고리즘이다. 모든 경우를 고려하며, 재귀적으로 탐색을 진행하다가 특정 조건에 맞지않는 경우를 제외하고, 다시 탐색을 진행하는 것이다. DFS를 재귀로 구현할 때를 생각하면 형태가 거의 비슷하여 알고리즘의 ..

접근 대표적인 0-1 BFS 문제. 또는 다익스트라로 해결할 수 있다. 0-1 BFS 문제 노드간의 간선이 0 또는 1인 그래프를 탐색하기 위해 사용하는 BFS 문제. 일반적인 BFS문제와 큰 차이점은 없지만, 간선의 가중치가 0이 존재하기 때문에, 일반 BFS로 풀면 최단거리가 보장이 되지 않을 수 있는 문제가 발생. 위와 같은 0-1 BFS의 예시로 느낌이 올 수도 있겠지만, 최단거리를 보장하기 위해서 BFS를 살짝 변형한 것이다. 해결 우리가 사용하는 일반적인 BFS를 의사 코드로 작성해보겠다. Queue = [시작 노드] distance = [inf, inf, inf, ..., inf] # 거리를 무한대로 초기화 해두면, 방문 체크를 위한 리스트 대신 사용 가능 distnace[시작 노드] = 0..

접근 문제 그대로 평범한 배낭 문제다. D.P.를 이용한 Knasack알고리즘을 사용해서 해결할 수 있다. (여담이지만, 올리고 있는 글순서를 보면 알겠지만 솔브닥 클래스 클리어중인데, 이 문제 2년전쯤 그리디 공부할 때 시도했다가 틀리고 안풀고있었던걸 이제 알았다.) (여담2이지만, 이번에 풀 때도 1초틀이었는데, 2년전에 시도했던 코드랑 구조가 똑같았다. 난 발전이 없는것인가...? 하지만 이번엔 해결했다. 내가 틀린 반례도 적어두겠다.) 해결 Knapsack 알고리즘을 사용하지 않고, 전체 탐색으로 해결 자체는 가능하다. 당연히 시간초과가 나겠지만. 그러니까 배낭문제는 그냥 배낭으로 풀자.. 변수는 아래와 같다. $ N $ : 물건의 갯수 $ K $ : 버틸 수 있는 최대 무게 dp Table은 $..

구간 합에 대해서 처음이라면, 이 문제를 봤을 때 아이디어가 바로 안떠오를 수 있다. 그렇다면, 아래 문제로 1차원단위의 구간 합을 먼저 이해해보고오자. https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 접근 구간 합 문제는 일반적으로, 누적 합을 저장해두고 구해야되는 구간의 값들을 빼서 구하는 방식으로 해결한다. 해당 문제도 똑같이 해결하면 되지만 2차원임으로 중복되는 부분을 조심해서 해결해야한다. 구해야하는 케이스에 대..

접근 피보나치 수를 구하는 문제이다. 하지만 범위가 괴랄한.. $ n