분류 전체보기73

• 

  [백준] 5719번 : 거의 최단 경로 - 다익스트라 알고리즘 5719번: 거의 최단 경로 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. .. PS/최단경로 2022. 7. 27.

• 2022년 07월 26일 (화요일) 일지 보호되어 있는 글 입니다. 2022. 7. 27.

• 2022년 07월 25일 (월요일) 일지 보호되어 있는 글 입니다. 2022. 7. 27.

• 2022년 07월 24일 (일요일) 일지 보호되어 있는 글 입니다. 2022. 7. 27.

• [알고리즘 특강 6일차] 서로소 집합, 위상정렬, 최소 신장 트리, 최소 공통 조상 (Disjoint Set, Union-Find, DAG; Directed Acyclic Graph, Topological Sort, MST; Minimum Spanning Tree, Kruskal, Prim, LCA; Lowest Common Ancestor) 최소 신장 트리 (MST; Minimum Spanning Tree) 트리란? (Tree) 무향 그래프 G가 순환 없는 연결 그래프이면 G는 트리입니다. 숲이란? (Forest) 무향 그래프 G가 순환이 없는 그래프이면 G는 숲입니다. 신장 트리란? (Spanning Tree) 무향 연결 그래프 G의 부분그래프이며, G의 모든 정점을 포함 트리인 그래프입니다. 무향 연결 가중 그래프 S에서 간선의 가중치의 합이 최소인 신장 트리 (Spanning Tree) 입니다. 때문에 최소 신장 트리의 답은 여러 개가 될 수 있습니다. 신장 트리 탐색 종류 DFS Spanning Tree BFS Spanning Tree 크루스칼 알고리즘 (Kruskal) 프림 알고리즘 (Prim) 크루스칼 알고리즘 (Kruskal) .. CS/알고리즘, 자료구조 2022. 7. 25.

• [알고리즘 특강 4일차] 확장 유클리드 호제법, 베주 항등식, 에라토스테네스의 체 알고리즘 특강을 들으면서 인상 깊었던 내용을 정리합니다. 자세한 개념보다는 알고리즘의 '이해' 그리고 '활용'(팁)에 중점을 두었습니다. 내용이 이상하다면 지적해주시면 감사하겠습니다. 👍 벌써 알고리즘 특강 4일차 입니다. 정수론에 대해서 배웠는데 소수와 최대공약수와 관련된 알고리즘 이었습니다. 유클리드 호제법 유클리드 호제법은 2개의 자연수의 최대 공약수를 구하는 알고리즘 입니다. 두 개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다 성질을 이용합니다. 이제부터 자연수 a, b의 최대공약수를 gcd(a, b)라고 하겠습니다. (단, a > b) 그렇다면 gcd(a ,b)는 어떤 식으로 찾아지는 걸까요? (a % b) = ? 60 %.. CS/알고리즘, 자료구조 2022. 7. 24.

• 

  [백준, Java] 7453번 - 합이 0인 네 정수 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 문제 접근 A[a] + B[b] + C[c] + D[d] = 0 이 성립하는 {a, b, c, d}의 개수를 구하라. 첫 번째 방법입니다. 위와 같이 무작정 더하는 방법인데 O(n^4)는 좀 아니지 않나 싶습니다. 두 번째 방법입니다. 이번에는 이분 탐색 방법.. PS/백준 2022. 7. 24.

• 2022년 07월 22일 (금요일) 일지 보호되어 있는 글 입니다. 2022. 7. 22.

• 2022년 07월 21일 (목요일) 일지 보호되어 있는 글 입니다. 2022. 7. 22.

• 

  [알고리즘 특강 3일차] 인덱스 트리 (indexed tree, 이진 트리 응용) 알고리즘 특강을 들으면서 인상 깊었던 내용을 정리합니다. 자세한 개념보다는 알고리즘의 '이해' 그리고 '활용'(팁)에 중점을 두었습니다. 내용이 이상하다면 지적해주시면 감사하겠습니다. 👍 벌써 알고리즘 특강 3일차 입니다. 오늘 계속 조금씩 뭔가 빼먹으면서 문제를 풀었기에 틀릴 때가 많았습니다. 먼저 오늘 배웠던 것 중에 가장 어렵다고 느껴졌던 인덱스 트리에 대해 알아보겠습니다. 인덱스 트리 사용 이유 먼저 인덱스 트리를 사용하는 이유에 대해 알아보겠습니다. 한 개발자가 와서 저한테 이런 문제를 줬습니다. 이 배열 안에 있는 연속되는 숫자의 합을 구하는 프로그램을 구현해줘 😃 저는 여느때와 다름 없이 배열을 초기화여 입력값을 받고 숫자를 더할 배열를 범위를 입력받고 더했습니다. for (int idx =.. CS/알고리즘, 자료구조 2022. 7. 20.

• 2022년 07월 20일 (수요일) 일지 보호되어 있는 글 입니다. 2022. 7. 20.

• 2022년 07월 19일 (화요일) 일지 보호되어 있는 글 입니다. 2022. 7. 20.