개발하는 고라니

코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr [DFS + 백트래킹] 입력으로 들어온 문자열을 한 글자씩 쪼개어 char[] 에 저장하고, 각 인덱스에 해당하는 문자마다 방문했는지를 체크하기 위한 boolea[] visit를 준비했다. 즉 "017" 이라는 문자열이 있을 때 0은 0번째, 1은 1번째, 7은 2번째로 , 0을 포함하고 있다면 visit[0] = true가 되고, 0을 포함한 채로 1을 포함하고 있다면 visit[0]과 visit[1] 은 참이 된다. 백트래킹을 이용했기 때문에 ..

2017 카카오코드 본선 코딩테스트 연습 - 리틀 프렌즈 사천성 리틀 프렌즈 사천성 언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만 programmers.co.kr [DFS + 백트래킹] 문제의 이해도는 어렵지 않은 편이었으나, 출력 형식에 주어진 문구가 마음에 안들었다. 해는 여러가지 일테니, 알파벳 순으로 가장 먼저인 답을 출력하라니... 열심히 풀었건만 저 문장 때문에 코드를 싹 갈아엎었다. 다른 사람들은 타일을 깰 수 있는 조건으로 현재 타일에서 수평/수직/왼쪽 위, 아래/오른쪽 위, 아래 타일이 있을 때 이렇게 나누어서 한 것 같다. 나는 그냥 탐색하도록 했다. 예를 들어 현재 ..

1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net [DFS + 백트래킹 + 비트마스킹] DFS를 이용해 백트래킹을 구현했고, 알파벳 'a' ~ 'z'까지 어떤 알파벳을 알고 있는지에 대한 정보를 비트마스킹으로 표현했다. 즉, 'a', 'b'를 알고있다면 0b00 0000 0000 0000 0000 0000 0011로 나타낼 수 있다. 그런데 남극의 단어는 "anta"로 시작해서 "tica"로 끝난다고 했으니, 'a', 'c', 'n', 't', 'i'는 반드시 알고있어야 한다. 그래서 check를 다음과..

6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 DFS 탐색 -> 방문 취소 가 이뤄져야 한다. # Code import java.io.BufferedReader; import java.io.IOException; i..

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net [DFS] 0번부터 N-1번을 시작 정점으로 총 N번의 DFS를 실시하는데, 각 DFS가 끝나면 해당 정점의 visit[current] = false로 다시 변경한다. 이는 백트래킹 문제에서 주로 쓰던 방법이다. 해당 아이디어의 출처는 다음 링크에 있다. www.acmicpc.net/board/view/34026 그리고 DFS를 한층 한층 진행할 때마다 depth를 증가시키며, depth가 5가 되면 결과 flag를 true로 변경하고 루프의 진행을 멈춘다. # Code public class Main { static List[] list = new ArrayList[..

1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net # 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하..