STUDY PAGE

q1) 플로이드 n개의 도시가 있고, 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있다 각 버스는 한번 사용할 때 필요한 비용이 있다 모든 도시의 쌍 (A,B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구해라 - 첫째줄에 도시의 개수 n - 둘째줄에 버스의 개수 m - 셋째줄부터 m+2까지 버스정보 (위에 두줄이 도시와 버스 갯수 이므로 +2를해야 m개가 됨) INF=int(1e9) n= int(input()) m= int(input()) graph= [[INF]*(n+1) for _ in range(n+1)] for a in range(1, n+1): for b in range(1, n+1): if a == b: graph[a][b]=0 for _ in range(m): a..

코딩테스트 연습 2022. 8. 3. 14:15

1. 최단 경로 알고리즘 - 그래프상에서 가장 짧은 경로를 찾는 알고리즘 - 다익스트라 알고리즘과 플로이드 워셜 알고리즘을 성능, 구현 난이도, 역할에 대하여 비교하면 다음과 같다 알고리즘 종류 시간 복잡도 구현 난이도 역할 다익스트라 O(ElogV) 어려운 편 한 지점에서 다른 모든 지점까지의 최단 경로를 계산한다 플로이드 워셜 O(V³) 쉬운 편 모든 지점에서 다른 모든 지점까지의 최단 경로를 계산한다 2. 다익스트라 알고리즘 - 단계마다 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택한 뒤에, 그 노드를 거쳐 가는 경우 확인하여 최단 거리를 갱신하는 방법 - 우선순위 큐를 이용하여 소스코드를 작성할 수 있다 3. 플로이드 워셜 알고리즘 - 다이나믹 프로그래밍을 이용하여 단계마다 거쳐 ..

코딩테스트 연습 2022. 8. 1. 11:48

q5) 병사 배치하기 - N명의 병사가 무작위로 나열되어있다 각 병사는 특정한 값의 전투력을 보유하고 있다 - 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치하고자 한다 다시말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야한다 - 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다 그러면서도 남아 있는 병사의 수가 최대가 되도록 하고싶다 ed) 예를들어, N = 7일 때 나열된 병사들의 전투력이 다음과 같다고 가정 - 이때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아 있는 병사의 수가 내림차순의 형태가 되어 5명이 된다 이는 남아 있는 병사의 수가 최대가 되도록 하는 방법이다 - 병사에 대한 정보가 주어 졌을 때, 남아 있는 병..

코딩테스트 연습 2022. 7. 27. 11:31

q4) 금광 - n * m 크기의 금광이 있다 금광은 1 * 1크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다 - 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작, 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다 이후에 m -1번에 걸쳐 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기 출력 조건) 첫째 줄이 테스트 케이스 T가 입력된다 매 테스트케이스 다음줄에 n과 m이 공백으로 구분되어 입력 되어야 한다 그 다음 금의 크기를 공백으로 구분하여 입력 ex) 2 케이스 수 3 4 첫번째 케이스 3 * 4크기 1 3 3 2 2 1 4 1 9 6 4 7 4 4 두번째 케이스 4 * 4 크기 1 ..

코딩테스트 연습 2022. 7. 27. 00:34

q3) 효율적인 화폐 구성 - N가지 종류의 화폐가 있다 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다 이때 각 종류의 화폐는 몇 개라도 사용할 수 있다. - 예를들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다 - M원을 만들기 위한 최소한의 화폐 개수를 출력 ex) N가지 화폐의 N을 2로 M원이 되도록의 M을 15로 그리고 화폐의 단위는 2, 3으로 입력 받았을때의 예시로 보면 2 15 2 3 에서 출력은 5가 된다 하지만 여기서 문제조건에 또 다른 경우의 수를 두었다 불가능 할 때는 -1을 출력 이라는 조건이 붙었다! 이 점을 유념하자 - a¡ = 금액 i를 만들 수 있는 최소한의 화폐 개수 ..

코딩테스트 연습 2022. 7. 26. 22:18

q2) 1로 만들기 - 정수 X가 주어졌을 때, 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지다 1. X가 5로 나누어 떨어지면, 5로 나눈다 2. X가 3으로 나누어 떨어지면, 3으로 나눈다 3. X가 2로 나누어 떨어지면, 2로 나눈다 4. X에서 1을 뺀다 - 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 값을 1로 만들고자 한다 연산을 사용하는 횟수의 최솟값을 출력해라 예를들어 정수가 26이면 26 -> 25 -> 5 -> 1 ex) 피보나치 수열 문제를 도식화한 것처럼 함수가 호출되는 과정을 그림으로 그려보면 다음과 같다 - 최적 부분 구조와 중복되는 부분 문제를 만족한다 - 26 나누기 5 = 5.2가 된다 여기서는 다음 연산을 수행해도 1로 만들 수 없기 때문에 5는 제외하고 ..

코딩테스트 연습 2022. 7. 26. 20:53

q1) 개미 전사 - 개미 전사는 부족한 식량을 충당하고자 식량창고를 몰래 공격하려한다 여러개의 식량 창고가 있는데 식량 창고는 일직선으로 이어져 있다 - 각 식량 창고에는 정해진 수 의 식량을 저장하고 있으며 개미전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다 이 때 식량창고 중에서 서로 인접한 식량창고가 공격받으면 메뚜기 정찰병들에게 들킬 수 있다 - 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위한 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다 ex) [1, 3, 1, 5] - 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택 했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다 개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻길 원한다 - ..

코딩테스트 연습 2022. 7. 25. 21:38

다이나믹 프로그래밍 - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록한다 - 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성 - 다이나믹 프로그래밍은 동적 게획법이라고 부른다 - 일반적인 프로그래밍 분야에서 동적(Dynamic)이란? - 자료구조에서 동적 할당 (Dynamic Allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 - 반면 다이나믹 프로그래밍에서 '다이나믹'은 별다른 없이 없음 다이나믹 프로그래밍의 조건 - 다음 조건을 만족할 때 사용할 수 있다 1. 최적 부분 구조(Optimal Substructure) - 큰 ..

코딩테스트 연습 2022. 7. 25. 13:23