알고리즘||코딩테스트

https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 📌구현할 기능 목록 1. 격자 한 변의 크기, 색상의 개수와 각 격자 칸에 들어있는 블록의 정보를 입력받는다. - 격차 한 변의 크기 : 1~20 - 색상의 개수 : 1~5 - [블록의 정보] 검정 블록 : -1, 무지개 블록 : 0, 일반 블록 : 1~N 2. BFS 탐색을 통해 격자에서 가장 큰 블록 그룹을 찾는다. - 탐색으로 찾는 블록 그룹의 내부 블록 중, 무지개 블록이 아니면서 행/..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 📌구현할 기능 목록 1. 직사각형 맵의 크기와 맵의 좌표별 위치 정보를 입력받는다. - R, B, O 값을 입력받았을 경우, 해당 좌표값을 별도의 배열에 저장한다. 2. 1~10번 기울여 이동하여 조건에 만족하는 결과가 나오도록 DFS 함수를 구현한다. - 한번의 테스트 케이스를 마치면, 맵 정보와 빨간공, 파란공의 위치 좌표를 초기화하는 함수를 ..

https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net 📌구현할 기능 목록 1. 큐브를 돌릴 횟수와 방향을 입력받는다. 2. 큐브를 이중 배열 사용하여 손수 구현한다. 3. 큐브의 특정 부분을 원하는 방향으로 회전시키는 함수를 작성한다. 4. 윗면을 출력하는 함수를 작성한다. 🛠주요 로직 큐브를 이중 배열을 통해 구현하고 이를 회전시키는 작업을 수행할 것이다. 이 때, 회전 후 변경되는 큐브 내 배열의 위치를 하나라도 잘못 표기하지 않도록 주의해야한다...

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개의 치킨..