SilentWalk

문제 풀이과정 문제를 풀기에 앞서, 문제에 주어진 조건을 먼저 살펴보면 단체사진을 찍을 프렌즈는 8명으로 고정되어있음을 알 수 있다. 즉, 만일 무조건 만족할 수 있는 조건만 주어졌다면 최대 8! = 40320 개의 경우의 수가 존재함을 알 수 있다. 조건의 최대 갯수는 100개로 주어졌다. 따라서 모든 가능한 경우의 수를 먼저 계산한 후, 각각의 경우의 수가 조건을 만족하는지를 확인하게 된다면 최대 약 400만 번의 조건 확인 작업을 거치게 될 것임을 알 수 있다. 위의 두 가지 점으로부터 미루어 보아 조건을 생각하지 않고 모든 가능한 경우의 수를 먼저 구한 후, 각각의 경우의 수가 주어진 조건을 모두 만족하는지 검사하여도 크게 시간적으로 무리가 가지 않을것이라 예상하였다. 풀이과정은 아래와 같은 과정..

문제: https://programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 풀이과정 전형적인 DFS, BFS 문제라고 생각된다. 문제 풀이는 아래와 같이 진행하였다. (0, 0)부터 시작하여 순차적으로 picture에 속한 모든 원소를 순회한다. 순회 중 임의의 어떤 (i, j)번 째 원소에 대해서, picture[i][j] != 0 이고, visted[i][j] == false 이면 (i, j)번 째 원소는 아직 계산되지 않은 영..

문제 - 프로그래머스 "여행경로" 풀이 과정 주어진 공항의 이름을 오름차순 정렬한다. 이동 가능한 경로가 2개 이상일 경우 알파벳의 오름차순으로 경로를 결정하기 위해 사용한다. 이름의 오름차순 정렬한 공항들에 index를 설정한다. 이 [이름 - index] 관계는 주어진 티켓에 따른 각 공항별 잔여 방문 횟수를 나타내는 2차원 배열을 나타내기 위해 사용한다. 위 1과 2에서 준비한 결과물을 바탕으로 출발/도착 공항별 잔여 방문 횟수를 2차원 배열로 나타낸다. 문제에서 주어진 예제 1번의 경우 아래의 표와 같이 나타낼 수 있다. DFS 방식으로 방문할 공항을 탐색한다. 최종 결과물을 주어진 조건에 맞게 공항의 이름으로 변경하여 반환한다. DFS 전개 주어진 출발공항을 현재까지 확인한 여행경로 Queue에..

문제 : 단어 변환 - 프로그래머스 풀이과정 문제에서 주어진 조건은 다음과 같다. 한 번에 한 개의 알파벳만 바꿀 수 있다. words에 있는 단어로만 변환할 수 있다. 이 조건으로부터 우리는 매 턴 마다 현재 단어에서 바뀔 수 있는 단어들을 찾아낼 수 있다. 예를 들어, 문제에서 주어진 예시를 보면, begin 으로 "hit"가 주어졌으며, words로는 ["hot", "dot", "dog", "lot", "log", "cog"]가 주어졌다. "hit"에서 변화할 수 있는 알파벳은 'h', 'i', 't' 셋 중 하나이다. 여기서 words에 있는 단어들로부터, 'h', 'i', 't'가 각각 어떤 알파벳으로 변할 수..

네트워크 풀이과정 모든 컴퓨터는 자기자신에 대해서 연결됨 상태로 주어지는 것을 이용한다. 기본적인 골자는 다음과 같다. (i, i) 번 째 좌표에서 탐색을 시작한다. 탐색 시작시마다 이미 해당 컴퓨터를 확인했음을 표시한다. i번 째 row를 통해 연결되어있는 컴퓨터들을 모두 확인한다. 연결된 컴퓨터들의 번호를 k라 할 때 (k, k)번 째 좌표에서 다시 탐색을 시작한다. (DFS) 이미 확인되었음 표시가 있다면 스킵하고, 그렇지 않다면 그대로 진행한다. 1번 과정에서 한 번 빠져나올 때 마다 식별한 네트워크의 갯수를 1 증가시킨다. 더이상 탐색할 컴퓨터가 없으면 모든 탐색을 종료하고 식별된 네트워크의 총 갯수를 반환한다. 시나리오 n = 7 이고, 1-2-3과 4-5-6 및 7 으로 세 개의 네트워크를 ..

타겟 넘버 풀이과정 문제에 주어진 예제 2번을 살펴보면 다음과 같은 그림을 그릴 수 있다. (주어진 조건 : numbers = {4, 1, 2, 1}, target 4) 0에서부터 주어진 숫자들을 +, - 해 나가는 Tree를 만든 후(BFS) 최종 결과값을 확인하며 target과 일치하는 것의 갯수를 세면 정답을 찾을 수 있다. Code import java.util.ArrayDeque; import java.util.Queue; class Solution { public int solution(int[] numbers, int target) { Queue queue = new ArrayDeque(); queue.offer(0); for (int number : numbers) { int size = ..