갬미의 성장일기

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 9 최단경로 알고리즘 오늘 풀이한 문제 - 최단경로 알고리즘 예제 [이코테 259p] 미래도시 문제 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다. 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 공중 미래 도시에서 특정 회사와 다른 회사가 도로로 연결되어 있다면, 정확히 1만큼의 시간으로 이동할 수 있다. 또한 오늘 방문 판매원 A는 기대하던 소개팅..

주피터에서 다음 소스코드를 입력하면 아래와 같은 오류가 발생한다 import sys input = sys.stdin.readline n, m = map(int,input().split()) --------------------------------------------------------------------------- ValueError Traceback (most recent call last) in 2 3 input = sys.stdin.readline ----> 4 n, m = map(int,input().split()) ValueError: not enough values to unpack (expected 2, got 0) 대체 뭐가 문제냐 ~ 했는데 sys를 import하지 않으면 해결된..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. 오늘은 아래 첨부된 저자의 동영상 강의를 듣고 글을 작성하였습니다 Chapter 9 최단경로 알고리즘 최단 경로 : 말 그대로 가장 짧은 경로를 찾는 알고리즘, "길 찾기" 문제라고도 불린다 문제 상황 유형 한 지점에서 다른 한 지점까지의 최단경로 한 지점에서 다른 모든 지점까지의 최단경로 모든 지점에서 다른 모든 지점까지의 최단경로 각 지점은 그래프에서 노드로 표현 각 지점을 연결하는 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘이 많이 등장 하는 유형이다 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 음의 간선이 없을때 정상적..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 8 다이나믹 프로그래밍 오늘 풀이한 문제 - 다이나믹 프로그래밍 예제 [이코테 381p] 못생긴 수 문제 못생긴 수란 오직 2,3,5만을 소인수로 가지는 수를 의미합니다. 다시 말해, 오직 2,3,5를 약수로 가지는 합성수를 의미합니다. 1은 못생긴수라고 가정합니다. 따라서 못생긴 수들은 {1,2,3,4,5,6,8,9,10,12,15...}순으로 이어집니다. 이때 n번째 못생긴수를 찾는 프로그램을 작성하세요 입력 조건 1

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 8 다이나믹 프로그래밍 오늘 풀이한 문제 - 다이나믹 프로그래밍 예제 [이코테 375p] 금광 문제 n × m 크기의 금광이 있다. 금광은 1 × 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하라 접근 방법 드디어 혼자 점화식을 세워보았다 현재 위치에 있을때, 얻을수 있는 최대 금의..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 8 다이나믹 프로그래밍 오늘 풀이한 문제 - 다이나믹 프로그래밍 예제 [이코테 226p] 효율적인 화폐구성 문제 N가지 종류의 화폐가 있을 때, 이 화폐들의 개수를 최소한으로 이용해 그 가치의 합이 M원이 되도록 하여라.각 화폐는 몇 개라도 사용할 수 있고, 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 접근 방법 만약 m = 7, 주어진 화폐가 2,3이라고 하면 7 -> 4+3 -> 2+2+3 이런식으로 쪼개질 수 있다 = DP로 풀이할 수 있다 화폐 사용 횟수 저장 리스트 = a (큰값으로 초기화) m에서 각 화폐를 따지면서 업데이트 할 수 있는 최솟값을 a에 업데이트 한다 점화식은 다음과 같..