전체 글

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 📌구현할 기능 목록 1. 기존 세로선, 가로선 수와 앞으로 세로선에 추가할 수 있는 가로선의 개수를 입력받는다. 2. 기존의 가로선들을 입력받는다. 3. 백트래킹을 사용해 사다리를 놓을 수 있는 가로선들 중 0~3개의 사다리를 추가하여 조건(i번째 사다리에서 사다리 타기로 내려갈 때, 결과가 i)에 성립하는 최소 추가 사다리 개수를 구하는 함수 작성 4. 조건 만족을 위한 최소 추가 사다리 개수..

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 📌구현할 기능 목록📌 1. 드래곤 커브의 개수 그리고 각 커브의 좌표, 방향, 횟수를 입력받는다. 2. 101 x 101 크기의 맵을 생성하여, 특정 좌표가 드래곤 커브로 생긴 선분 위의 좌표인지 확인할 수 있도록 이중 ArrayList 를 생성한다. 3. 각 드래곤 커브에서, 주어진 방향에 맞도록 선분을 추가한다. 4. 주어진 횟수만큼 드래곤 커브를 진행하는 함수를 작..

https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 사용한 알고리즘 : LIS, 이진탐색 풀이 전략 위 문제에서 주어진 예제를 그대로 사용할 때, 앞 A 전봇대를 오름차순으로 정렬하고 B 전봇대를 기준으로 LIS를 구하면 [3,6,7,9,10] 이라는 결과가 나옵니다. 따라서 (처음 입력받은 전깃줄의 개수) - (LIS로 구한 배열의 크기)를 구해 제거해야 할 전깃줄의 개수를 구할 수 있습니다. 하지만 문제에서 제거해야할 전깃줄의 개수와 전깃줄..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net [문제 유형 : 구현] 📌구현할 기능 목록📌 1. 지도의 크기(N)와 경사로의 길이(L)를 입력받는다. 2. 지도의 각 위치별 높낮이를 입력받고 2차원 배열에 저장한다. 3. 지도에서의 한 열을 1차원 배열로 변환시켜줄 수 있는 메서드를 작성한다. 4. 매개변수로 전해받은 1차원 배열에 대해서 경사로를 사용해 지나갈 수 있는지 검사하는 메서드를 작성한다. - 아래의 3가지 경우를 생각하여 구현 로직을 달리한다. 1) 이..

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 📌구현할 기능 목록📌 1. 파이어볼 객체를 구현할 클래스를 작성한다. - 행 위치, 열 위치, 질량, 속도, 이동방향 값을 저장할 필드를 가진다. 2. 각 위치를 나타내는 격자를 N x N 크기의 삼중 ArrayList로 생성한다. - ArrayList map = new ArrayList(); - 마지막 ArrayList에서 Fireball 객체를 저장하면서..

https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 사용한 알고리즘 : 구현 풀이전략 1. 구름 이동 후 해당 지역 바구니에 물 1 추가 2. 물복사 버그 (비가 내렸던 지역의 대각선 지역 양동이가 0이 아닌 개수만큼 +) 3. 맵에서 비가 내렸던 지역을 제외한 지역들 중 양동이의 물이 2이상인 지역에 구름 생성 4. 모든 지역의 양동이 물 총합 출력 1. 구름 이동 후 바구니에 물 1 추가 static int dx[] = {0,-1,-1,..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 사용한 알고리즘 : 백트래킹, DFS를 통해 구현한 조합, 구현 풀이전략 문제에서 핵심은 기존의 모든 치킨집들 중에서 M개의 치킨집만 남겼을 때, 가장 최소의 치킨 거리를 구하는 것이다. (치킨 거리란 모든 가정집에서 남김 특정 치킨집까지의 최소 거리 합을 뜻한다.) 1. 조합을 사용해 모든 치킨집들 중 M개의 치킨집을 선정한다. 2. 각 가정집에서 조합으로 구한 M개의 치킨..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 사용한 알고리즘 : DP 풀이전략 DP 문제를 풀 때, 보통 맨 처음 입력으로 주어진 값을 시작으로 반복성을 찾아낸다 하지만, 이 문제에서는 입력의 맨 뒤부터 반복성을 찾아야 풀 수 있는 문제이다. 위 표는 문제에서 주어진 1번 예제 입력을 대입했을 경우, 얻을 수 있는 최대 수익을 나태는 표이다. d[i]는 i~N일 사이에 얻을 수 있는 최대 수익을 뜻한다. (예로 d[3]은 3~7일 사이에 얻을 수 있는 최대 수익을 뜻함) 이 문제는 입력의 맨 뒤부터 시작하여 반복성을 찾아야 한다고 했는데, 아래와 같은 반복성을 띈다. 7일 : ..

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) 풀이전략 문제는 연출자들이 정한 가수의 출연 순서를 모두 만족시키는 공연 순서를 출력하는 것이 목표로 대표적인 위상정렬 알고리즘을 통해 해결이 가능한 문제이다. 위상정렬 : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 위와 같은 방향 그래프가 주어졌을 때 이를 위상 정렬로 나..