코딩기록

https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 이 문제는 첫번째 집부터 마지막 집까지 하나씩 추가하면서 최대가 될 수 있도록 값을 구하면 된다. 인접한 두 집은 털 수 없기 때문에 "현재 i번째 집 money + i-2번째 집 money" 와 "i-1번째 집 money" 중 더 큰 값을 선택하면 된다. 즉, 점화식은 dp[i] = max(dp[i-2] + money[i], dp[i-1]) 가 된다. 이 문제는..

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 이 문제는 동적계획법 문제로 왼쪽 위 집에서부터 모든 경우의 수를 계산하며 학교까지 가면 되는 문제였다. 최단 경로로 가기 위해서는 오른쪽이나 아래쪽으로만 움직여야 하므로 [i][j] 위치에 오는 방법은 [i-1][j] 에서 오른쪽으로 움직이거나 [i][j-1] 에서 아래쪽으로 움직이는 방법이다. 따라서 경우의 수를 구할 때 오른쪽이나 아래쪽만 고려해..

https://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 이 문제는 동적계획법 문제로 꼭대기부터 최대값이 될 수 있도록 업데이트하며 풀어야 하는 문제였다. 양쪽 끝인 경우에는 그 전 줄의 양쪽 끝에만 영향을 받으므로 값을 비교할 필요 없이 더해주기만 하면 된다. 가운데인 경우에는 그 전 줄의 두 값에 영향을 받으므로 값을 비교하여 더 큰 값을 더해주면 된다. 다음 예시를 보면 이해하기 더 쉬울 것이다. 예시로 이런 삼각형이 있다고 하겠다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 ..

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 이 문제의 로직은 다음과 같다. 1. 숫자 N을 사용하는 숫자당 만들 수 있는 숫자 조합을 만든다. 2. 만들어진 숫자 조합에 number이 있으면 리턴한다. 3. 만들어진 숫자 조합에 없다면 1-2번 과정을 반복한다. N이 5인 경우를 생각해보자. 숫자 5를 1번 사용할 때 5 숫자 5를 2번 사용할 때 55 (이어붙이는 경우) 5+5(10), 5-5(0), 5*5(25), 5/5(1) 숫자 5를 3번 사용할 때 555 (이어붙이는 경우) 5+55(60), 5-55(-50), 5*55(275), 5/55(1/11) 5+(5+5)(15), ..

https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 최소 카메라를 설치해야하므로 그리디 방식으로 나간 시점 기준으로 확인한다. 두 풀이 모두 진출시점 기준으로 작성된 코드이다. 첫번째 풀이 - 카메라에 걸리는지 확인하는 check 리스트를 두고 모든 구간을 검사하는 방법 def solution(routes): answer = 0 length = len(routes) check = [0] * length # 카메라에 걸리는지 확인하는 리스트 routes.sort(key = lambda x: x[1]) # 진출 시점 기준..

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]] 4 programmers.co.kr costs 리스트를 비용 기준으로 정렬해야하는 것까진 생각했는데 그 뒤로는 어떻게 접근해야할지 모르겠어서 구글링을 했다.. 구글링을 했더니 이 문제는 Kruskal 알고리즘으로 풀면 된다는 사실을 알게 되었다. Kruskal 알고리즘이 뭔지 몰라서 공부를 한 후 코드를 짰더니 수월하게 해결할 수 있었다. 이 알고리즘을 알아야 풀 수 있는 문제였다 Kruskal 알고리즘 - 탐욕적인 방법을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비..

https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 처음 생각한 문제 풀이는 people 리스트를 오름차순으로 정렬한 다음 최소값 두 개를 가져와 limit보다 크면 최소값 하나만 리스트에서 빼고 limit보다 작거나 같으면 최소값 두 개를 리스트에서 빼는 로직으로 코드를 짰다. 그런데.... 일부는 맞았지만 일부는 실패가 떴다..ㅠㅠ 질문하기를 보니 내가 생각한 로직이 틀린거 였다....

https://programmers.co.kr/learn/courses/30/lessons/42891# 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr import heapq def solution(food_times, k): if sum(food_times)

https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr def solution(number, k): num = [] for n in number: while num and n > num[-1] and k > 0: k -= 1 num.pop() num.append(n) if k != 0: num = num[:-k] return ''.join(num) 입력받은 number에서 큰 수만을 뽑아야 하므로 큰 수를 담을 num 리스트를 생성한다. for문을 통해 number배열을 돌면서 num에 큰 수만을 담는다. while문을 통해 num에 담긴 숫자보다 현재 숫자가 크면 현재 숫자보다 큰 숫자만 담..

https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 조이스틱을 움직일 때 움직인 마지막 위치에서 최소거리를 구해야하는 줄 알고 생각하다가 방법이 생각나지 않아서 다른 사람 풀이를 보려고 검색했는데 완전히 잘못 이해하고 있었다...ㅋㅋㅋㅋ 다음 위치로 넘어가면 조이스틱이 A에서 시작하는 것이었다... 이 사실을 알고 다시 생각해보았더니 방법이 생각났다 이 문제는 상하로 움직이는 로직과 좌우로 움..