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

목차 접근 `n`개의 정점을 가는 이진 트리의 정점에서 1 ~ n까지 중복 없이 번호가 매겨져 있다. 이런 이진 트리에서 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더(전위순회)를 구하는 문제다. 정말 많이 틀리고, 시간이 들었다. 여러 개선점에 대해서 생각해보는 시간이었다. 먼저 기본적인 접근에 대해서 생각해보자. 중위순회는 이진트리를 Left - Mid - Right 순으로 탐색을 진행한다. 후위순회는 이진트리를 Left - Right - Mid 순으로 탐색을 진행한다. 그럼 맨 처음 주어진 각각의 순회의 결과에서 후위순회의 마지막 결과값이 처음 트리의 Mid의 값이라는 것을 알 수 있다. 그럼 아래와 같으 과정을 거치면, 트리를 재귀적으로 분해해나갈 수 있다. 위에서 구한 Mid..

목차 접근 D.P.로 해결하는 간단한 문제. 근데 생각지도 못한 완전탐색을 진행하면서.. 너무 당연한 형태의 D.P.문제여서 그냥 풀면되겠지 했는데, 생각보다 점화식이 떠오르지 않았다. 왼발과 오른발에 대한 얘기가 있어서 어떻게 접근하지 하면서, 질문게시판 제목들을 보면서 대충 풀이를 유추했는데 시간복잡도에 관한 질문들이 많이 보였다. 그럼 혹시...? 하면서 전체탐색을 진행하며 D.P.를 수행하여 해결했다. 해결 이번에 밟아야할 발판에 대해서, (왼발, 오른발) 모든 조합에 대한 경우의 수를 탐색하며 D.P.를 수행했다. 이렇게 전체 탐색에 대한 의심을 한 이유는 입력의 길이가 100,000개 까지 들어올 수 있다는 것, (왼발, 오른발)의 조합이 5 x 5 = 25가 나옴으로 최대 시간복잡도는 `O(..

목차 접근 스도쿠를 풀어내는 문제다. 스도쿠 문제는 N과M 문제와 더불어서 백트래킹으로 푸는 가장 대표적인 예제 중 하나이다. DFS를 수행하면서, 특정 조건을 만족하는지 체크하고 DFS가 끝나면, 다시 원래 상태로 되돌려놓는 알고리즘이다. 이렇게 DFS 알고리즘 시작단에 끝나는 조건을 명시해주면, 특정 조건이 맞는 케이스일 때까지 전체적으로 탐색을 진행할 것이다. 해결 백트래킹으로 해결하자. 0인 위치를 먼저 기록해두고, 0인 위치를 하나씩 채워나가는 방식으로 구현을 진행하자. 또한 스도쿠의 정답이 여러개가 나올 수 있음으로 종료단에, return이 아닌 exit를 이용해서 한번만 출력하고 프로그램을 종료시켜줘야한다. 안그럼 출력 초과가 뜬다.. 코드 sdoku = [] zero_idx = [] for..

목차 접근 이름에서부터 풍겨오는 위상정렬의 냄새. 그냥 아주 간단한 위상정렬 문제이다. 위상정렬에 관한 내용은 이전 문제를 참고해보자. 2023.12.20 - [알고리즘(Algorithm)] - [BOJ] 1005번 : ACM Craft(위상 정렬, dp) [BOJ] 1005번 : ACM Craft(위상 정렬, dp) 접근 순차적인 접근으로, 우선시 되는 건물의 건설 시간 중 가장 긴 시간을 갖도록 목표 건물의 건설 시간을 구하는 문제. 느낌적으로 봤을 땐, DP, 그래프 탐색 이론등을 통해 해결할 수 있을 것 one-way-people.tistory.com 간단하게 설명하자면, 위상정렬은 BFS 탐색과는 거의 비슷하지만, "진입차수"라는 차별적인 요소를 이용해서 순서에 맞춰서 그래프 탐색을 진행하는 알..

목차 접근 2차원 평면상에 존재하는 `N`개의 선분들의 교차를 체크하고, 만약 교차하거나 만난다면 하나의 선분 그룹으로 속한다고 정의하고, 그룹의 수와 가장 큰 그룹에 속한 선분의 갯수를 찾는 문제. 선분의 교차를 체크하는 방법론은 예전에 선분 교차 문제를 풀어봤던 기억이 있어서 CCW(Counter Clock Wise)알고리즘을 이용해서 접근했다. CCW 알고리즘은 외적을 이용해서 선분의 교차를 판정하는 방법론이다. 외적에 대한 설명은 [BallPen님의 블로그]: 외적 - 벡터끼리 곱하여 벡터가 되는 계산법 이 블로그에 아주 자세히 나와있다. 나는 참고해서 설명하겠다. 외적 아래는 외적의 식이다. $ \vec{A} \times \vec{B} = ABsin\theta \hat{n}$ $ \hat{n} ..

접근 부 배열은 수열의 연속된 부분에 대한 합이다. 다른 두개의 수열 각각의 부 배열에 대한 합이 특정한 값과 같은 조합의 갯수를 세는 문제다. 두 수열에 대해 가능한 부 배열의 합을 모두 구하고, 투포인터를 이용해 각각의 합에 대해서 특정한 값과 맞는지 갯수를 세는 방식으로 문제를 해결했다. 해결 부 배열의 합을 구하기 위해서, 구간합을 먼저 구한 뒤 이중반복문으로 존재하는 모든 부 배열의 합을 구했다. 나는 부 배열의 합을 dict형식으로 저장해, '부 배열의 합'을 Key로, '갯수'를 Value로 사용하여 한번에 처리하도록 구성했다. 그리고 한 부 배열 조합은 부 배열의 합의 종류에 대해서 오름차순으로, 다른 부 배열 조합은 내림차순으로 정렬한 뒤에 투포인터를 이용해 각자의 인덱스로 접근하여 합의..

접근 으아아아아아!!! 진짜 오래 걸렸다. 접근 자체는 너무 유명한 문제라 간단하게 했는데 최적화하는 과정에서 2일은 잡아먹었다. 외판원을 잡아다가 그냥 알아서 좀 가라고 너무 말하고싶었다... 결론은 DFS로 갈 경로를 정하고, BitMask로 지금까지 방문했던 도시를 저장한다. 또한 DP를 이용해서 해당 도시 방문의 최소비용을 저장하여, 효율성을 높인다. 앞서 해결했던, 2023.12.31 - [알고리즘(Algorithm)] - [BOJ] 1562번 : 계단 수(DP, BitMask) 문제에서 설명했듯이, BitMask 방법론은 너무 큰 N에 대해선 공간 효율면에서는 맞지않을 수 있다고 말했다. 하지만 이 문제는 N이 16정도로 별로 크지 않기 때문에 BitMask를 사용해볼 수 있다. BitMask..

접근 이름에서부터 뿜어져 나오는 위상정렬의 향기. 위상정렬에 대한 해설은 이전 게시글을 참고하자. 2023.12.20 - [알고리즘(Algorithm)] - [BOJ] 1005번 : ACM Craft(위상 정렬, dp) 문제 풀이의 우선순위 조건이 몇가지가 있다. 문제 번호가 더 큰 문제가 어려운 문제 먼저 푸는 것이 좋은 문제가 있다면, 그 문제부터 해결해야함 쉬운 문제부터 풀기 문제풀이의 우선순위(선수과목)이 있다면, 웬만하면 위상정렬일거라 생각해서 위상정렬로 방향을 잡았다. 해결 위상정렬로 기본적인 알고리즘을 구현하되, "쉬운 문제부터 풀기" 이 조건을 해결하기 위해 우선순위 큐를 사용했다.(나는 Heap큐를 사용했다) 코드가 간단하니 해설은 길게하지 않겠다. 위의 위상정렬해설과 아래 코드를 같이 ..

접근 연결된 그래프를 분할하고,그 가중치 합의 최솟값을 구해내는 문제다. 보자마자 당연히 먼저 든 생각은 다익스트라를 떠올렸지만, 그럼 마을을 분할하는 과정을 접근하기 쉽지않다. 그 다음에 든 생각은 저번에 풀었던 2023.12.21 - [알고리즘(Algorithm)] - [BOJ] 1197번 : 최소 스패닝 트리(Kruskal) 이 문제의 알고리즘인 크루스칼 알고리즘이 떠올랐다. 최소 스패닝 트리는 모든 노드를 연결하는 엣지들의 최소 가중치를 찾는 문제다. 그럼 모든 노드를 연결짓는 최소 가중치를 찾고, 나머지 하나 가장 큰 가중치의 엣지를 제거하면 되겠네? 라는 흐름으로 이어졌다. 해결 위에 언급했던대로, 크루스칼 알고리즘을 사용하여 쉽게 해결했다. 근데 처음 과정은 가장 큰 가중치 하나를 찾고, M..

접근 비트마스크를 이용한 동적프로그래밍으로 해결하는 문제. 비트마스크.. 정말 하기싫었는데, 이게 동적 프로그래밍이랑 엮어서 나온다고? 최고의 조합이다. 그래도 모르면 안되는 개념이니, 비트마스크에 대한 기본적인 내용을 한번 정리해보고 가야겠다. 비트마스크(BitMask) 말그대로 비트를 마스크로 다루는 것이다. 예를 들어 우리가 어떤 인덱스의 방문을 다루기 위해선 일반적으로 배열을 사용한다. `visited = [False, False, True, False, True]` 이런식으로 방문여부를 저장하는 배열을 생성한 뒤 조작한다. 예시를 든 배열의 경우엔 2, 4번 인덱스가 방문을 했다는 것을 알 수 있다. 방문여부의 경우는 어떻게 보면 마스크 개념과 동일하다. 2, 4번 인덱스는 방문했으니까, 못 쓰..