전체 글

문제 (Gold 3) https://www.acmicpc.net/problem/4933 4933번: 뉴턴의 사과 각 테스트 케이스에 대해서, 두 트리가 동등하면 true를, 아니면 false를 출력한다. www.acmicpc.net 풀이 입력 받은 값을 어떻게 트리로 만드느냐를 생각하는 것이 관건. 입력은 포스트오더(후위순회)로 주어진다고 하니 stack을 활용하여 트리 구성 후위순회로 주어진 그래프의 stack 변환 로직 1. 현재 넣으려는 노드(i)가 null이 아니고, 이미 스택에 2개 이상 쌓여있다면 2. 맨 나중에 넣은 노드(stack.pop())가 오른쪽 노드 3. 그 전에 넣은 노드(stack.pop())가 왼쪽 노드 4. right와 left노드의 부모를 현재 노드(i)로 설정 5. 현재 ..

문제 (Gold 2) https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 모든 경로에 대한 최소 비용을 구해야 하므로 '플로이드-워샬 알고리즘' 사용! 최소 비용 외, 경로에 대한 내용도 저장해야 하므로 이차원배열 변수 하나 더 선언 map[i][j]: i -> j 경로의 최소 비용 저장 path[i][j]: i에서 출발해서 j까지 도착하기 직전에 들르는 도시 바로 오는 길(map[i][j])보다 경로 k를 거쳐서 오는 길(map[i][k..

문제 (Silver 2) https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 풀이 접근 설명 1과 0을 1과 -1이라고 생각하자! ( 부호의 차이로 생각하자! ) 2의 제곱 수(2,4,8,16,...)만큼 앞뒤로 대칭되고 있는 문자열! 즉, N보다 작은 2의 제곱수를 뺀 인덱스 값(N - (2*?)) 을 알면 N의 값을 알게 됨 위의 예시로 설명하자면, 27번째 값은 11번째 값과 같음(부호만 반대) 11번째 값은 3번째..

문제 (Silver 2) https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이 1. 양 또는 늑대가 있는 영역을 검사 (BFS) 2. 그래프를 돌며 양과 늑대의 위치 저장 3. 탐색 후, 양과 늑대 리스트 크기 비교 후 map에 반영 코드 더보기 import java.util.*; import java.io.*; public class Main { static int[] di = {-1,0,1,0}; static int[] dj =..

문제 (Bronze 5) https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 풀이 문자열을 캐릭터 배열로 변환하여 하나씩 비교하는 문제 코드 더보기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStr..

문제 https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 풀이 모든 정점에 대한 최단 경로를 탐색하는 다익스트라 알고리즘 문제 가장 중요한 고려사항은 늑대의 경우 홀수/짝수번째로 건넜을 경우를 각각 저장해 줄 수 있어야 함! 속도가 /2가 될 수 있으므로 소수점 방지를 위해 처음 입력 받을 시 weight에 *2 를 곱하여 저장! 다익스트라 알고리즘은 PriorityQueue를 사용하여 구현..