Java

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 사용한 알고리즘 : DFS, 백트래킹, 시뮬레이션(구현) 풀이전략 문제 풀이 핵심 키워드는 아래 2가지다. 1. DFS를 통해 모든 경우의 수를 중북 순열로 완전 탐색을 진행한다. 2. 상하좌우 이동 시, 변경된 상태를 나타내는 2차원 배열을 원래 블록판 상태를 나타낸 2차원 배열의 내부 값 변경을 통해 구하면 시간 초과가 발생한다. 따라서 별도의 배열을 생성하고, 생..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 사용한 알고리즘 : 위상정렬(Topological_Sort) 풀이전략 문제는 연출자들이 정한 가수의 출연 순서를 모두 만족시키는 공연 순서를 출력하는 것이 목표로 대표적인 위상정렬 알고리즘을 통해 해결이 가능한 문제이다. 위상정렬 : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 위와 같은 방향 그래프가 주어졌을 때 이를 위상 정렬로 나..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 사용한 알고리즘 : 분리 집합, DFS 풀이 전략 문제에서는 회원들이 발판을 따라 움직인다고 할 때, 회원들이 반복되는 싸이클로 인해 계속해서 발판을 움직이며 돌지않고 중간에 멈출 수 있도록 SAFE ZONE을 만드려고 한다. 이 때 이를 만족시킬 수 있는 SAFE ZONE의 최소 개수를 구하는 것이 목표이다. 풀이 방법이 여러가지 있겠지만, 나는 분리 집합과 ..

https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 사용한 알고리즘 : MST(최소 스패닝 트리) 풀이 전략 전형적인 최소 스패닝 트리를 사용한 문제이다. 그래프의 모든 간선들 중에서 비용이 가장 적은 간선을 하나씩 더해간다. 단, 더해가는 과정에서 싸이클이 발생하지 않아야하며 최종적으로는 모든 정점들이 이어져야 한다. 문제에서 주어진 예제 입력2를 그림을 통해 설명해보겠다. 위 예제에서는 작은 순서 그대로 추가해도 싸이클이 생기는 문제가 없었다...

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 사용한 알고리즘 : 자료 구조(List) - 구현 문제 풀이전략 이 문제에서 가장 신경써야할 부분은 명령어로 'R'이 주어졌을 경우 배열을 뒤집느냐 뒤집지 않느냐이다. 만약 'R' 명령이 들어올 때마다 배열 뒤집기를 실행한다면 최악의 경우 시간 복잡도는 아래와 같다. 배열에 들어갈 수 있는 수는 최대 100,000개이고 명령어의 길이 또한 최대 100,000번이 가능하다. 배열 내부의 수가 100,000개 일 때, 'R'로 인해 뒤집기 연산을 수행하면 ..

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 사용한 알고리즘 : LCA(Lowest Common Ancestor, 최소 공통 조상) 풀이 전략 위 문제에서 주어진 첫 번째 입력을 그래프로 나타내면 아래와 같다. 문제에서는 16과 7의 가장 가까운 공통 조상인 LCA를 구하라고 주어졌다. 결론부터 말하면 눈에 보이듯 4인데, 이를 알고리즘적으로 어떻게 구할 수 있을지 생각해보자. 먼저 LCA..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 사용한 알고리즘 : BFS 풀이전략 모든 경우의 수를 BFS를 사용해 완전탐색하는 문제이다. 물통에서 물을 옮길 수 있는 경우의 수는 총 6가지로, 1. A물통-> B물통 2. A물통-> C물통 3. B물통 -> A물통 4. B물통 -> C물통 5. C물통 -> A물통 6. C물통 -> B물통 이 있다. 그런데 물을 옮길 때 조건으로 한 물통이 빌 때까지 물을 다른 물통에 쏟거..

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 사용한 알고리즘 : 세그먼트 트리 풀이전략 만약 완전 탐색을 통해 문제를 푼다고 생각해보자. 그러면 최악의 경우, 수의 개수 N = 1,000,000 , 수 변경 횟수 M = 10,000, 구간 곱 구하는 횟수 K = 10,000으로 1,000,000 * (10,000+10,000) = 20,000,000,000(200억)번의 연산이 ..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 사용한 알고리즘 : 위상정렬(Topological Sorting) 풀이전략 문제들을 주어진 이전 단계를 거쳐가야만 풀 수 있으므로 위상 정렬 알고리즘을 사용해야한다. https://chaechaeros.tistory.com/199 [BOJ 1766] 문제집 - JAVA, Gold2 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 사용한 알고리즘 : 위상정렬(Topological Sorting) 풀이전략 위상정렬에 대해 먼저 알아야하는데 아래 유튜브 링크를 참조하여 개념을 작성했다. https://www.youtube.com/watch?v=xeSz3pROPS8 위상정렬 : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 위와 같은 방향 그래프가 주어졌을 ..