배움 저장소

programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr i번째 집을 방문하면 i-1번째 집을 방문할 수 없고 i-2번째 집을 방문할 수 있다. i번째 집을 방문하지 않으면, i-1번째 집을 방문할 수 있다. 배열을 만들어, 도둑이 집을 방문하며 얻은 최대값을 저장하면된다. 이때 i번째 집은 방문 하거나 방문 하지 않거나 선택할 수 있다. 최대값을 반환하면 되므로 다음과 같은 식을 세울 수 있다. i번째 최적값은 (i-2번째 최적값 ..

programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 먼저 떠오른 방법은 DFS, 정확성 테스트를 통과하였으나 효율성 테스트를 통과하지 못했다. 2차원 백터 위에서 동적할당 기법을 사용하면 된다는 생각은 했는데, 최단 거리 조건을 어떻게 넣을지 몰라 헤매다가 다른 풀이를 찾아보았다. 그런데 최단 거리 조건은 고려할 필요가 없었다. 왔던 자리를 돌아가지 않으면 최단거리 조건을 만족하기 때문이다. DP 기법을 사용할 때 ..

programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 동적계획법으로 문제를 풀기위해 데이터를 어떻게 구성해야하는지 여러 방법을 고민해봐야 한다. 3개 사용했을 때는 2개 사용한 경우와 1개 사용한 경우를 합친 경우다!라는 발견을 할 수 있어야 동적계획법으로 문제를 풀 수 있다. 증말 쉽지 않다~ N을 1개 사용했을 때, 2개 사용했을 때, 3개 사용했을 때, K개 사용했을 때로 나누어서 생각하는 것이 실마리. K개 사용하여 나온 숫자의 그룹을 S(K)라고 하자. S(2)는 S(1)과 S(1)을 사칙연산 한 경우를 넣고 N을 겹쳐만든 NN을 추가하면 된다. S(1) = { 4 } S(2) = { 44 } + ..

programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 처음 보고 떠오른 생각은 굳이 2차원 벡터로 나타낸 이유가 뭐지?라는 생각이었다. 1차원 백터와 인덱스를 사용하여도 정수 삼각형을 만들 수 있는데. 2차원 벡터로 문제를 풀어야하나 보다. 떠올린 풀이는 DFS. 구현을 했지만 시간 초과였다. 다른 방법을 찾아야 했다. 2차원 벡터를 만들어, 해당 자리까지 도달하기 위한 최대값을 저장해놓으면 될 것 같았다. 이전 값으로 현재 값을 업데이트 하는 방식을 사용하였다. 다른 사람의 풀이를 보니 현재 값을 기준..

programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 처음 문제를 보고 단방향 그래프로 문제를 풀어야 하는 줄 알았다. 이긴 사람 기준으로 단방향 그래프를 그려보고, 진 사람 기준으로 단방향 그래프를 그려보고, 방문개수가 적은 순에서 중복이 생기지 않을 때까지 승부가 결정된다고 가정해보고 문제를 풀었다. 아주 멋진 삽질이었다. 정답은 Floyd Warshall 알고리즘을 사용해서 풀어야한다. 2차원 벡터를 사용해 노드 i에서 노드 j까지 가는 최소 거리를 구한다. 그래서 모든 노드 간 최단 이동 거리를 2차원 벡터에 저장하게 된다. 그..

programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제를 보고 떠오른 풀이는 다익스트라. 다익스트라로 풀어야되는 건 알겠는데 구현 방법은 생각나지 않았다. GeeksForGeeks를 보는데 너무 길어서 programiz를 참고했다. www.programiz.com/dsa/dijkstra-algorithm Dijkstra's Algorithm It differs from the minimum spanning tree because the shortest distance between two ver..

programmers.co.kr/learn/courses/30/lessons/43236# 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 돌 사이 거리를 새로운 벡터로 만들어 문제를 풀려고 했는데 이분탐색을 적용할 방법이 떠오르지 않았다. 1. 풀이. 문제의 실마리는 돌 간 거리의 최소값을 이분탐색으로 찾아가는 것이다. 이 때 이분탐색의 기준은 돌 간 거리가 아니라 제거된 돌 개수이다. 찾는 값과 기준이 되는 값이 다르기 때문에 문제 해결이 더 어렵고, 다른 사람의 해답을 처음 봤을 때 뭔지 이해..

programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 하루 종일 붙들고 있었던 문제. 변수 타입을 int로 놓고 풀어서 삽질을 했다. long long int 타입을 사용해야 했다. while Loop를 돌면서 n과 비교하는 값인 pass도 long long 타입으로 설정해주어야 문제가 풀린다. long long 타입이 나올 때는 모든 변수를 long long으로 바꾸고 여유가 있으면 int에 맞는 값들은 바꾸어주는 것이 편할 것..