본문 바로가기
728x90

알고리즘(w.KOTLIN)/탐색

 (23)
[백준][코틀린][4574] 스도미노쿠 https://www.acmicpc.net/problem/4574 4574번: 스도미노쿠 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 www.acmicpc.net 문제 풀이 1. sudomiku 배열을 선언하고 주어진 입력을 저장한다. 2. 완전 탐색을 수행한다. 이때 9 X 9 의 보드판이므로 완전 탐색의 depth 가 81이 되면 결과를 출력한다. 3. depth 81 인 경우가 여러 가지가 나올 수 있으므로 completed flag 를 설정하여 출력은 한 번 하면 다음번 depth(81) 조건을 만족하는 경우는 무시한다. 4. 도미노..
[백준][코틀린][12100] 2048 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 풀이 1. board 정보를 저장하는 2차원 배열을 선언한다. 2. 현재 board 판의 정보과 이동 횟수를 저장하는 Queue 선언하고 BFS 탐색을 한다. 3. 상/하/좌/우를 탐색한다. 이때 문제에서 주어진 숫자가 합쳐지는 경우를 처리하기 위해서 stack 에 저장한다. 4. 한 번 합쳐진 블록은 합쳐지지 않으므로 stack 을 처리할 때 combined f..
[백준][코틀린][1062] 가르침 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제 풀이 1. 남극의 단어가 anta, tica 로 시작되기 때문에 최소한 알파벳 a, n, t, i, c 는 알아야 한다. 2. 따라서 K 가 5보다 작을 경우에는 단어를 읽을 수 있는 경우가 없으므로 "0" 을 바로 출력한다. 3. 주어진 단어들을 String 배열에 저장한다. 4. 소문자 a ~ z 까지를 index 로 가지는 26 크기의 visit 배열을 선언하고 a, n, t, ..
[백준][코틀린][14225] 부분수열의 합 https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 문제 풀이 1. 부분수열을 구하기 위한 DFS 탐색을 수행한다. 2. DFS 수행 시 depth 를 1 부터 N 까지 설정하여 부분 수열을 구한다. 3. result list 를 최대의 크기인 2,000,001 크기로 설정하고 초기 값을 1로 한다. 4. 부분 수열의 합을 result index 로 넣고 value 를 0으로 설정..
[백준][코틀린][1987] 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 풀이 1. 주어진 입력을 저장하는 board 2차원 배열을 선언한다. 2. 이전 경로를 방문했는 지 여부를 확인하는 visit 배열을 선언한다. index 는 {현재 알파벳 - 'A'} 로 구한다. 3. result 에 최대값을 저장한다. 코드 import java.io.* private var result = Int.MIN_VALUE fun main(args: Array) { val..
[백준][코틀린][9663] N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 1. 체스 판에 놓여진 퀸을 기준으로 가로/세로/대각선 방향으로 공격할 수 있기 때문에 다른 퀸을 놓을 수 없다. 2. 따라서 퀸을 하나 놓으면 놓여진 행에는 다른 퀸을 놓을 수 없기 때문에 탐색을 할 필요가 없다. 3. 놓여진 퀸의 열을 탐색하여 놓을 수 있는 열이 있는 지 확인 한다. 4. 대각선의 경우 오른쪽 위에서 부터 시작하는 대각선과 왼쪽 위에서 부터 시작하는 대각선이 있다. 5. 탐색하는 ..
[백준][코틀린][15658] 연산자 끼워넣기(2) https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net 문제 풀이 1. 주어진 입력을 number 배열과 operator 배열에 저장한다. 2. operator 배열의 정보를 완전 탐색하는 DFS 를 수행한다. 3. 연산 결과를 구하는 것이기 때문에 DFS 수행 시 첫번째 num 값을 채워서 수행한다. 코드 import java.io.* private var max = Int.MIN_VALUE..
[백준][코틀린][1339] 단어 수학 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제 풀이 1. 주어진 입력을 중복 없이 알파벳으로 저장한 뒤 0 ~ 9 까지 하나씩 숫자를 넣어서 최대 합을 구하였더니 시간이 너무 오래 걸렸다. 2. 수학적인 접근 법을 이용하여 탐색 시간을 최소한으로 한다. 3. 문자열의 더하기에서 각 문자열은 숫자가 어떤 값인지는 알 수 없는 상황이지만 몇의 자리 수 인지는 파악할 수 있다. 예를 들어 입력이 GCF 일 경우 G 는 100의 자리 수,..

티스토리툴바