전체 글
-
Programmers Lv3) [2019 카카오블라인드] 길 찾기 게임Algorithm/Programmers 2021. 4. 21. 16:50
출처: programmers.co.kr/learn/courses/30/lessons/42892 분류: Tree 접근방식 주어진 노드 정보를 가지고 이진트리를 구성한 후 전위순회, 후위순회 결과를 반환하면 되는 문제였습니다. 노드 정보는 [Int]로 x, y 값이 주어지는데, 같은 레벨의 노드는 모두 y값이 같고, y값이 클수록 상위 레벨의 노드입니다. 따라서 y값을 기준으로 sort해주고 차례대로 이진트리를 구성해주면 됩니다. 저는 순회할 때 인덱스를 반환해야 하므로, 노드에 index 값을 가지고 있도록 했습니다. x,y 정보도 그냥 배열 그대로 들고있도록 해줬어요. class Tree { var value: [Int] var index: Int var leftChild: Tree? var rightC..
-
백준 11049 행렬 곱셈 순서Algorithm/BOJ 2021. 4. 21. 14:08
출처: www.acmicpc.net/problem/11049 분류: DP 접근방식 전체 순서를 유지하면서 특정 연산을 해야할 때 연산 순서를 어떻게 해야 최소가 될까? 에 관한 문제였습니다. 11066 파일합치기 와 유사한 문제였다는 생각이 드네요. 핵심 아이디어는 X ~ Y까지 연산의 최소값을 DP에 계속 저장해나가는데, X ~ Y까지 연산의 최솟값은 (X~K) + (K~Y) 연산들 중 최소를 찾아나가는 것입니다. 문제의 예시를 가지고 생각해보겠습니다. 각 행렬이 배열에 들어있다고 생각하면, (5x3) - 0 (3x2) - 1 (2x6) - 2 0 ~ 1 까지의 최소값은 dp[0][1], 0 ~ 2 까지의 최소값은 dp[0][2] 에 담는 것입니다. 0 ~ 2 까지의 최솟값은 ( [0][1] 을 먼저 ..
-
팩트풀니스일상/독서 2021. 4. 20. 16:24
2021.04.01 ~ 2021.04.10 그동안 내가 얼마나 왜곡된 시선을 가지고 살아왔는지 알게 해 준 책이었다. 세상을 사실 그대로 받아들이기가 얼마나 어려운지, 얼마나 쉽게 한쪽으로 치우쳐 생각하게 되는지 크게 10가지 본능으로 구분해서 설명해주고 있다. 특히 독감, 바이러스에 대해 주의해야 한다는 내용을 읽으면서는 현재 코로나로 상황과 맞물려 더욱 와닿았다. 이미 몇 년이 지난 책인데도 지금의 현실을 보고 쓴 것처럼 진행형인 내용이 많아서... 아는 만큼 보이는 세상이라는 걸 다시 한번 깨닫는다. 더 열심히 배워야겠다는 생각이 든다! 또 네 단계의 소득수준의 삶을 보면서 정말 닮아있다는 생각이 많이 들었다. 예전 유럽의 가부장적이었던 집안 분위기에 대한 내용을 보면서도 우리나라의 가부장적인 모습..
-
백준 17070 파이프 옮기기 1Algorithm/BOJ 2021. 4. 20. 12:38
출처: www.acmicpc.net/problem/17070 분류: DP, 백트래킹 접근방식 주어진 요구사항 대로 파이프의 이동 가능 위치를 잘 계산하고 나면 백트래킹으로 도착한 경우의 수를 세주면 되는 문제였습니다. 파이프의 끝 점에서 출발한 경로는 역시 다시 방문해줄 필요가 없으므로 방향을 고려한 3차원 배열에 이를 기록해서 방문 횟수를 줄여줬습니다. 조금 귀찮긴 하지만 크게 어렵지는 않아서 풀이를 보시면 이해가 되실거에요 :) 해결방법 let n = Int(readLine()!)! var map = [[Int]]() for _ in 0.. Direction { if pipe.0.r == pipe.1.r, abs(pipe.0.c - pipe.1.c) == 1 { return .horizontal } ..
-
백준 9252 LCS 2Algorithm/BOJ 2021. 4. 20. 11:25
출처: www.acmicpc.net/problem/9252 분류: LCS 접근방식 최장 증가 수열을 찾는 전통적인 LCS 문제입니다. 문자열을 그대로 사용하면 시간초과가 나서 길이 테이블을 완성하고 백트래킹을 통해 문자열을 찾아주는 방식으로 해결했습니다. LCS는 다음과 같이 두 문자열로 이차원 행렬을 완성시켜 나가는 방식으로 찾아줄 수 있습니다. 현재 칸의 두 문자열의 문자가 같다면 왼쪽 대각선 위의 문자열에 현재 문자를 붙여나갑니다. 다르다면 위나 왼쪽 중에서 더 큰 문자열을 가져옵니다. 같다면 모두 가능한 문자열이겠죠? 이 원리를 이용해 저희 예제로 만들어보면 가로 CAPCAK 세로 ACAYKP 로 두면 다음과 같은 LCS 테이블을 만들 수 있습니다. 이제 마지막으로 마지막부터 백트래킹으로 문자열을..
-
백준 2096 내려가기Algorithm/BOJ 2021. 4. 20. 09:54
출처: www.acmicpc.net/problem/2096 분류: DP 접근방식 간단한 DP 문제였습니다. 1, 2, 3 각 열에서 가장 최선인 경우를 계속 선택해나가면 됩니다. 행마다 갱신하고 나면 그 이전은 생각할 필요가 없으므로 디피는 각 열을 저장할 행 하나만 있으면 됩니다 :) 저는 맨 밑에서부터 올라왔는데 위에서부터 내려가도 상관은 없을듯 하네요! 해결방법 let n = Int(readLine()!)! var num = [[Int]]() for _ in 0..
-
백준 1915 가장 큰 정사각형Algorithm/BOJ 2021. 4. 19. 20:26
출처: www.acmicpc.net/problem/1915 분류: DP 접근방식 문제 이름처럼 만들 수 있는 가장 큰 정사각형을 찾는 문제입니다. 정사각형의 성질을 생각해보면 DP와 재귀를 활용해 정사각형의 크기를 쉽게 구해낼 수 있습니다. 정사각형은 다른 정사각형의 모음입니다. 3x3짜리 정사각형을 예로 들어볼까요? 각 칸에 정사각형의 크기를 적어보면 다음과 같습니다. 3 2 1 2 2 1 1 1 1 여기서 하나가 빠져서 아깝게 정사각형이 못되는 경우를 생각해보면 다음과 같습니다. 2 2 1 2 1 1 1 1 0 규칙이 보이시나요? 정사각형은 자신을 둘러싸고 있는 정사각형들의 크기 중 가장 작은 값 + 1 만큼이 자신의 크기입니다. 위 예처럼 하나만 빠져도 정사각형이 될 수 없기 때문이죠! 이 성질을 ..
-
백준 1937 욕심쟁이 판다Algorithm/BOJ 2021. 4. 19. 19:39
출처: www.acmicpc.net/problem/1937 분류: DP, DFS 접근방식 기본적인 DFS 접근 방식에 DP의 개념을 추가해서 풀 수 있는 문제였습니다. 한 점에서 갈 수 있는 최대 거리(판다의 생존 일 수)를 DFS를 통해 구해나가는 데, 어차피 그 점에서 시작한 결과는 어차피 어디서 와서 시작하든 같기 때문에 다시 탐색할 필요가 없다는 점을 이용합니다. 따라서 일 수를 기록하는 Map크기와 같은 DP를 채워나가면 해결할 수 있었습니다. 해결방법 import Foundation typealias Point = (r: Int, c: Int) let n = Int(readLine()!)! var map = [[Int]]() for _ in 0.. Int { guard dpMap[curr.r]..