Leo.K | To become a cooler Developer

오늘은 저번시간에 이어서 분할정복 문제를 풀었다. 분할을 2개로 하는 것이 아닌 3개로 하는 것이기 때문에 조금 까다로울 수 있지만, 이전에 분할정복을 사용한 별찍기 문제를 한 번 풀어보았더니 이 문제는 비교적 쉽게 접근하여 풀 수 있었다. 이 문제를 풀이해보셨다면 아래의 문제도 풀어보시면 좋을 것 같다. basecase만 바꿔주면 된다. https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net [ 문제 풀이 ] 종이에 적힌 ..

오늘은 우선순위큐에 대한 기본적인 문제를 풀어보았다. 혹시라도 우선순위큐를 처음 들어본 사람은 아래의 링크로 들어가서 정리된 내용을 한 번 공부하고 오길 바란다. https://cm-me0410.tistory.com/79 우선순위큐(Priority Queue) 오늘은 다익스트라 문제를 본격적으로 풀어보기 전에 먼저 그래프 문제에서 자주 사용하는 우선순위 큐라는 자료구조에 대해 정리를 해보겠다. 결국에 큐이기 때문에 add, poll, peek 등의 연산을 cm-me0410.tistory.com 오늘도 마찬가지로 한 문제을 풀이하려 했지만, 카테고리에 분류된 처음 두 문제가 너무 비슷하고 기본적인 문제이기 때문에 두 문제를 모두 풀이하도록 하겠다. 문제에 대한 링크를 아래에 걸어두도록 하겠다. 우선순위큐 ..

오늘은 BFS문제를 풀이해보았다. 요즘 시간에 뒤쫓기며 계속 더 어려운 알고리즘, 아직 모르는 개념을 공부하는데만 몰두했었다. 오랜만에 탐색문제를 풀었는데, 생각보다 잘 풀리지 않았다. 그래서 위로만 올라가려고 하지 않고, 기본부터 단단히 잡으면서 가려고 한다. [ 문제 접근 ] 바이러스가 퍼지기 전에 3개의 벽을 세워서 바이러스가 퍼지지 않도록 반드시 막아야 한다. 바이러스를 차단한 경우 남아있는 안전지대의 영역 수를 최대로 만들어야 한다. 벽을 세우는 경우의 수는 어떻게 할 수 있을까? 바이러스가 퍼지는 과정은 어떻게 포함할까? 문제를 풀기전에 혼자 생각을 해보았을 때, 벽을 세우는 경우의 수를 구하면 이 중에서 바이러스를 막을 수 없는, 즉 안전지대가 0인 경우의 수가 존재할 수도 있을 것이다. 그..

한동안 미뤄두었던 최단거리 알고리즘 문제를 풀어보았다. 오랜만에 풀어보다 보니 많은 난항을 겪었는데, 풀이과정과 접근 방법을 정리해보겠다. 시작노드에서 도착노드까지의 최단거리가 구해지는 것은 맞는데, 최단거리를 구성하는 경로의 경우의 수가 반드시 하나일 것이라는 보장이 없다. 바로 전전 단계 문제인 특정한 최단 경로와 아주 비슷한 문제라고 생각할 수 있다. [ 접근 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에 분류되어 있는 다이나믹 프로그래밍 문제를 풀이해보겠다. 같은 카테고리에 존재하는 계단오르기 문제와 아주 비슷한 문제이다. 그 문제를 풀때는 점화식을 어떻게 구해야 할지 몰라서 다른 사이트를 참고했는데 참고한 사이트 주소는 아래의 링크를 걸어두겠다. https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 연속해서 세개의 와인을 먹으면 안되기 때문에 연속해서 선택하는 수가 2를 초과하면 안된다. 시작하기에 앞서 ..

오늘은 백준 카테고리 중에서 그래프 순회에 있는 탐색 문제를 풀어보았다. 이번 문제는 BFS로 해결해보고자 한다. 너비 우선 탐색은 자료구조로 큐를 이용하며 인접한 노드를 모두 방문한 후에 자식 노드로 넘어가는 특징이 있다. 기본적인 너비 우선 탐색의 의사 코드는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 map -> 탐색 대상이 존재하는 전체 맵 visit -> 중복 방문 방지용 방문배열(boolean) BFS(R){ -> R은 출발 노드 혹은 출발 지점 Queue -> 방문할 노드를 저장할 큐를 생성. Enqueue하는 순간이 실제 방문이 아니라, 방문 해야할 노드의 리스트를 FIFO구조에 저장하는 것이다. visit[R] = ..

오늘은 백준 단계별로 문제 풀기의 동적 계획법 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방식으로 구현을 하는데, 전자는 재귀로, 후자는 반복문으로 구현을 한다. 기본적으로 재귀는 깊이가 깊어질수록 스택 오버플로우가 발생할 위험이 있기 때문에 반복을 사용하여 바틈 업 방식으로 구현을 하는 것이 효율적이라고 한다. 재귀..