기록

문제https://programmers.co.kr/learn/courses/30/lessons/72412 코딩테스트 연습 - 순위 검색["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"] ["java and backend and junior and pizza 100","pytprogrammers.co.kr풀이1. 모든 경우의 수를 가지는 dict 만들기"언어 직군 경력 음식"의 형태로 된 모든..

문제https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한programmers.co.kr풀이dp에 해당 위치에서 얻을 수 있는 최대값을 저장한다.dp[i] = max(i-1번째 집을 털때 최대값, i-2번째 집과 i번째 집을 털때의 최대값) 1. -1번째, 1번째 집을 건너뛴다.2. 0번째 집을 건너 뛴다.초기 경우를 둘로 나누어서 최댓값을 구한다.코드def solution(money): answer = list() # -1번..

문제 https://programmers.co.kr/learn/courses/30/lessons/87694 코딩테스트 연습 - 아이템 줍기 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 programmers.co.kr 풀이 우선, (1) 테두리를 포함한 사각형을 1로 채운다. 그리고 (2) 사각형의 내부를 0으로 채워 가장 바깥쪽 테두리만 남긴다. 마지막으로 (3) 탐색을 통해 캐릭터와 아이템 사이의 최단 경로를 구한다. 1. 좌표를 2배로 확대 주어진 좌표에 따라 사각형을 그려보면, 좌..

문제https://programmers.co.kr/learn/courses/30/lessons/12929 코딩테스트 연습 - 올바른 괄호의 갯수올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모programmers.co.kr풀이1. 접근하기괄호쌍 2개를 이용한다고 할때, 아래와 같다.탐색하기문자열 뒤에 "("을 붙인다.올바른 괄호쌍이라면, 탐색을 계속한다. 문자열 뒤에 ")"을 붙인다.올바른 괄호쌍이라면, 탐색을 계속한다. 올바른 괄호쌍")"의 개수가 "("보다 많지 않다.2. 시간초과'('의 개수 기록하기더보기# "("의 개수를 기록하지 않음d..

문제https://programmers.co.kr/learn/courses/30/lessons/12942# 코딩테스트 연습 - 최적의 행렬 곱셈크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다. 예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 =programmers.co.kr풀이문제 접근하기행렬곱셈에는 결합법칙이 성립하므로 행렬을 곱하는 순서에 따라 곱셈의 횟수가 달라진다.dp를 사용해서 이 문제를 해결할 수 있다. 우선, N*N의 테이블을 작성한다. 테이블의 각 셀에는 아래에 해당하는 값을 적어 넣는다.dp[시작][끝] = (시작~끝) 범위에 있는 행렬을 모두 곱할 ..

문제https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4programmers.co.kr풀이신장트리모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프최소신장트리최소한의 비용으로 만들수 있는 신장트리크루스칼 알고리즘1. 간선을 비용이 적은 것부터 오름차순으로 정렬한다.2. 각 간선이 사이클을 발생시키는지 확인한다.2-1. 사이클을 발생시키지 않는다면 신장 트리에 포함한다.2-2. 사이클을 발생시키지 않는다면 신장 트리에 포함하지 않는다.풀이전체적인 틀은 dfs & bfs 와 같다.graph에 연결된 노드와 가중치를 저장한다.graph = {0..

문제https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4programmers.co.kr풀이간단한 다익스트라dfs & bfs 방식으로 각 노드를 탐색한다.중복을 체크하는 방식dfs & bfs 방식과 이 부분만 다르다지금의 방식이 이전보다 비용이 적게 들때만 탐색을 계속한다.개선된 다익스트라간단한 다익스트라에 탐색할 노드를 선정하는 방식이 개선되었다.최소 heap을 사용하여 가장 적은 비용이 드는 노드부터 검증한다.플로이드 워..

문제https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한programmers.co.kr풀이각 leaf node에서 가중치를 부모 노드로 옮긴다.이 과정을 leaf 노드가 사라질 때까지 반복한다. 시간초과dfs 나 bfs를 이용해서 모든 노드를 탐색하도록 했으나, 시간초과로 대부분의 테스트 케이스에서 통과하지 못했다. leaf node를 제거하면, 그 부모가 leaf node 후보가 되므로, 부모가 가진 간선개수를 이용해서 다음에 ..