SW 행사
홈>SW 소식>SW 행사
장소 : 인터넷 강의 모집기간 : 2017-04-25 ~ 2017-05-07
많은 사람들이 어려워 하는 다이나믹 프로그래밍을 쉽고 이해가기 쉽게 가르칩니다.
먼저, 이번 챕터에서는 다이나믹 프로그래밍이 뭔지를 배우게 되며, 약 20가지 문제 풀이를 통해서 다이나믹 프로그래밍을 연습합니다.
4. 수학 1
알고리즘을 공부하는데 왜 갑자기 수학이 필요할까요?
먼저, 알고리즘 대회나 이런 문제 풀이에서 중요한 것은 복잡한 프로그램은 구현 능력이 아니고 문제 해결 능력입니다. 당연히 복잡한 프로그램의 구현 능력도 중요합니다. 간단하고 정제되어있는 문제를 해결하지 못한다면, 복잡하고 정제되어 있지 않은 문제를 풀 수 있을까요? 따라서, 경우의 수가 매우 큰 경우에는 큰 정수의 구현 보다는 나머지 연산을 통해서 정답을 출력하라는 문제를 많이 만날 수 있습니다. 따라서, 첫 번째로 나머지 연산에 대해서 배웁니다.
그 다음은 최대 공약수와 최소 공배수에 대해서 배웁니다.
소수는 약수가 1과 자기자신 밖에 없는 수입니다. 소수는 암호학에서 매우 중요한 역할을 하고 있으며, 알고리즘에서도 소수가 매우 중요합니다. 따라서, 어떤 수가 소수인지 판별하는 방법과, 어떤 정수 범위 안에 들어있는 소수를 구하는 방법을 배웁니다.
마지막으로는 소인수분해를 하는 간단한 방법과 진법 변환, 그리고 팩토리얼에 대한 내용을 조금씩 배우고 넘어갑니다.
5. 정렬
정렬은 STL의 sort를 응용하는 방법을 배웁니다. O(N^2) 정렬 알고리즘은 다루지 않으며, 강의 때는 O(NlgN) 정렬 알고리즘만 다룹니다. 다양한 데이터를 정렬해야 하는 상황을 제시하며, 이럴 때는 sort의 비교 함수를 어떻게 작성해야 하는지를 배웁니다.
퀵 소트, 머지 소트, 힙 소트같은 유명한 소트 알고리즘은 다루지 않을까요? 아닙니다! 모두 다 강의 시간에 다룹니다. 퀵 소트와 머지 소트는 분할 정복 챕터에서, 힙 소트는 자료구조 2 챕터에서 배웁니다.
6. 그래프 1
그래프는 가장 자료구조 중의 하나입니다.
그래프가 뭔지, 그래프 용어에 대해서 배웁니다.
이제, 그래프가 무엇인지 알았기 때문에 그래프를 저장하는 방법 세 가지를 배웁니다. 그 세 가지는 바로 인접 행렬, 인접 리스트, 간선 리스트입니다.
세 가지 중에서 가장 중요하게 다루는 내용은 인접 리스트입니다. 인접 리스트를 사용하면 인접 행렬을 사용했을 때보다 시간과 공간이 더 효율적입니다. 효율적인 알고리즘 구현을 위해서 연결 리스트를 사용하지 않고 STL의 vector를 사용해서 인접 리스트를 구현하는 방법을 배웁니다.
그런데, 연결 리스트를 구현하기도 싫고, 사정상 STL을 사용할 수 없는 곳이라고요? 그런 분들을 위해 간선 리스트라는 자료구조도 준비했습니다. 간선 리스트는 그 어떤 책을 봐도 나오지 않는 신기한 자료구조입니다. 그런 분들을 위해 준비한 자료구조입니다.
이제, 그래프의 탐색에 대해서 배웁니다. 바로 DFS 알고리즘과 BFS 알고리즘입니다. 바로 전에 배운 자료구조 3가지를 이용해서 그래프를 탐색하는 방법을 배우면서 그래프를 저장하는 방법을 다시 한 번 복습하게 됩니다.
이제 DFS와 BFS를 응용할 차례입니다. 따라서, 연결 요소에 대한 내용을 배우고, 이분 그래프에 대한 내용을 배우게 됩니다.
그래프에서 가장 중요한 것은 일반 문제를 그래프로 모델링해서 푸는 것입니다.
그래프 모델링을 연습하기 위해서 사이클을 찾는 연습과 이차원 배열 상에서 플로드 필 알고리즘을 배웁니다.
7. 트리 1
그래프를 배웠으니 이제 트리를 배울 시간이지요! 트리의 용어에 대해서 배우고, 트리를 순회하는 방법인 프리 오더와 인 오더, 포스트 오더에 대해서 배웁니다.
그 다음에는 그래프와 마찬가지로 트리를 저장하는 방법 세 가지를 배웁니다.
트리를 저장하는 방법을 배웠으니 트리 문제를 통해서 트리 알고리즘을 연습할 시간이지요. 트리의 부모에 대한 내용과 트리의 지름에 대한 내용으로 트리를 복습합니다.
포함되어 있는 문제
1. 알고리즘과 입/출력
- Hello World
- A+B
- A+B - 2
- A+B - 3
- A+B - 4
- A+B - 5
- A+B - 6
- A+B - 7
- A+B - 8
- 그대로 출력하기
- 그대로 출력하기 2
- 숫자의 합
- 열 개씩 끊어 출력하기
2. 자료구조 1
3. 다이나믹 프로그래밍 1
- 1로 만들기
- 2×n 타일링
- 2×n 타일링 2
- 1, 2, 3 더하기
- 붕어빵 판매하기
- 쉬운 계단 수
- 오르막 수
- 이친수
- 스티커
- 포도주 시식
- 가장 긴 증가하는 부분 수열
- 가장 큰 증가 부분 수열
- 가장 긴 감소하는 부분 수열
- 가장 긴 바이토닉 부분 수열
- 연속합
- 계단 오르기
- 제곱수의 합
- 타일 채우기
- 파도반 수열
- 합분해
- 암호코드
4. 수학 1
- 나머지
- 최대공약수와 최소공배수
- 최소공배수
- GCD 합
- 진법 변환 2
- 진법 변환
- 2진수 8진수
- 8진수 2진수
- -2진수
- Base Conversion
- 소수 찾기
- 소수 구하기
- 골드바흐의 추측
- 소인수분해
- 팩토리얼
- 팩토리얼 0의 개수
- 조합 0의 개수
5. 정렬
6. 그래프 1
7. 트리 1
※ 교육 신청은 아래의 신청하기에서 해주세요 ※
- 댓글보기
- 본 게시물의 취지에 맞지않는 글은 예고없이 삭제 및 수정될 수 있습니다.