Chapter 03 - 그리디(Greedy) 1. 그리디 알고리즘(=탐욕법) : 현재 상황에서 지금 당장 좋은 것 만 고르는 방법 👉 매 순간 좋아 보이는 것만 선택 👉 현재의 선택이 나중에 미칠 영향에 대해 고려X 예제 3-1 ) 거스름돈(C++) Q . 손님에게 거슬러야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수? (동전은 500원, 100원, 50원, 10원이 있다) > 가장 큰 화폐 단위부터 돈을 거슬러 줘야 함 #include using namespace std; int n;//손님에게 받은 돈 int coin[4] = { 500, 100, 50, 10 }; int ans; //거스름돈의 개수 int main() { cin >> n; for (int i = 0; i < 4; i++) ..
알고리즘
11724번: 연결 요소의 개수 (acmicpc.net) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 난이도 : 실버2 문제 설명 : 연결 요소란, 무방향 그래프에서 적어도 한 개 이상의 경로로 연결된 정점들로 구성된 종속 그래프를 이야기합니다. 예를 들어, 아래와 같은 그림이 있을 때, 연결 요소의 개수는 2개입니다. (각각의 떨어져 있는 그래프가 2개!) 풀이 과정 : DFS나 BFS로 풀 수있는 문제입니다. 이 문제를 풀기 전에 dfs와 b..
8958번: OX퀴즈 (acmicpc.net) 8958번: OX퀴즈 "OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수 www.acmicpc.net 난이도 : 브론즈2 과정 : 연속된 O의 개수들을 더하는 문제였습니다. 연속된 O의 개수를 담는 변수 CNT와, CNT를 더하는 ANS 변수를 선언하여 반복문을 이용해 답을 구하였습니다. #include #include using namespace std; int n; int main() { cin >> n; string arr; for (int i = 0; i > ..
1. 정렬 알고리즘 - 정렬알고리즘은 알고리즘 중에 가장 기본적인 알고리즘 이다. - 이 글에서 살펴볼 알고리즘은 삽입, 선택, 거품(버블), 퀵, 합병(merge), 힙, 이진탐색 트리를 이용한 정렬이다. 1) 삽입정렬 - O(n^2) - 배열의 모든 원소를 앞에서부터 차례대로 배열 부분과 비교하여, 삽입함으로써 정렬하는 알고리즘 - 처음 key 값(처음으로 뽑아 비교할 원소)은 두번째 원소이다 > 과정 두번째 원소 10을 뽑아 첫번째 원소와 비교하여 29보다 작으므로 29왼쪽으로 삽입된다. 세번째 원소 14를 뽑아 두번째 원소와 비교하여 29보다 작으므로 29왼쪽으로 삽입된다. 14는 10보다 크므로 바뀌지 않는다. 네번째 원소 37를 뽑아 세번째 원소인 29와 비교한다. 37이 29보다 크므로 바뀌..
1. 문제 * 길이가 n인 배열 A[0], A[1], ..., A[n-1] 이 입력으로 주어 질때, i번째부터 j번째까지 원소드로 이루어진 배열 A[i], ..., A[j] 를 부분배열이라고 하고, A[i, j] 로 나타낸다. - 부분 배열의 속한 원소들의 합이 최대가 되는 부분 배열을 구하는 것이 이 문제의 목적이다. 이 때 길이가 0인 부분배열도 허용하며, 이 부분배열의 원소들의 합은 0이라고 정의한다. 예를 들어, 아래와 같은 배열이 있다면, -2 -1 3 5 2 -5 0 2 이 배열의 최대부분배열의 합은 몇일까? 3+5+2 = 10 이다. 2. 해결방법 - 최대부분배열의 원소합을 구하는 알고리즘에는 크게 4개가 있다. - 완전탐색, 중복제거한 탐색, 분할정복법, 동적계획법 1) 완전탐색(브루트포스..
1. BFS란? - BFS 는 너비우선탐색을 말합니다. - 루트 노드에서 시작하여 인접한 노드를 탐색하는 방법입니다. Q. 너비우선 탐색을 하면 순서가 어떻게 될까요? A. 0 - 1 - 2 - 3 - 4 - 5 -6 1) 특징 - 두 노드사이의 최단 경로를 찾을 때, 임의의 경로를 찾을 때 사용 - 코드가 DFS보단 복잡하지만 속도는 더 빠르다 2) 알고리즘 구현 방법 BFS의 결과 : 1 - 2 - 6 - 3 - 4 -5 - 큐를 이용하여 구현함 void bfs(int st) { q.push(st); visited1[st] = 1; while (!q.empty()) { int now = q.front(); q.pop(); printf("%d ", now); for (int i = 0; i < adj[..
1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 난이도 : 실버2 풀이과정 : DFS는 재귀함수를 이용해서 풀었습니다 [Algorithm] DFS 정리 (tistory.com)
1. DFS란? - DFS 는 깊이 우선 탐색 을 말합니다. - 루트 노드에서 시작하여, 해당 노드들의 자식을 우선적으로 탐색합니다. * 미로찾기로 예시를 들면, 한 방향으로 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게 되면 다시 가까운 갈림길로 되돌아 와서 다시 탐색을 진행하는 것과 유사합니다. Q. 깊이우선 탐색을 하면 순서가 어떻게 될까요? A. 0-1-3-4-2-5-6 1) 특징 > 모든 노드를 탐색할 때 좋은 방법입니다. > BFS보다 좀 더 간단하지만 느립니다. 2) 알고리즘 구현 방법 DFS의 결과 : 1 - 2 - 3 - 5 - 4 -6 ⓐ 재귀함수 이용 #include #include using namespace std; bool visited[10]; //방문했던 노드를 기억하는..
