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 우선 이 문제에서 "자신의 키가 몇 번째인지 정확히 알 수 있는 사람"은 자신을 제외한 나머지 사람들이 자신보다 키가 큰지, 작은지를 모두 아는 사람입니다. 만..
Algorithm
[백준(Python/Java)] 14890_경사로
https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제를 해석을 잘못해서 엄청나게 복잡한 코드를 생각했었는데요. 처음에 이 문제를 봤을 때는 "가로로 설치한 경사로와 세로로 설치한 경사로가 겹치면 어떻게 하지?"에 대한 처리를 엄청 고민했습니다. 하지만 이 문제는 가로와 세로에 설치한 경사로를 따로 구분해서 푸는 문제이기 때문에 위와 같은 상황은 고려하지 않아도 되는 것이었죠. 따라서 이 문제는 매우 간단해집니다. 주어진 이차원 배열의 모든 행과 열을 탐색해보면서 해당..
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의 문자열과 비교해봐야 하기 때문에..
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가 되는지 여부만 판별해주면 되기 때문에 정렬을 이용할 수 있다고 ..
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..
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],..
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..
Algorithm
[백준(Python/Java)] 4386_별자리 만들기 - 최소 신장 트리
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소 신장 트리(Minimum Spanning Tree)를 이용하는 기본적인 문제로 저는 우선순위 큐를 이용해 해결했습니다. MST는 모든 정점을 연결하는 최소 비용의 간선들의 집합을 구해야 하므로, 임의의 정점 하나를 잡고 시작합니다. 이 임의의 정점도 반드시 언젠가는 포함되어야 하기 때문이죠. 그리고 해당 정점에서 연결된 간선들 중에서 최소 비용인 간선을 뽑고, 해당 간선과 이어진 정점이 방문하..
Algorithm
[백준(Python/Java)] 1987_알파벳 - DFS
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 깊이 우선 탐색(DFS)을 통해 가장 긴 알파벳을 찾는 문제였습니다. 기존에 풀었던 많은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)를 문제에서는 방문한 곳을 true로 체크하여 재방문을 하지 않도록 알고리즘을 설계했습니다. 하지만 이 문제에서는 깊이 우선 탐색을 하여 방문한 곳들이 최적해가 되지 않을 때, 다시 그 곳들의 방문 여부를 false로 복원하여 다음 탐색에서 방문할 수 ..
Algorithm
[백준(Python/Java)] 2234_성곽(DFS, 비트마스킹)
https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 약간의 비트마스킹을 사용해서 푸는 문제인데, 비트마스킹이 중심인 문제는 아니라고 생각합니다. 단순히 각 방에 위치하는 벽의 정보를 이진수로 바꾸고 남동북서 방향으로 바꿔서 읽어주면 되는 것이죠. 예를 들어, 어떤 방의 벽에 대한 값이 11이라면 11을 2진수로 바꾼 뒤 남동북서 방향으로 네 자릿수를 채우면 0111이 됩니다. 즉, 남쪽에 대한 값만 0로 이동가능하고, 동북서에 대한 값은 1로..
