백준

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 사용한 알고리즘 : DFS 풀이전략 1. 이중 ArrayList를 사용하여 각 노드가 가지고 있는 자식 노드의 번호를 저장한다. 2. 각 노드들의 부모 노드 번호를 저장하는 배열을 만든다. 3. 제거한 노드의 부모노드에 대응되는 ArrayList에서 제거한 노드의 번호를 삭제한다. 4. DFS를 통해 트리를 탐색하고, 방문한 노드 중 자식 노드가 없는 경우 count를 1씩 더한다. 제..

https://www.acmicpc.net/problem/21758 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 풀이 사용한 알고리즘 : 누적합(Prefix Sum) 풀이전략 1. 입력한 값들의 누적합을 새로운 배열에 저장한다. 2. 문제에서 구하는 최대의 꿀양이 나올 수 있는 경우는 아래의 세가지 중 하나의 경우이다. 1) 벌 벌 꿀통 좌측의 벌은 항상 배열의 최좌측에 위치, 꿀통은 배열의 최우측에 위치한다. 중간의 벌을 이동시키며 가질 수 있는 최대 꿀양을 알아낸다. 2) 꿀통 벌 벌 꿀통은 항상 배열의 최좌측에 위치, 우측의 벌은 배열의 최우측에 위치한다. 중간의 벌을 이동시키며 가질 수 있는 최대 꿀양을 알아낸다. 3) 벌 꿀통 벌 좌측의 ..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 사용한 알고리즘 : DP, LCS(Longest Common Subsequence) 풀이전략 1. 주어진 두 문자열 길이에 맞게 이차원 배열을 선언한다. int d[][] = new d[두번째문자열.length()+1][첫번째문자열.length()+1] 2. 문자열에서 동일한 문자가 있을 경우 D[i+1][j+1]=D[i][j]+1 문자열에서 동일..

https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 사용한 알고리즘 : 스택 풀이전략 1. 탑의 높이 입력이 들어올 때마다 입력 값이 stack의 top에 저장된 값보다 크면, 기존 stack에서 top 원소가 더 큰게 있을 때까지 pop하고 입력 값이 stack의 top에 저장된 값보다 작으면, stack의 top 인덱스를 resut에 저장하고 기존 stack의 원소들을 유지한다. 2. stack에 현재 입력값을 push 하고 1번 과정을..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 사용한 알고리즘 : DFS 풀이전략 싸이클이 발생하는 노드들을 모아 오름차순으로 출력해주면 되는 문제다. 1. DFS를 통해 각 노드마다 싸이클이 발생하는지 판단한다. - DFS 탐색 중, 탐색의 첫 번째 노드와 동일한 노드로 탐색을 하게 되면 싸이클이다. 2. 싸이클이 발생하면 탐색과정의 모든 노드 번호들을 TreeSet에 삽입한다. 3. 첫번째 노드부터 마지막 노드까지 2번 ..

https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 사용한 알고리즘 : 투 포인터 풀이전략 1. 문자열의 시작점 인덱스를 start, 끝점 인덱스를 end로 둔다. 2. start 인덱스에 해당하는 문자와, end 인덱스에 해당하는 문자를 비교하여 일치하면 ++start, --end를 수행한다. 3. 만약 start 인덱스에 해당하는 문자와, end 인덱스에 해당하는 문자가 일치하지 않는다면 count를 1 증가시키고 start를 1 증가시켜 문자 하나를 제외한 경우와 e..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 사용한 알고리즘: BFS 풀이전략 문제를 풀기 앞서 이분 그래프가 어떤 구조인지 알고 있어야 문제 풀이가 가능하다. 위와 같은 그래프가 있을 때, 인접한 노드끼리 서로 다른 색을 지니는 그래프를 이분 그래프라고 한다. 노드끼리 모두 연결되어 있지 않아도, 서로 인접한 노드끼리만 다른 색으로 구분될 수 있어도 이분그래프다. 이런 이분 그래프의 성질을 이용하여 BFS를 사용하면 문제를 풀 수 있..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 사용한 알고리즘: 플로이드 워셜(Floyd Warshall) 풀이전략 플로이드 워셜 알고리즘을 사용하여 모든 출발지에서 도착지까지의 최단 거리를 구한다. 단, 기존 플로이드 워셜 알고리즘에서는 자기 자신에게 가는 거리를 0으로 두고 알고리즘을 실행했지만 이 문제에서는 거리가 아닌 경로의 유무 판단이 중요 쟁점이기 때문에 모든 배열의 원소를 INF(무한)으로 초기설정한다. 그리고 입력에서 1로 경로가 있는 경우에만 배열 ..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 사용한 알고리즘 : 플로이드 워셜 알고리즘(Floyd Warshall) 풀이전략 전형적인 플로이드 워셜 알고리즘을 사용한 문제이다. 플로이드 워셜은 A에서 B로 가는 거리를 D(AB)라고 할 때, 다른 노드 K를 지나쳐 가는 것과 현재 거리를 비교하여 더 짧은 거리를 D(AB)에 저장시키는 알고리즘이다. 예로 D(AB) = Math.min(D(AB),D(AK)+D(KB))처럼 특정 노드 K를..