개발개발

1. 문제 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 2. 풀이 시작점에서 부터 다익스트라로 최단 경로를 구한다. 도착점에서 부터 거슬러가며 최단 경로를 따로 표시한다. k[i][j] = 1; // i~j까지가 최단 경로면 1 원래의 리스트에 간선 중 최단 경로가 아닌 간선만 추가해 리스트 갱신 최단 경로를 뺀 간선으로만 다익스트라를 돌림 3. 코드 import java.io.*; import java.uti..

1. 문제 https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 2. 풀이 처음엔 플로이드 와샬을 써야하는가....? 싶었지만 LCA를 써서 푸는 문제였다. LCA에서는 조상 노드들을 따로 저장하는 배열(parent)가 있는데, 이 때 노드에서부터 2^i번째 노드까지의 최솟값, 최댓값을 저장하는 따로 저장하는 것이 포인트다. 3. 코드 import java.io.*; import java.util.Array..

1. 문제 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 2. 풀이 LCA를 구현하는 문제다. LCA는 최소 공통 조상을 구하는 문제다. LCA를 구현하기 위해 현재 노드의 부모를 2차원 배열에 저장하는 방법과 1차원 배열에 저장하는 방법이 있다. 1) 부모를 2차원 배열에 저장 부모를 2차원 배열에 저장할 경우 첫번째 차원에는 노드의 인덱스가 담기고 두번째 차원에는 노드의 2^i번째 조상 노드가 저장된다. 2) 부모를 1차원 배열에..

1. 문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 2. 풀이 플로이드 와샬을 활용한 문제다. 문제의 예제에서 나온 그래프를 잘 보자. 여기서 순서를 정할 수 있는 노드는 뿐이다. 4보다 큰사람이 , 로 2명이고, 4보다 작은 사람이 , , 로 3명이므로 총 6명 중 나보다 큰 사람 2명, 나보다 작은 사람 3명 => 나는 3등 이라는 결론을 얻을 수 있는 것이다. 즉, 현재 노드가 다른 노드들과 모두 연결되어 있는 경우 순서를 따질 수 ..

1. 문제 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 2. 풀이 투포인터를 사용해 풀이한다. A의 부분합과 B의 부분합의 합을 구해야하는 상황이므로 A의 부분합과 B의 부분합을 미리 구해놓고 A의 부분합과 B의 부분합을 각각 정렬해 투포인터를 이용해 합이 T일 경우, answer에 추가한다 +) A의 부분합과 B의 부분합이 중복될 경우 한번에 처리해주기 위해,..

1. 문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 코드 import java.util.Scanner; // 백트래킹 public class Main { static int answer = 0; public static void nQueen(int[] arr, int n, int depth) { if(n == depth) { answer++; return; } for(int i = 0; i < n; i++) { // 한 row에서 퀸을 놓을 수 있..

1. 문제 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 2. 풀이 이진탐색을 사용한다. 새롭게 해야 하는 게임의 수를 이진탐색을 사용해서 찾는다. 소숫점을 버리기 위해 새로한 게임을 포함한 승률을 구하는 가정에서 100을 곱하게 되는데, 이 때 int 범위의 수가 넘을 수 있으므로 long 처리를 해줘야 된다는 것을 주의 해야 한다. 3. 코드 import java.util.Scanner; //이진탐색 public class Main..

1. 문제 https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 2. 풀이 투포인터와 BFS를 모두 활용한다. 구해야 되는 것은 가장 작은 고도의 차이므로, 가장 높은 고도(high)와 가장 낮은 고도(low)를 설정해 그 고도 내에서 집배원이 모든 집을 방문할 수 있는지 본다. 투포인터를 이용해 low 값 과 high 값을 변경해가며 가장 작은 고도차를 찾는다. 고도 내에서 모든 집을 방문할수 있는지 확인 할 때 BFS를 사용한다..

1. 문제 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 2. 풀이 숫자가 A, B, C, D 총 네종류가 있고 합이 0이 되는 A, B, C, D 쌍을 구해야 한다. 이를 A와 B의 가능한 모든 합과 C와 D의 가능한 모든 합으로 나누어 구하고 A와 B의 합과 C와 D의 합 중 0이 되는 쌍을 찾는다. 즉, (A+B) + (C+D) 이런식으로 나누어 생각하는 것이다. A와 B의 합과 C와 D의 합은 가능한 모든 경우의 수를..

1. 문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 2. 풀이 방법 1) 우선 순위 큐 사용 자바로 우선 순위 큐를 사용해 정렬 된 값을 바로 사용해서 하려고 했더니 시간 초과가 난다. 자바로 풀기 위해 다른 방법을 찾아 봤다. 방법 2) Deque 사용 숫자가 있는 위치와 숫자의 값을 모두 Deque에 넣어 풀이하는 방법이다. (1) 현재 숫자를 입력 받는다. (2) 현재 덱 내에 있는 수 중 뒤에서 부..