일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 종만북
- 완전탐색
- 그리디
- DP
- 문자열
- 스택
- 백트래킹
- 알고리즘문제해결전략
- 재귀
- stack
- 다이나믹프로그래밍
- priority_queue
- 백준
- union-find
- 동적계획법
- 너비우선탐색
- acm
- 세그먼트트리
- Greedy
- 유니온파인드
- backtracking
- DFS
- 분리집합
- 이분탐색
- BOJ
- 누적합
- 분할정복
- 알고스팟
- BFS
- Algospot
- Today
- Total
목록분류 전체보기 (105)
DAMPER's 낙서장
www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 딱 실버 분할정복 문제. '-'만 \( 3^{N} \)개 있는 문자열을 3등분으로 나누어 가운데 부분은 공백(space)로 바꾸고 왼쪽, 오른쪽은 다시 같은 작업을 반복하는 문제. 다음 그림과 같이 (부분)문자열의 첫번째 인덱스를 start로 하고, 3등분한 문자열의 오른쪽 부분의 첫번째 인덱스를 end 라고 하자. size를 3등분된 문자열의 크기라고 할 때, end = start+size+size 라고 할 ..
저번 글까지는 맛보기였고 지금부터가 진짜입니다. 이번 시간에 진행할 내용은 재귀함수 입니다. 재귀함수는 알고리즘에 있어서 매우매우 중요합니다. 여러 알고리즘들이 재귀함수를 베이스로 가지고 있기도 하고, 재귀 함수 대한 이해 없이는 진행할 수 없는 알고리즘도 수없이 많습니다. 재귀함수는 자기 자신을 호출하는 함수입니다. 반복문을 사용하는 코드는 항상 재귀함수를 통해 구현이 가능합니다.(물론 그 반대도 가능합니다.) 우리가 어떤 문제를 재귀함수로 푼다는 것은, 귀납적인 방법으로 문제를 푼다는 뜻입니다. 수학적 귀납법을 생각해보면 1. 기본 가정 2. 귀납 가정 3. 귀납 증명 이 세가지 단계를 통해 우리는 귀납적으로 증명할 수 있습니다. 예를 들어, \( 1+3+5+ ... + (2n-1) = n^{2} \..
이번 시간에 다뤄볼 알고리즘은 저번 시간에 이어 기본 정렬 알고리즘인 Bubble Sort 입니다. Bubble Sort는 Selection Sort와 함께 가장 기본적인 정렬 알고리즘에 속합니다. Bubble Sort의 동작 과정 1. 첫번째 수 부터 N-1 번째 수 까지 가면서 해당 수와 바로 다음 수를 비교한다. 2. 해당 수 보다 바로 다음 수가 더 작다면, 둘의 자리를 바꿔 큰 수가 뒤에 오도록 한다. 3. N번째 수에 도달하게 되면 그 자리에는 가장 큰 수가 오게된다. 4. 1~3 과정을 N-2번째 수 까지, N-3번째 수까지 ... ... 첫번째 수 까지 하게되면 모든 수가 오름차순으로 정렬된다. 1, 2, 3번과정을 수행하면 다음과 같이 진행됩니다. 여기서 초록색 부분은 현재까지 정렬된 구..
이번 시간에는 기본적인 정렬 알고리즘을 배울겁니다. 정렬 알고리즘은 정말 여러가지 있지만 오늘 다뤄볼 정렬은 Selection Sort (선택정렬) 입니다. 첫 시간이기에 쉬운 정렬 알고리즘을 다룹니다. 정수를 오름차순으로 정렬하므로 내림차순이나 다른 특정한 순서로 정렬하고 싶으면 조건을 바꾸시면 됩니다. 먼저 Selection Sort 입니다. Selection Sort 는 \( n \) 개의 수 중에 가장 작은 수를 찾아(혹은 가장 큰 수를 찾아) 아직 정렬되지 않은 부분의 맨 앞자리에 위치시키는 방법으로 정렬을 수행합니다. 위와 같이 정렬을 하고자 할 때, 1. 5, 1, 3, 4, 2 를 모두 확인하면서 가장 작은 수를 찾습니다. -> 이 때 가장 작은 수는 1 입니다. 2. 그럼 이 1과, 현재..
전북대학교 알고리즘 동아리 'COALA'에서 진행하는 기초 알고리즘 튜터링 내용을 기록합니다. 이 튜터링을 진행하기에 앞서 필요한 지식은 다음과 같습니다. 1. C/C++ 기본 문법에 대해 알고 있어야합니다. 2. 함수 사용 및 재귀함수가 무엇인지 알고 있어야 합니다. 알고리즘 문제를 잘 해결하기 위해서는 3가지가 필요합니다. 1. 여러 알고리즘, 자료구조 등 배경지식이 필요합니다. 2. 배경지식을 현재 문제 상황에 맞게 잘 선택, 변형할 줄 아는 능력(문제해결능력)이 필요합니다. 3. 생각한 풀이를 코드로 나타낼 수 있는 능력(구현력)이 필요합니다. 우리는 이 세가지 능력을 기르는 연습을 해야합니다. www.acmicpc.net Baekjoon Online Judge Baekjoon Online Jud..
www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 육십갑자의 확장판 문제. M = 10, N = 12 인 경우는 육십갑자의 방식과 같다. (10개의 천간, 12개의 지지) 총 경우의 수는 M과 N의 최소공배수 만큼이다. 따라서 육십갑자의 모든 경우의 수는 10과 12의 최소공배수인 60이다. 처음에는 최소공배수를 구해서 그만큼 돌리다가 안나오면 -1, 나오면 출력을 하려고 했으나... 그냥 배열로 중복을 체크하면서, x는 고정시킨 채 y가 나오는 해를 구할 때까지..