1. 문제 현재 위치에서 N미터 떨어진 곳까지 물고기가 얼마나 있는지 주어진다. 정확히 M마리의 물고리를 잡고자 할 때 그물은 딱 한번 내리고 딱 한번 올릴 수 있다. 이때 정확히 M마리를 잡을 수 있는 경우의 수를 구하라. 예를 들어 5 3 7 2 1의 물고리가 존재할 때, 10마리의 물고리를 잡을 수 있는 경우의 수는 위와 같이 2가지가 존재한다. 가장 밑의 경우 떨어져있으므로 불가능한다. 2. 입력 3. 출력 가능한 경우의 수를 출력한다. 4. 알고리즘 : 투포인터 그물을 내리는 위치, 그물을 올리는 위치를 가리키는 두개의 포인터를 이용해서 구할 수 있다. 왼쪽에서 시작하기 때문에 물고기가 너무 적다면 그물을 올리는 위치를 오른쪽으로 이동하고, 물고기가 너무 많다면 그물을 내리는 위치를 오른쪽으로 ..

1. 문제 수열에 있는 연속된 원소들의 합을 이용하여 새로운 수열을 만들 수 있다. 예를 들어 1, 2, 3, 4, 5와 같은 수열이 있다고 했을 때, 1, 2를 합쳐서 3, 3, 4, 5 또는 2, 3, 4를 합쳐서 1, 9, 5를 만들 수 있다. 모든 원소를 합쳐서 15 등의 수열을 만들 수도 있다. 두 개의 수열이 주어질 때, 두 수열을 같은 수열로 만들 수 있을 때, 만들수 있는 가장 긴 같은 수열의 길이를 구하는 것이다. 2. 입력 3. 출력 두 수열을 똑같은 수열로 만들 수 있다면 그 수열의 최대 길이를, 만들 수 없다면 -1을 출력한다. 4. 알고리즘 : 그리디, 투포인터 첫번째로 두 수열의 총합이 다르다면 절대로 같은 수열로 만들 수 없다. 해당 확인이 끝났다면 투 포인터를 이용해서 원소들..

