개발하는 고라니

12763번: 지각하면 안 돼 1호관에서 3호관, 4호관을 거쳐 5호관으로 간다면, 3시간만에 3500원의 지출로 도착할 수 있다. (다행히 이번 수업은 휴강이었다고 합니다.) www.acmicpc.net [Dijkstra + DFS] N개의 정점을 탐색하는 것에서 그래프 문제임을 유추할 수 있고, 조건이 주어지며 최소한의 값으로 목표 정점에 도착하는 것을 구하는 것에서 최단경로 문제임을 유추할 수 있다. 그저 그런 다익스트라 문제인줄 알고 여유롭게 풀었지만 85% 쯤 오답판정을 받았다. 이럴리가 없는데..하면서 몇 번을 다시 제출했지만 여전히 오답이었다. 틀린 이유에 대한 해답은 질문 게시판에서 찾을 수 있었다. 링크 : https://www.acmicpc.net/board/view/37703#post..

코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 나의 문제 접근법 주어진 문자열을 문자 배열로 변환하고, 각 문자로의 이동 회수를 구했다. 예를 들어 "JAN"이라는 문자열이 주어지면 첫번째 'A'에서 'J'로 갈 수 있는 이동횟수는 오른쪽으로 이동했을 때 9회, 왼쪽으로 이동했을 때 16회인데, 이 둘 중 최소값인 9를 택한다. 마찬가지로 두번째 문자에 대해서도 동일한 방법으로 이동회수를 구한다. 현재 문자에서 왼쪽과 오른쪽으로 탐색을 하는데, 이 때 'A'가 아닌 문자가 있는 곳을 찾는..

코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 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] 은 참이 된다. 백트래킹을 이용했기 때문에 ..

코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr [BFS] BFS의 가장 전형적인 문제. 최단거리를 구할 때 DFS를 이용하려할 수도 있는데, 이는 잘못된 것이다. DFS가 탐색하는 곳은 항상 최적해(최단거리)는 아니기 때문이다. # Code import java.util.LinkedList; import java.util.Queue; class Solution { static class Point{ int y, x, move; public Point(i..

4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net [DFS] 다수의 테스트 케이스 중 DFS를 이용해 사이클이 존재하는 것을 찾아 제외하고, 트리의 개수를 찾는 문제이다. 트리의 특징은 문제에서 잘 나타내어주고 있으며, 정점이 하나만 있는 것 역시 트리라고 본다. 문제의 입력과 출력이 번거로워서 그렇지 문제 자체의 난이도는 크게 어렵지 않다고 생각된다. 사이클을 찾는 방법은 글로 푸는 것 보다 코드가 간단하므로 코드를 보는 것이 더 빠르게 이해가 될 것 같다. static boolean DFS..

18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net [BFS + 우선순위 큐] 1초마다 낮은 번호의 바이러스부터 상하좌우 인접한 칸(단, 0인 곳)으로 한 칸씩 전염시킬 수 있으므로 우선순위 큐를 사용해 낮은 번호의 바이러스부터 퍼지게 한다. 그러려면 입력을 받을 때 모든 바이러스를 우선순위 큐에 넣는다. 그리고 s번의 루프를 수행하고, 각 루프마다 BFS를 실행하는데 일반적인 BFS는 다음 탐색할 정점을 동일한 큐에 저장하는데 반해, 이 문제에서는 다른 큐(tmpQ라고 지정)에 저장..

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

3709번: 레이저빔은 어디로 레이저박스라는 게임은 정사각형 모양의 n x n 보드에서 진행한다. (체스판을 상상하면 된다) 레이저박스의 임의의 칸마다 우향우 거울이라는 장치가 설치되어 있고, 마지막으로 레이저 한개가 www.acmicpc.net [DFS] N x N 격자의 밖에서 레이저빔을 쐈을 때 우향우 거울을 통해 반사되어 최종적으로 레이저빔이 도착한 위치를 찾는 문제. 레이저 빔은 이미 지나온 곳도 다시 지날 수 있다. 그렇다고 해서 방문을 했는지 여부를 체크하지 않으면 안된다. 문제에서 주어진 것을 보면 알 수 있듯, 레이저빔이 격자 밖을 빠져나가지 못하면 0 0을 출력하라고 한 것을 보아 방문을 체크하지 않는다면 무한루프에 빠져 Stackoverflow 에러가 발생할 것이다. 그러면 어떻게 방..