Leo.K | To become a cooler Developer

한동안 미뤄두었던 최단거리 알고리즘 문제를 풀어보았다. 오랜만에 풀어보다 보니 많은 난항을 겪었는데, 풀이과정과 접근 방법을 정리해보겠다. 시작노드에서 도착노드까지의 최단거리가 구해지는 것은 맞는데, 최단거리를 구성하는 경로의 경우의 수가 반드시 하나일 것이라는 보장이 없다. 바로 전전 단계 문제인 특정한 최단 경로와 아주 비슷한 문제라고 생각할 수 있다. [ 접근 1 ] 이전에 다익스트라 문제를 풀어보았을 때, 특정 정점을 지나서 가는 경로를 구하는 문제를 풀어본 적이 있었다. 단순하게 생각해서 정점 g, h를 연결하는 경로를 반드시 지나가야 할때, 시작노드가 s, 도착노드가 e라고 하면, s -> e인 최단 거리가 s -> g -> h -> e인 경우에 구해지는 최단 거리 또는 s -> h -> g ..

오늘은 색종이 문제에 이어서 두 번째로 분할정복의 문제를 풀이했다. 이번 문제는 쿼드트리를 생각해보는 문제로 트리의 개념이 직접적으로 코드에 구현되지는 않지만, 한 번쯤 생각해볼만한 문제이다. 우리가 평소에 알고 있던 트리는 이진트리로서 한 노드가 가질 수 있는 자식노드가 최대 2개인 트리의 구조이다. 그렇다면 쿼드 트리는 무엇일까? 말 그대로 한 노드가 가질 수 있는 자식 노드가 최대 4개인 트리의 구조이다. 그림상으로 보면 다음과 같다. 그렇다면 이 문제에서 쿼드트리를 어떻게 적용해볼수 있을까? 문제에서 주어지는 조건을 한 번 생각해보자 [ 문제 접근 & 알고리즘 ] 0과 1로만 구성된 흑백영상이 모두 0이면 괄호없이 0, 모두 1이면 괄호없이 1을 출력한다. 이때, 흑백영상을 자르는 기준을 왼쪽위,..

오늘은 누적합 카테고리 중에서 네번째 골드 문제를 풀었다. 이전에 구간합에 대한 개념을 정리하고 동적계획법을 풀면서 모듈러연산의 분배법칙을 익혀두었더니 다른 골드문제에 비해 쉽게 풀렸던 것 같다. [ 문제풀이 & 접근 ] 시간 초과가 나지 않기 위해서는 구간합을 구해야 하는데, 1차원 배열의 경우 dp[k]를 0~k까지의 구간합이라 하고, i

오늘은 백준 단계별로 문제풀기에서 누적합으로 분류된 문제를 풀이하겠다. 이전에 구간합에 대해 정리한 내용이 있어서 쉽게 풀리겠지 하고 생각을 했는데, 아니나 다를까 틀렸다. ㅜㅜ 한 가지 간과한 사실을 인지하고 코드를 수정해서 정답을 맞추었다. 처음에 생각했던 알고리즘 접근 과정과 간과했던 부분, 수정한 부분을 정리하고자 한다. 구간합에 대한 내용을 아직 잘 모른다면 여기를 눌러서 공부하고 오기를 바란다. [ 접근 과정 : 오류 있는 코드] 이 문제의 입력값의 최악의 경우를 보면 어마무시하다. 문자열의 길이는 최대값이 200,000, 최대 문제의 수도 200,000개, 구간의 최대 길이도 200,000이다. 이 문제를 단순히 반복문 만을 이용해서 풀이한다면 볼것도 없이 시간초과가 날것이다. 그렇다면 시간..

오늘은 알고리즘 스터디원들과 문제풀이를 하는 도중 다들 이 문제를 어려워 하길래 정리할 겸 풀어보았다. 필자는 별 다른 문제를 못느끼고 문제를 풀었는데, 아무리 해도 안된다는 스터디원들의 말을 듣고, 다른 풀이를 인터넷에 검색해보았다. 한 가지 다른 점이 있다면 인터넷과 팀원들의 풀이는 입력값에 반대 방향으로 그래프를 그렸고, 필자는 입력값 방향 그대로 그래프를 구성했다. 문제를 보면 그래프가 방향성이 없는 무방향 그래프가 아니라 방향성이 있는 단방향 그래프라는 것은 눈치챘을 것이다. 사실 필자도 구글링을 해보면서 찾아보았지만 시간 초과가 나는 정확한 이유를 모르겠다... 예상가는 바라고 한다면, 1만개의 정점이 10만개의 간선으로 모두 연결이 되어 있는 상태라면, 모든 노드를 탐색해야 하는 이번 문제에..

오늘은 평소에 약했던 부분인 DFS탐색문제를 풀어보았다. 이번에는 단계별로 문제풀기에 분류되어 있지 않지만 학원사람들과 알고리즘 스터디를 하기 위해서 찾은 비교적 쉬운 DFS탐색 문제이다. [ 접근 ] '-' 이 같은 행에 연결되어 있거나 '|'이 같은 열에 연결되어 있는 경우 하나의 나무 판자로 카운트 한다. 맵을 탐색하다가 해당 위치에 있는 나무판자의 모양이 '-'라면 좌우만 탐색, '|'라면 상하만 탐색한다. 모든 위치에서 DFS탐색을 하되 재귀가 끝나는 위치에서 count해준다. 경우의 수가 두 가지 뿐이므로 조건의 편의성을 위해서 -와 |를 true, false로 변환해서 map에 저장했다. 비교적 쉬운 문제이기 때문에 나머지는 소스코드를 보면 쉽게 이해할 수 있을 것이다. [ 소스코드 ] 1 ..

오늘은 백준 단계별로 문제풀기 카테고리 중에서 그래프 순회로 분류되어 있는 문제를 풀어보았다. 최근에 그래프 탐색문제로 너비우선탐색 문제를 많이 풀이해왔는데, 이번 문제는 생각보다 까다로웠다. [ 문제 분석 ] 시작점과 도착점은 벽이 없음이 보장된다. 시작점과 도착점을 포함해서 이동 거리의 최소값(최단거리)를 도출한다. 이때 단 한 번의 벽은 부술 수 있다. 도착점에 도달할 수 있는 경우는 최단거리를, 도달할 수 없으면 -1을 출력한다. [ 오답노트 ] 처음에는 그렇게나 골치를 썩이던 벽을 뚫을 수 있다는 말에 반가웠지만 막상 구현에 앞서보니 어떤 벽을 뚫어야 최단거리가 가능할까? 라는 생각을 하다가, 이렇게 생각하기엔 경우의 수가 너무 많아서 도달달 수 있는지 없는지를 판단하기로 했다. 위를 구현하기 ..

오늘은 백준 단계별로 문제 풀기의 동적 계획법 1 카테고리에 있는 기본 DP문제를 풀어보았다. https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP문제는 크게 Top-down방식과 bottom-up방식으로 구현을 하는데, 전자는 재귀로, 후자는 반복문으로 구현을 한다. 기본적으로 재귀는 깊이가 깊어질수록 스택 오버플로우가 발생할 위험이 있기 때문에 반복을 사용하여 바틈 업 방식으로 구현을 하는 것이 효율적이라고 한다. 재귀..