개발개발

1. 문제 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 2. 풀이 오른쪽에서 레이저를 쏘기 때문에 오른쪽으로 시작 할 수 있지만, 그렇게 하면 최악의 경우 N!의 복잡도가 발생할 수 있다. 따라서, stack을 활용해 오른쪽부터 계산한다. 풀이 과정은 아래와 같다. 탑의 위치와 높이를 스택에 모두 저장하기 위해 별도의 클래스를 만든다. 탑의 왼쪽부터 시작한다. while문을 이용해 stack에 있는 탑들을 돌아보며, 현재의 탑 높이가 스택..

1. 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 풀이 BFS로 풀이했다 (1) n층을 최소한의 버튼을 눌러 도착했을 때의 버튼 누른 횟수를 저장하는 배열(minBtn)을 사용해 정답을 구하고, 중복을 체크하는데 사용한다. (2) 위의 최소 버튼 누른 횟수를 저장하는 배열(minBtn)에서 시작점의 버튼 누른 횟수를 0이 아닌 1로 처리해, 시작점과 처음 도착한 층의 차이점을 만들어 처리한다. (3) 맨 마지막 정답을 처리할때, +1 한 값을..

1. 문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 2. 풀이 BFS를 써서 풀이한다. 처음에는 큐에서 poll 했을때 촌수를 높이는 걸로 처리를 했는데, 그렇게 하면 연결되지 않는(?), 결과에 상관없는 촌수를 계산할 때까지 더하기 처리가 나서 실패했다. 그래서 기준점을 잡아서, 기준점과의 촌수를 계산하는 배열을 따로 만들어 처리했다. 3. 코드 import java.util.Arrays; import java.ut..

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..