SilentWalk

정수 삼각형 풀이과정 삼각형의 가장 아래쪽에서부터 두 줄을 선택한다. 아랫줄을 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에 추가한다...

문제 : https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이과정 주어진 자동차 정보(출입지점, 이탈지점)을 이탈지점을 기준으로 오름차순으로 정렬한다. (단, 여기서 모든 차량은 한 방향으로만 진행한다는 가정이 있어야 한다.) 맨 앞 차량(가장 먼저 이탈하는 차량)이 카메라에 잡히기 위해서는 반드시 이 차량의 [진입 지점, 이탈 지점]의 범위 내에 단속 카메라가 설치되어야 한다. 여기서 가장 다른 차량과 동선이 겹칠 가능성이 높은 지점은 이 차량의 이탈지점이다. 그 이유는 이미 1에서 이탈지점을 기준으로 오름차순 ..

문제 이 풀이 및 코드는 2022년 3월 14일 재검토 시점에 오답으로 처리되고 있습니다. 풀이과정 주어진 문자열의 현재 위치(시작시 0)에서 가장 가까운 ‘A’가 아닌 문자의 위치를 찾는다. 해당 위치까지 이동할 때, 좌우 방향 중 더 적은 이동횟수를 센다. 해당 문자를 ‘A’로 바꾸기 위해 상하 방향 조작 횟수를 센다. 2와 3의 결과를 더한다. 해당 문자를 ‘A’로 교체한다. 더이상 ‘A’ 문자가 없을 때 까지 1~4 과정을 반복한다. 위 과정처럼 문제를 풀이했을 때 테스트 케이스 11, 13, 23, 25, 26에서 실패가 발생한다. 이에, 위 과정 중 2번 과정에서 좌우 방향 이동횟수가 같을 때 어느 한 쪽 방향에 대한 우선도가 존재하는지 확인 해 보았으나 별도의 우선도가 존재하지는 않는 것으로..

문제 : programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 먼저, 각 학생별 체육복 도난 및 여분 보유 여부를 정리한다. 각 학생들의 체육복 보유 수량을 나타내는 정수 배열을 선언하고 그 값을 모두 1로 초기화한다. (시작시점에는 모든 학생이 체육복을 가지고 있다.) 도둑질 당한 학생들의 번호에 해당하는 원소들에서 1씩 뺀다. 여분 체육복을 가지고 온 학생들의 번호에 해당하는 원소들에 1씩 더한다. 이후, 맨 앞 학생부터 차례..