CS/Algorithm
[BOJ] 백준 1914 하노이탑 - Python/Java
https://www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 해설 이 문제가 실버2인 이유는 아마 대중적으로 알려진 문제라서 그렇지 않을까 생각합니다. 혼자서 풀려고 했을 때는 정말 모르겠어서 다른 사람들의 풀이를 참고해서 이해할 수밖에 없었습니다...☹️ 하노이탑 문제의 핵심 아이디어는 원반 N개 문제를 해결하기 위해서는 원반이 N-1개인 문제를 해결하면 된다는 것인데요. 구체적으로 풀어서 이야기해보면 아래와 같습니다. 1) N개의 원반이 주어지면 위에서부..
CS/Algorithm
[백준(Python/Java)] 6497_전력난
6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 이 문제는 도시의 모든 집을 연결할 수 있는 최소한의 간선(길)만을 선택하는 문제로, 최소 스패닝 트리(Minimum Spanning Tree, MST)를 이용해 풀 수 있습니다. MST를 구현하는 방법에는 우선순위 큐를 이용하는 방법, 크루스칼 알고리즘을 이용하는 방법과 프림 알고리즘을 이용하는 방법이 있는데요. 이 문제에서는 MST에 보편적으로 쓰이는 크루스칼 알고리즘을 이용해 해결했습니다. 개별 간선(Edge)은 해당 길의 비용과 이어진 두 마을(정점)의 정보를 가지..
CS/Algorithm
[백준(Python/Java)] 2458_키 순서
https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net * 프로그래머스에 있는 [순위] 문제와 완전히 동일한 문제인데요. 해당 문제의 링크는 아래에 있습니다. 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 우선 이 문제에서 "자신의 키가 몇 번째인지 정확히 알 수 있는 사람"은 자신을 제외한 나머지 사람들이 자신보다 키가 큰지, 작은지를 모두 아는 사람입니다. 만..
CS/Algorithm
[백준(Python/Java)] 14890_경사로
https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제를 해석을 잘못해서 엄청나게 복잡한 코드를 생각했었는데요. 처음에 이 문제를 봤을 때는 "가로로 설치한 경사로와 세로로 설치한 경사로가 겹치면 어떻게 하지?"에 대한 처리를 엄청 고민했습니다. 하지만 이 문제는 가로와 세로에 설치한 경사로를 따로 구분해서 푸는 문제이기 때문에 위와 같은 상황은 고려하지 않아도 되는 것이었죠. 따라서 이 문제는 매우 간단해집니다. 주어진 이차원 배열의 모든 행과 열을 탐색해보면서 해당..
CS/Algorithm
[백준(Python/Java)] 9251_LCS
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통 부분수열 문제는 DP를 이용해 풀 수 있는 대표적인 문제입니다. 이 문제를 DP를 이용하지 않고 완전탐색으로 풀었을 때에는 모든 각 수열의 모든 가능한 부분수열을 전부 하나씩 구해서 비교해봐야 합니다. 그러면 문자열 s1의 모든 가능한 부분수열을 구할 때 2^(s1의 길이) 만큼의 시간이 소요되고, 이를 s2의 문자열과 비교해봐야 하기 때문에..
CS/Algorithm
[백준(Python/Java)] 5052_전화번호 목록
https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 이 문제를 푸는 방법은 크게 두 가지가 있습니다. 첫번째는 Trie 자료구조를 이용해서 문자열 탐색을 하는 방법이고, 두번째는 제가 푼 방법처럼 정렬을 이용해 탐색을 하는 방법입니다. 조금 더 일반적인 풀이 방법은 Trie 자료구조를 이용하는 것이겠지만 이 문제는 하나의 전화번호가 다른 전화번호의 Prefix가 되는지 여부만 판별해주면 되기 때문에 정렬을 이용할 수 있다고 ..
CS/Algorithm
[백준(Python/Java)] 2143_두 배열의 합
https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 이 문제에서 구하고자 하는 내용은 아래와 같습니다. 한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A..
CS/Algorithm
[백준(자바/Java)] 6087_레이저 통신(BFS, 우선순위 큐)
https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS와 우선순위 큐를 사용하여 풀 수 있는 문제입니다. 카카오 2020 인턴십 "경주로 건설"과 비슷한 느낌의 문제라고 생각해서, 혹시 풀어보시지 않은 분이 계시면 풀어보면 좋을 것 같습니다. 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],..
CS/Algorithm
[백준(Python/Java)] 11725_트리의 부모찾기(DFS, BFS)
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리의 연결 정보가 주어졌을 때, 각 노드의 부모 노드가 몇 번 노드인지를 묻는 문제입니다. 문제 조건에서 루트 노드가 항상 1번이라는 조건이 있으므로 1번 노드부터 DFS나 BFS 탐색을 시작합니다. 현재 노드를 A라고 하고 그 다음에 탐색을 할 노드를 B라고 한다면, B노드의 부모는 A가 되므로 한 번의 DFS 혹은 BFS 수행으로 모든 노드의 부모 노드를 정할 수 있습니다. 저 같은 경우에는 BFS를 이용해서 문제를 해결했습니다. [풀이 - 파이썬] fr..
CS/Algorithm
[백준(Python/Java)] 4386_별자리 만들기 - 최소 신장 트리
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소 신장 트리(Minimum Spanning Tree)를 이용하는 기본적인 문제로 저는 우선순위 큐를 이용해 해결했습니다. MST는 모든 정점을 연결하는 최소 비용의 간선들의 집합을 구해야 하므로, 임의의 정점 하나를 잡고 시작합니다. 이 임의의 정점도 반드시 언젠가는 포함되어야 하기 때문이죠. 그리고 해당 정점에서 연결된 간선들 중에서 최소 비용인 간선을 뽑고, 해당 간선과 이어진 정점이 방문하..
