스톤헤드 부수기

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 난이도 : 골드 2 위상 정렬을 이용해 풀 수 있는 문제입니다. 하지만 세 가지 조건에 따라 풀어야 하는데 먼저 푸는 문제를 먼저 풀고 쉬운 문제부터 풀어야 합니다. 이 부분은 우선순위 큐를 이용하여 풀었습니다. 예제로 확인해보겠습니다. 4-2, 3-1 순으로 문제를 풀어야 합니다. 쉬운 문제부터 풀어야 하므로 우선순위 큐에는 3, 4가 들어갑니다. 3번을 풀고 연결..

https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 난이도 : 골드 1 Set을 이용한 BFS로 문제를 풀다가 오류를 만났습니다. 도저히 방법이 없어 검색해보니 비트 마스킹으로 쉽게 풀 수 있는 문제였습니다. 방문 검사는 3차원 배열을 통해 진행합니다. a~f까지 6개의 열쇠가 있으므로 [N][M][111111]의 크기를 가집니다. 비트 연산을 통해 key를 저장하고 문을 여는 것이 목표입니다. key를 넣는 과정은 ..

https://www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 난이도 : 플레 5 2020/10/02 - [문제풀이/자바] - [백준 12100] 2048 (Easy) (자바) [백준 12100] 2048 (Easy) (자바) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기..

https://www.acmicpc.net/problem/2957 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net 난이도 : 플레 5 문제에서 보여준 수도 코드로 트리를 구현하여 정직하게 풀면 시간 초과가 납니다. 최대 30만 개의 입력이 들어옵니다. 1~30만까지 차례대로 입력이 주어졌을 때 정석 풀이대로 한다면 O(N^2)의 시간 복잡도이기 때문에 시간 초과가 납니다. 저는 TreeSet을 이용하여 풀었습니다. 제가 생각한 풀이가 너무 복잡해 다른 풀이를 보며 공부하다가 TreeSet의 lower와 ..

https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에� www.acmicpc.net 난이도 : 골드 4 BFS를 이용해 풀었습니다. 2020/08/01 - [문제풀이/자바] - [백준 3055] 탈출 (자바) [백준 3055] 탈출 (자바) https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고 jellyinghe..

https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀�� www.acmicpc.net 난이도 : 골드 5 전형적인 DFS 문제입니다. 가 아니고 DP 문제였습니다. DFS로 풀었다가 시간 초과 났네요. 아무리 생각해도 DP로 풀 방법이 생각 안 나 검색해서 공부했습니다. 4 10 2 3 4 를 예로 들어보겠습니다. 이런 식으로 기존의 값에 +- n을 해주어 값을 최신화해줍니다. 이 예시의 출력은 0이겠네요. 단, 이 문제에서 수의 범위는 long형입니다. 이것을 주의하여..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 난이도 : 골드 2 난이도에 비해 어렵지 않은 문제였습니다. 백트래킹으로 구현을 하면 풀 수 있습니다. 총 5번의 이동으로 가장 큰 수를 구해야 하므로 각 이동(상, 하, 좌, 우)을 백트래킹을 이용해 구현했습니다. 전역 변수 n = 맵의 크기 answer = 5번의 이동이 끝났을 때의 가장 큰 값 map = 게임 판 메소드 void main 입력을 받고 게임을 시작한..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net 난이도 : 골드 2 위상 정렬을 통해 풀 수 있는 문제입니다. 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 사용할 수 있는 알고리즘입니다. 위상 정렬 설명을 위해 입학부터 졸업까지의 예시를 들어봤습니다. 물론 기사 신청에는 기능사 자격증이 필요없습니다. '입학' -> '1학년' -> '2학년' -> '기능사 자격증' -> '3학년' -> '4학..