시냅스

플로이드 알고리즘 Floyd algorithm 모든 지점에서 모든 지점으로의 최단 경로를 모두 구하는 경우 꼭짓점 k를 두고, k를 경유할 경우를 원래의 값과 비교하여 더 짧다면 업데이트 한다. (i,j) > (i,k) + (k,j) 와 같은 꼴이다. 다이나믹 프로그래밍 기술에 의거한다. 구현이 쉽고 간단하지만 O(n^3) 시간복잡도가 높다. 구현 int INF = 99999999; int **arr_init(LinkedGraph *graph) { int **arr = calloc(graph->currentVertexCount, sizeof(int *)); ListNode *temp; for(int i = 0; i currentVertexCount; i++) arr[i] = calloc(..

다익스트라 알고리즘 Dijkstra algorithm 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 방식 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법 다익스트라 알고리즘은 너비우선탐색(BFS)와 유사 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트 다익스트라 알고리즘의 다양한 변형 로직이 있지만, 가장 개선된 우선순위 큐를 사용하는 방식을 소개 구현 방식 우선순위 큐는 MinHeap 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨 1) 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정..

프림 알고리즘 Prim algorithm 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 Kruskal's algorithm 과 Prim's algorithm 비교 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 MST를 구함 Prim's algorithm은 특정 정점에서 시작, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중..

크루스칼 알고리즘 Kruskal algorithm 모든 정점을 독립적인 집합으로 만든다. 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다. 두 정점 사이 사이클이 발생하지 않으면(DFS) 정점을 연결한다. 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) c언어로 구현 간선 가중치를 최소 값으로 오름차순 정렬 dfs를 통해 사이클을 갖고 있는지 확인 Heap *sorted_heap(LinkedGraph *graph) // 간선의 가중치를 기준으로 최소로 정렬한다. // 여기에선 key가 가중치가 된다. { Heap *temp = createHeap(graph->currentEdgeCount); ListNod..

https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 백트래킹을 이용하여 풀었다. 부등호들은 brackets라는 배열로 관리하였고, dfs로 체크하는 동안 check_up이라는 함수를 통해 부등호가 만족하는지 확인하였고, 만족하는 것들은 배열에 담아두었다가 dfs가 끝나면 맨 처음 것과, 마지막 것을 출력해주었다. code n = int(input()) brackets = list(input().split()) visited = [0] * 10 ans = [] ..

https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 브루트포스와 백트래킹을 활용하여 풀었다. 가능한 조합을 모두 뽑아줘야 했지만, 시간제약의 관계로 dfs를 돌릴 때 for문을 쓰지 않는 방법으로 접근하였다. 조합을 뽑아 냈으면 start와 link로 나눠 차이를 구하고, 최소값을 갱신해줬다. code n = int(input()) stats = [list(map(int, input().split()))..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 다이나믹 프로그래밍을 통해 해결하였다. 다만, 문제를 풀면서 고려해야할 조건이 2가지인데, 최대값과 일자를 고려하여야 했다. 주어지는 일자를 넘어가면 안 되는데, 이를 위해 for문을 역순으로 돌렸다. 값을 구할 때에 뒤에서부터 더해질 수 있는 최대값을 구해나가고, 일자를 벗어난다면 전의 결과를 저장함으로써 0번째 인덱스에 최대값을 도출할 수 있게 했다. code total = int(input()) days =[] cost = [] dp = [] for i in range(total): n, m = map(int, input().s..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹을 이용한 문제였다. 주어지는 6개의 문자 중에 4개를 뽑아 조합해야 하는데, 문자 4개 중 최소 2개는 자음, 1개는 모음이 되어야 한다. 백트래킹을 통해 모든 가능성을 체크하면서, 모음을 포함하는지에 대한 여부와 자음을 2개 이상 포함하는지에 대한 여부를 함수로 판단하였고, 위 조건에 만족되는 경우에만 출력 할 수 있게 해주었다. code vowel = ['a', 'e', 'i', 'o', ..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹을 이용하는 기본 문제였다. 다만, 중복에 관한 제약조건들이 있었는데 자기 자신을 출력하면 안되고, 이미 출력한 조합은 다시 출력해서는 안 된다. 자기 자신에 대한 여부는 visited 라는 배열로 관리하였고, 이미 출력한 것에 대한 여부는 printed 라는 배열을 통해 출력한 것들을 저장하여 비교해주었다. code n, m = map(int,input().split()) input_l..

https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 이어서 쓰인 수의 length 값을 구하는 문제였다. 물론, 시간초과를 한 번 맛본 후 반복문을 쓰지 말아야겠다 하고 생각했던 풀이법은 한자리 수인, 1 ~ 9 의 총 합은 9 두자리 수 까지인, 1 ~ 99 의 총 합은 189 세자리 수 까지인, 1 ~ 999 의 총 합은 2889 로 규칙성을 찾아 내었다. 이후에는 각 자리수의 총합에서 입력받은 수 까지의 차이를 빼 결과값을 나타내었다. code n = input() every_nineth = str(len(n) - 1) + ('8' * (len(n) - 1)) ..