SilentWalk

문제 링크 참고 : 플로이드-워셜 알고리즘 풀이 과정 Floyd-Warshall 알고리즘을 되짚어보고 진행하면 수월하다. 문제에 주어지는 조건 (선수의 수 및 전적)을 int 형 2차원 배열로 표현할 수 있다. 주어진 예제라면 아래 표와 같이 표현된다. int 타입 2차원 배열로 표현하였으므로 위 표의 빈칸도 0으로 초기화되어있다. 따라서, 0은 자기 자신 또는 결과 모름을 의미한다. 1은 상대에게 승리했음을, -1은 상대에게 패배했음을 의미한다. 이후 1번 선수부터 아래의 과정을 반복한다. i번 선수가 승리한 상대 선수를 찾는다. 주어진 예제에서는 1번 선수가 2번 선수를 상대로 승리했다. 1번의 결과로 찾은 선수가 승리한 상대 선수를 찾는다. 주어진 예제에서는 2번 선수가 5번 선수를 상대로 승리했다..

문제 - 가장 먼 노드 풀이과정 BFS 방식으로 풀이를 진행 사전준비 각 Node마다 연결되어있는 Node들을 표현하기 위한 2차원 배열을 만든다. (boolean[n][n]) 이후 주어진 edge 정보를 바탕으로 서로 연결되어 있는 Node들 끼리는 해당 위치의 원소값을 true로 변경한다. 1번 Node로부터 얼마만큼의 거리에 떨어져 있는지를 표현할 1차원 배열을 만든다. (int[n]) 여기서 원하는 결과는 가장 먼 거리에 있는 Node의 갯수이므로 정확한 최대 거리를 꼭 알아야 할 필요성은 없다. 1번 Node로 부터 떨어져 있는 거리를 모르는 Node의 경우 원소값이 0인 상태로 존재한다. 1번 Node 부터 BFS 탐색을 시작할 수 있도록 준비한다. queue에 1번 Node를 enqueue ..

등굣길 풀이과정 주어진 n과 m에 대하여 이동 가능한 길을 grid로 나타낼 수 있다. 예를 들어 n = 3, m = 4이면 아래 그림과 같다. 문제의 제한 조건으로 이동 방향은 우측 및 하단 뿐이므로, 출발지점에서 우측과 하단으로 이동 가능한 방법의 수는 아래의 그림과 같이 나타낼 수 있다. 각각 오른쪽으로만 계속 이동하거나, 하단으로만 계속 이동해야 도달할 수 있는 위치이므로 이동가능한 방법의 가짓수는 모두 1이다. 나머지 비어있는 cell 들로 이동할 수 있는 방법은, 바로 위 cell에서 아래로 이동하거나 바로 왼쪽 cell에서 우측으로 이동하는 것 뿐이므로 나머지 각각의 cell들에 대한 이동 가능한 방법의 수는 바로 위쪽 cell까지 이동 가능한 방법의 수 + 바로 왼쪽 cell까지 이동 가능..

정수 삼각형 풀이과정 삼각형의 가장 아래쪽에서부터 두 줄을 선택한다. 아랫줄을 currentLine, 그 윗 줄을 nextLine으로 설정. currentLine[i] 또는 currentLine[i + 1] 중에서 큰 값을 선택하여 nextLine[i] 에 더한다. nextLine 이 삼각형의 꼭대기를 가리킬 때 까지 currentLine, nextLine을 삼각형의 위로 올려가며 2번 과정을 반복한다. 삼각형의 꼭대기에 최댓값이 저장되므로 이를 반환한다. 위 과정과는 반대로 위에서부터 아래쪽으로 내려가면서 계산할 수도 있지만, 이렇게 풀이를 진행 할 경우 삼각형의 가장 아랫줄을 순회하면서 최댓값을 찾는 과정이 추가되므로 비효율적이다. Code class Solution { public int sol..

N으로 표현 풀이과정 각 단계별로(숫자 N을 i번 사용) 표현할 수 있는 수는 크게 두 종류로 구분할 수 있다. N을 i번 이어 붙인 경우 이전 단계의 결과를 서로 사칙연산한 결과 예를 들어, 4번 째 단계라면 다음과 같은 경우의 수를 갖는다. N을 4번 이어붙인 경우 N을 3개 사용한 경우(바로 이전 단계)와 N을 1개(= 4 - 3)만 사용한 경우의 사칙연산 N을 2개 사용한 경우(전전 단계)와 N을 2개(= 4 - 2)만 사용한 경우의 사칙연산 N을 1개 사용한 경우(전전전 단계)와 N을 3개(= 4 - 1)만 사용한 경우의 사칙연산 이를 통해 특정 숫자 N만을 활용하여 어떤 임의의 정수 k를 만들 수 있는 방법은 다음과 같이 전개하여 찾을 수 있다. i개의 N을 사용하여 표헌할 수 있는 모든 수를..

문제 : https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 풀이과정 1. 이분탐색 범위 설정 입국심사에 걸리는 최소시간은 1분이고, 최대시간은 모든 입국 대기자가 가장 심사시간이 긴 심사관 1명에게 입국심사를 받는 경우(n * 최대심사시간)에 해당한다. 이 최소값과 최대값의 범위 안에서 이분탐색을 활용한다. 2. 임의의 시간 동안 입국심사 가능한 사람의 수 계산 심사관들의 입국심사시간이 [a_1, a_2, a_3..

문제 가장 작은 부분문제를 떠올리는 부분이 생각보다 무척 어려웠다. 문제의 조건을 정리하면 아래와 같이 표현할 수 있다. 앞으로 숫자를 더 지워야 할 때 어떤 숫자의 앞에 그 숫자보다 작은 숫자를 두지 않는 것 이를 전개하면, 아래와 같은 로직을 만들 수 있다. 앞에서부터 계속 두 개의 숫자를 비교하여 앞의 숫자가 작으면 버리고, 아니면 취한다 하지만 문제 풀이를 떠올리는 과정에서 특정 상황별 대처 방법을 같이 떠올리고 추가하려고 하다 보니 자연스럽게 가장 작은 부분문제에서 멀어지는 문제가 발생하였고, Greedy한 풀이에서 자꾸만 멀어지는 모습을 확인하였다. Greedy 알고리즘 문제풀이 연습이 좀 더 필요할 것 같다. 코드 제출 후 다른 풀이를 찾아보니 굉장히 깔끔한 풀이가 있어서 이를 참고하여 코드..

풀이 과정 프림 알고리즘을 떠올리면 풀이를 쉽게 진행할 수 있다. 섬의 갯수가 1 이상, 100 이하로 주어졌으며 절대로 연결될 수 없는 섬은 주어지지 않는다고 하였으므로 시작지점을 임의로 0번 섬으로 지정하여도 아무런 문제가 없다. 기본적인 풀이의 진행방식은 아래와 같다. Edge의 cost에 대해 오름차순 정렬하는 Priority Queue를 준비한다. 현재까지 방문한 각 섬에 대하여 이하의 과정을 수행한다. 전체 edge에서 현재 선택중인 섬과 연결된 edge를 찾는다. 해당 edge의 다른 한 쪽 끝이 아직까지 방문하지 않은 섬과 연결되어있는지를 확인한다. 방문하지 않은 섬과 연결되어 있는 edge는 다음번에 설치될 다리가 될 가능성이 있으므로 1에서 준비한 Priority Queue에 추가한다...