1. 문제 강의 상부와 하부를 연결하는 다리를 건설해야한다. 다리는 여러 지점으로 나눠져있고, 같은 번호의 지점끼리만 연결할 수 있다. 다리를 건설하기 위해 미리 N개의 지점을 골라두었다. 강 한쪽은 1번부터 N번까지 순서대로 지점에 번호를 매겼지만 반대쪽은 무작위로 매겨져 있다. 같은 번호의 두 지점끼리만 다리로 연결할 수 있다. 두 개의 다리는 겹칠 수(교차될 수) 없다. 주민들의 편의를 위해 다리는 최대한 많은 개수를 건설하고자 한다. 2. 입력 첫 번째 줄에는 지점의 개수 N이 주어진다. (5

1. 문제 지구를 호시탐탐노리는 아주 질나쁜 외계인들을 다 무찔러야한다. 그러기 위해서는 외계인들의 행성인 A행성의 모든 기계들을 파괴시켜야한다. A 행성에 있는 모든 기계의 위치는 N x N크기의 격자판 상에 나타낼 수 있다. 격자판 위의 모든 기계가 같은 종류의 기계라면 단 한 번의 공격으로 모든 기계를 파괴할 수 있다. 만약 격자판 위의 기계들 중 하나라도 다른 종류의 기계가 있다면, 4개의 구획으로 나누어 다시 기계를 확인한다. 모든 기계가 파괴될 때까지 2-3단계의 작업을 반복한다. 2. 입력 첫번째 줄에는 격자판 크기 N이 주어진다. 이때 N은 항상 2^k(2의 지수승) 형태이다. 두번째 줄부터 N x N 행렬에 기계번호 3이하의 자연수가 주어진다. 3. 출력 기계의 최소 공격횟수 4. 알고리..

https://swexpertacademy.com/main/learn/course/lectureVideoPlayer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 최단 경로 간선의 가중치가 있는 directed graph가 있을 때, 두 정점 사이의 경로들 중 간선의 가중치가 합이 최소인 경로 단일 시작점 최단 경로 문제 출발점에서 다른 모든 정점들에 이르는 최단경로를 구하는 문제 다익스트라 알고리즘 : 음의 가중치 허용 안함. 밸만 포드 알고리즘 : 음의 가중치 허용, 음의 사이클은 허용 안함 모든 쌍 최단 경로 문제 모든 정점 쌍 간의 최단 경로를 구하는 문제 플로이드-워샬 알고리즘 : 동적계획..

1. 크루스칼 알고리즘 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘 정점이 n개인 그래프에서 n-1개의 간선을 선택하는 방식 초기 상태는 n개의 정점들이 하나의 트리가 된다. 하나의 정점을 포함하는 n개의 상호 배타 집합이 존재 간선을 선택하면 간선의 두 정점이 속한 트리가 연결되고 하나의 집합으로 합쳐진다. 사이클이 생기면 안된다. 두 정점이 같은 집합의 원소인지 검사해야한다. 동작과정 최초, 모든 간선을 가중치에 따라 오름차순 정렬 최소 가중치 간선부터 선택하면서 트리 증가 사이클이 존재하면 다음 가중치 낮은 간선 선택 n-1개의 간선이 선택될 때 까지 (2) 반복 소스코드 # G : 그래프 def mst_kruskal(G): mst = [] # 선택된 간선 집합, 공집합으로 ..

1. 프림 알고리즘 한 정점에 연결된 간선들 중 하나씩 선택하며 최소 신장 트리를 만드는 알고리즘 임의의 정점을 하나 선택해서 시작 선택한 정점들과 인접한 정점들 중 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때 까지 (2) 반복 두 종류의 상호 배타 집합(disjoint set)이 필요 트리 정점 : 최소 신장 트리에 선택된 정점들 비트리 정점 : 선택되지 않은 정점들 소스코드 # G : 그래프 # s : 시작 정점 def mst_prim(G, s): key = [INF] * N # 가중치를 무한대로 초기화 pi = [None] * N # 트리에서 연결될 부모 정점 초기화 visited = [False] * N # 방문 여부 초기화 key[s] = 0 # 시작 정점의 가중치를 0으로 ..

1. 그래프 최소 비용 문제 : 최소 신장 트리 문제 vs 최단 경로 문제 최소 신장 트리 문제 가중치 그래프에서 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제 최단 경로 문제 시작 정점에서 목표 정점까지 가는 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제 2. 신장 트리(Spanning Tree) 정점인 n개인 undirected graph에서 n개의 정점과 n-1개의 간선으로 구성된 트리 즉, 모든 vertex set을 포함해야한다. 신장 트리의 수는 정점의 개수와 간선의 수의 비례한다. 3. 최소 신장 트리(Minimum Spanning Tree) 가중치 그래프의 신장 트리 중 간선들의 가중치의 합이 최소인 신장 트리 프림 알고리즘과 크루스칼 알고리즘이 존재한다.

1. 친구관계 A와 B는 친구를 (A - B)로 표현 2. 그래프 객체들 사이의 연결 관계 표현 정점(vertex)집합과 정점을 연결하는 간선(edge)집합으로 구성 G = (V, E) |V| : 정점 수, |E| : 간선 수 |V| = n개의 정점은 최대 C(n, 2) = n*(n-1)/2 개의 간선이 가능 3. Directed Graph vs Undirected Graph Undirected Graph 서로 대칭적이지 않은 관계 기업간의 공급관계, 작업의 선후 관계 등을 표현 4. 가중치 그래프(Weighted Graph) 간선에 비용이 추가된 그래프 5. 용어 인접(adjacency) : 두 정점 사이에 간선이 존재할 경우 인접하다고 한다. 완전 그래프 : 모든 정점이 인접한 그래프 부분 그래프 :..

1. 동전 거스름돈 총금액 800, 동전 종류 : 10, 50, 100, 400, 500 그리디 : 500, 100, 100, 100 -> 최적해가 아니다 소스코드 # coin[] : 동전의 금액을 젖아 # choice[] : 선택한 동전 집합 # best : 거스름돈에 대한 최소 동전 개수 def coinChange(choice, N, money): global best if best N best = N else: for i in range(len(coin): if money - coin[i] >= 0: choice[N] = coin[i] coinChange(choice, N+1, money-coin[i])