[백준 12094] 2048 (Hard) (자바)
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개의 줄에는 게임판의 초기..
[백준 2957] 이진 탐색 트리 (자바)
https://www.acmicpc.net/problem/2957 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net 난이도 : 플레 5 문제에서 보여준 수도 코드로 트리를 구현하여 정직하게 풀면 시간 초과가 납니다. 최대 30만 개의 입력이 들어옵니다. 1~30만까지 차례대로 입력이 주어졌을 때 정석 풀이대로 한다면 O(N^2)의 시간 복잡도이기 때문에 시간 초과가 납니다. 저는 TreeSet을 이용하여 풀었습니다. 제가 생각한 풀이가 너무 복잡해 다른 풀이를 보며 공부하다가 TreeSet의 lower와 ..
[백준 5427] 불 (자바)
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..
[백준 5557] 1학년 (자바)
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형입니다. 이것을 주의하여..
[백준 12100] 2048 (Easy) (자바)
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 입력을 받고 게임을 시작한..
[백준 2252] 줄 세우기 (자바)
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학..
[백준 2493] 탑 (자바)
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 �� www.acmicpc.net 난이도 : 골드 5 스택과 우선순위 큐를 이용하여 풀었습니다. 스택에서 하나씩 pop 하여 우선순위 큐에 있는 값과 비교하고, pop 한 값이 더 크다면 우선순위 큐에 있는 값에 그 인덱스를 남겨줍니다. 문제에서 주어진 예제를 그림으로 이해하기 쉽게 표현해 봤습니다. 표 밑은 우선순위 큐(value, index)이고 좌측은 스택입니다. 메소드 void main 스택에 입력을 받고 우선순위 ..