본문 바로가기
반응형

전체 글1306

다익스트라 (Dijkstra) 개념 다익스트라 알고리즘은 Single Source shortest path problem으로 하나의 정점에서 다른 모든 정점까지 최단 경로를 구할 때 주로 사용됩니다. 이때, 간선의 가중치는 only 양수가 전제조건입니다. (음의 가중치 X) 실제, 현실 세계에서는 음의 가중치는 일반적이지 않기에 현실에 적합한 알고리즘이라고 볼 수 있습니다. 시뮬레이션 그래프를 인접행렬로 표현 ▶ dist[] 배열 초기화 ※ 시작 정점 = [5] 가정. ← 방문 표시 - 정점 [5]와 연결된 정점 [2], [4]와 정점 [5] 자체에 대한 dist[] 초기화 ▶ 방문하지 않은 정점 가장 비용이 적은 정점 [4] 선택 ← 방문 표시 [4]번 정점과 연결되었으면서 동시에 아직 한번도 방문하지 않은 정점 [2], [3]에 .. 2021. 2. 25.
그래프 정의 및 구현 방식 (인접 행렬 & 인접 리스트) 그래프는 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 정점을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조로 객체들의 상호 관계를 표현하기 위해 고안된 자료 구조입니다. 여러 도시들을 연결하는 도로망, 사람들 간의 지인 관계, 웹사이트 간의 링크 관계 등이 우리 주변에서 찾을 수 있는 연결 구조의 예라고 할 수 있습니다. 여러 객체들이 서로 연결되어 있다는 점에서 그래프는 트리와 별로 다를 것이 없습니다. 그래프 표현 ▶ 인접리스트와 인접행렬 메모리 or 시간 사용 특성이 굉장히 다르기 때문에, 적절한 표현 방식 선택 인접리스트(adjacency list) - 각 정점마다 하나의 연결 리스트를 갖는 방식 |V|개의 연결 리스트에 실제 간선 수만큼의 원소가 들어.. 2021. 2. 25.
그래프 표현 (인접 리스트 / 인접 행렬) 정점 u - v 간 간선 여부 확인 - 인접 리스트는 adList[u]의 처음부터 읽어나가면서 각 원소를 일일이 확인 - 인접 행렬은은 정점 u, v가 주어졌을 때, 단 한 번의 배열의 접근으로 연결 여부 확인 공간 복잡도 - 인접행렬: V × V 개수 만큼 공간 필요 - 인접리스트: 정점 개수 V와 실제 간선의 개수 E에 좌우 (V + E) (만약 간선의 개수가 V에 수렵한다면 인접행렬 비슷한 공간복잡도를 가짐) 결론 - 간선의 수가 V2에 비해 훨씬 적은 그래프를 희소 그래프 → 인접 리스트 - 간선의 수가 V2에 비례하는 그래프를 밀접 그래프 → 인접 행렬 방향성 그래프 (인접 리스트) import java.util.ArrayList; import java.util.Iterator; import j.. 2021. 2. 25.
[BOJ] 백준 3006 터보소트 출처: https://www.acmicpc.net/problem/3006 Input 3 2 1 3 Output 1 0 0 ① 1의 교환횟수 arr = [5 4 3 7 1 2 6] tree = [1 1 1 1 1 1 1] ← 단말 노드만 표시 Bubble Sort와 같이 교환(swap)하기 때문에 결국, 『1』 앞에 몇개의 숫자가 존재하는지 필요합니다. 세그먼트 트리에서 첫번째 부터 현재 숫자 『1』 앞 위치까지의 구간 합이 필요합니다. → [1, pos[1]-1] = [1, 4] = 4 『1』은 이동하였기 때문에 『0』으로 표시하면 다음 구간합을 구할 때 제외처리 할 수 있습니다. ② 7의 교환횟수 arr = [5 4 3 7 1 2 6] tree = [1 1 1 1 0 1 1] ← 단말 노드만 표시 『7.. 2021. 2. 25.
[BOJ] 백준 11053 가장 긴 증가하는 부분 수열 출처: https://www.acmicpc.net/problem/11053 Input 6 10 20 10 30 20 50 Output 4 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com LIS (Longest Increasing Subsequence) subsequence은 연속하지 않아도 되는 부분 수열입니다. 따라서 subsequence의 개수는 N2 입니다. 완전 탐색 방법으로 접근할 경우 T.. 2021. 2. 25.
[BOJ] 백준 12015 가장 긴 증가하는 부분 수열 2 출처: https://www.acmicpc.net/problem/12015 Input 6 10 20 10 30 20 50 Output 4 [BOJ] 11053 가장 긴 증가하는 부분 수열 제의 경우는 N이 최대 1000이기 때문에 DP로 해결가능하였지만 N의 최대 크기가 증가하였기에 구간의 최대값을 가지는 세그먼트 트리 이용 DP에서는 i 번째 숫자가 입력될 때, 0 ~ i-1번째 숫자 중에서 자기보다 작은 j번째 숫자를 찾아 DP[j]의 최대값을 구하는 것이었습니다. 세그먼트 트리에서는 i 번째 숫자 입력될 때, DP[j]의 최대값을 for문으로 탐색하지 않고 구간의 최대값 세그먼트 트리를 이용하는 것입니다. 즉, tree[]의 단말 노드에는 i번째가 숫자가 입력되었을 때, 0 ~ i-1까지 최대값 +.. 2021. 2. 25.
[BOJ] 백준 2792 보석상자 출처: https://www.acmicpc.net/problem/2792 Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com [탐색] Parametric Search [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 경우가 많습니다... 2021. 2. 25.
[BOJ] 백준 2983 개구리 공주 출처: https://www.acmicpc.net/problem/2983 Input 7 5 ACDBB 5 6 8 9 4 13 1 10 7 4 10 9 3 7 Output 7 4 식물들의 위치는 아래와 같습니다. [Jungol] 1889 N Queen 문제에서도 이용했지만 [Jungol] 정올 1889 N Queen 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1162 Input 4 Output 2 N이 4일 때, 나오는 경우는 두 가지이다. 한 행에 놓을 수 있는 여왕말의 개수는 1개 입니다. 그렇기 때문에 행.. zoosso.tistory.com 2차원 평면에서 같은 선상의 대각선상에 위치한 것은 아래와 같이 알 수 있습니다. ▶ (x.. 2021. 2. 25.
[BOJ] 백준 3217 malloc 출처: https://www.acmicpc.net/problem/3217 Input 5 baka=malloc(214); baka=malloc(123); free(baka); deda=malloc(100); print(deda); Output 215 주어지는 명령에서 변수는 항상 4글자 소문자 이므로 특정 위치의 문자를 확인해서 명령이 무엇인지 확인할 수 있습니다. (모든 명령은 최소 6글자 이상을 보장합니다.) - 5번째 글자가 『 = 』 → xxxx=malloc(size); - 5번째 글자가 『 ( 』 → free(var); - 6번째 글자가 『 ( 』 → print(var); - 시작 번호와 할당가능한 크기를 나타내는 free block - 각 변수에 할당된 메모리 (시작 번호 + 할당된 크기) (변.. 2021. 2. 25.
[BOJ] 백준 1238 파티 출처: https://www.acmicpc.net/problem/1238 Input 4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3 Output 10 다른 정점들로부터 특정 정점까지의 최단 거리 비용을 구해야 하므로 플로이드 와샬 (Floyd Warshall) 플로이드 와샬 (Floyd Warshall) 개념 아래와 같은 가중 그래프에서 최단 경로를 찾는 알고리즘. ex) 정점 ③ → ⑤로 가는 최단 경로는 다음과 같습니다. 경로Path: ③ → ② → ④ → ① → ⑤ 비용Cost: +4 +1 +2 -4 = 3.. zoosso.tistory.com 같은 내용의 문제이지만, 다익스트라 알고리즘을 이용해서 풀이 [SWEA] 4007 간담회 참석 [SWEA] .. 2021. 2. 25.
반응형

티스토리툴바