백준 알고리즘 코드플러스 강의(인강) 후기

코드플러스 백준 알고리즘 강의 중급과 고급을 수강하고 작성한 개인적인 후기입니다. 강의의 개요를 파악할 수 있도록 강의의 모든 목차가 기록되어 있습니다만, 강의 저작권을 고려하여 강의 내용은 제가 필기한 부분 중 일부분만 포함되어 있습니다.

알고리즘 관련 공부를 처음하신다면, '기초'강의 부터 수강하시기를 강추 드립니다. 만약 자료구조/알고리즘 수업을 꽤 재미있게 들어서 기초강의에 있는 스택/큐/그래프 등의 내용을 다 숙지하고 있으며, 실력에 자신 있다고 하더라도, 이런 종류의 문제에 접근하는 방법과 팁을 효율적으로 학습하기 위해 기초강의 부터 차근차근 수강하는것을 강추드립니다. 오히려 중급을 듣다가 모르는 부분을 찾아보고 이렇게 하는것은 시간 낭비입니다. 시간은 돈입니다 :)

저는 '중급 셋트+고급으로 가는 연결고리 셋트'를 약 31만원 주고 결제했습니다. 중급셋트는 수강기간이 3달이고, 고급으로 가는 연결고리셋트는 수강기간이 2달입니다. 솔직히 이 기간동안 저 모든 강의를 소화한다는것은 상당히 빡빡한 일정이었습니다. 만약, 약 61.4만원의 종합 셋트를 구매하면 기초과정부터 포함된 모든 강의를 1년내내 수강할 수 있습니다. 제가 만약 시간을 되돌릴수 있다면 '종합 셋트' 강의를 결제할것 같습니다.

단, 코딩대회나 순수 알고리즘 학습에 대한 목적 보다는 '코딩인터뷰를 준비'하기 위한 공부라면, 인터뷰 준비셋트를 추천드립니다.

최백준 알고리즘 강의 사이트인 '코드 플러스의' 강의 중 어떠한 강의를 선택해야 되며, 어떤 할인혜택을 받을 수 있는지에 대한 내용은 다음의 포스팅을 참고하시면 됩니다.

관련글: 백준 인강 듣는 법 (백준 알고리즘 강의 - 코드 플러스)

저는 총 31만원을 지불하고 알고리즘 중급과 알고리즘 고급으로 가는 연결고리를 결제하였습니다. 각각 3개월, 2개월 이라는 시간이 주어지지만, 겹쳐서 결제했기 때문에 총 강의 수강 기간은 3개월 정도 였습니다.

중급 - 총 37시간

- 중급1: 7시간

- 중급2: 11시간

- 중급3: 9시간

고급으로 가는 연결고리 - 총 17시간

- 고급으로1: 8시간

- 고급으로2: 9시간

예습/복습/문제풀이를 제외한 순수하게 강의를 듣는데만 걸리는 시간이 54시간이었습니다.

하루에 6시간 들어도 듣는데만 9일.... 3시간씩 들으면 18일이 걸리는 시간이었으며, 실제로 하루에 3시간씩 강의를 듣는것은 쉬운일이 아니었습니다.

아래는 제가 12주동안 공부를 어떻게 했는지 간략하게 적은 표입니다. 저는 이미 각 알고리즘에 대해서 잘 알고 있는 상태였기 때문에, 제가 필요한 순서대로 골라가며 수강하였습니다.

중급1BF	중급1재귀	중급1BFS	-	-	-	중급1그리디
중급1분할정복 중급2BF	중급2자료구조2 기초2그래프1 중급3그래프2	-	-	중급3세그먼트	중급3BF	-
중급3펜윅트리 중급2문자열 기초1DP1	중급2수학 DP2	중급1-완료 그리디/분할정복 중급3 그래프/트리/수학	고으1조합게임1 고으2NF1,2 개념	-	-	고으2MCMF개념
BUSY	BUSY	BUSY	중급2/DP2복습	-	-	-
-	-	중급2/문자열1 고급으2/문자열2	중급1BF/BFS/그리디/분할정복	그래프 복습	고으1조합게임1 복습	고으1조합1복습/세그,펜윅 중급3세그,펜윅복습
-	BUSY	BUSY	BUSY	BUSY	DP3,그래프복습	-
BUSY	BUSY	그리디-LIS	-	-	중급2BF	중급3DP3
-	중급2BFS 트리2 중급2-완료	-	중급2/DP2복습	-	중급3/DP3복습	중급2기하 고급 고으2 NF1,2 / MCMF 중급2BF 문자열/DP2
고으1DP4 문자열2	고으2DP5 세그먼트 펜윅2 중급3DP3/DP4/DP5	BUSY	BUSY	BUSY	BUSY	BUSY
-	-	-	-	-	-	-
-	-	-	-	-	-	-
25			고급	고급	고급	고급

● 알고리즘 기초

프로그래밍 언어 (C++, Java)를 할 줄 알고, 기초 알고리즘을 배우는 강의입니다.

알고리즘 기초 1/2 정리: inner-game.tistory.com/256
알고리즘 기초 2/2 정리: inner-game.tistory.com/257

알고리즘 기초 1/2

100 - 알고리즘 시작

먼저,알고리즘이 무엇인지,어떻게 공부하는 것이 좋은지알아봅니다. 그 다음으로 알고리즘의 효율성을 측정하는 방법 중 하나인시간 복잡도에 대해서 배워봅니다.

200 - 자료구조 1

스택 (Stack)에 대해서 집중적으로 배워봅니다. 스택을 사용하는 문제를 이용해 스택의 어떤 성질을 이용해서 문제를 해결할 수 있는지 알아봅니다. 큐(Queue)와 덱(Deque)은 이 챕터에서 소개만 합니다. 두 자료구조는 그래프와 BFS 챕터에서 집중적으로 다루게 됩니다.

300 - 수학 1

문제를 푸는데 필요한 기본적인 수학 내용을 알아봅니다.나머지 연산,최대 공약수,소수에 대해서 알아봅니다.

400 - 다이나믹 프로그래밍 1 (중급2, 중급3 연관)

다이나믹 프로그래밍이 무엇인지, 난이도가 가장 낮은 문제들을 이용해 다이나믹 프로그래밍을 이해해 봅니다.

알고리즘 기초 2/2

500 - 브루트 포스 (중급1, 중급2 연관)

모든 경우의 수를 다 시도해보는 알고리즘인 브루트 포스에 대해서 알아봅니다.

경우의 수를 만들기 위해 순열, 재귀, 비트마스크방법을 알아보고, 여러가지 문제를 해결해봅니다.

600 - 그래프 1

그래프와 그래프를 저장하는 방법인인접 행렬,인접 리스트를 알아봅니다. 그 다음, DFS와 BFS 알고리즘도 알아보고 여러가지 문제에 적용해봅니다.

610 - BFS (중급1, 중급2 연관)

문제를 그래프로 모델링해 BFS로 풀어봅니다.

620 - 트리 1

트리와 관련된 기본적인 내용을 알아봅니다.

● 알고리즘 중급 1/3 (7시간 10분 28초)

521, 531, 541 - 브루트 포스 - 순열, 재귀 비트마스크 (연습)

알고리즘 기초 2/2에서 공부한 브루트 포스 알고리즘을 여러가지 문제에 적용해봅니다.

611 - BFS (연습)

알고리즘 기초 2/2에서 공부한 BFS 알고리즘을 여러가지 문제에 적용해봅니다.

710 - 그리디 알고리즘

그리디 알고리즘과 여러가지 문제들을 알아봅니다.

800 - 분할 정복

분할 정복 알고리즘과 여러가지 문제들을 풀어봅니다.

820 - 이분 탐색

이분 탐색을 이용해서 정답을 결정하고 문제를 푸는 방법을 알아봅니다.

521 - 브루트 포스 - 순열 (연습)

부등호 부등호가 k개, 10개중 k+1개를 고르고 (k+1)!순서를 만들고 부등호 검사

2^(k+1) x (k+1)! x (k+1) 부등호 검사

모두 해보지 않고, 가장 큰수 (9876)과 가장 작은수(0123)를 구해본다. <- 이 개념이 신기.

단어 수학 그리디 방법이 더 좋음

연산자 끼워넣기 실제 경우의 수는 (n-1)! 이 아니고, 연산자가 4개 이므로 가장 다양하게 연산자가 구성된 경우에 2520밖에 안됨.

스타트와 링크 두팀의 능력치를 구한 다음, 차이의 최소값을 구하는 문제

항상 두팀으로 나눈다는것이 핵심.

11/9 : 연산자 끼워넣기 까지 들었음, 다음날 다 들음
12/8 : 다시들음
문제해결방법: 다해봐야함, 그런데 순서만 변경할수 있다고 할때, 순열을 사용한다. 그리고 개수가 고정되어 있다.

브루트포스에서는 사실 순열을 많이 이용하지 않는다. 그리고 앞에서 풀어본 모든 문제들은 재귀로 바꿔서 풀수있다. 는 것이 오늘의 결론.

531 - 브루트 포스 - 재귀 (연습)

로또 : 고르고 재귀호출, 돌아나오면 안고른걸로 리셋하고 다음꺼선택후 재귀호출

부분수열의 합 : 크기가 0인 부분수열 처리법을 눈여겨보자.

부분수열의 합

연산자 끼워넣기 : 네가지 재귀를 네줄로 사용

연산자 끼워넣기 (2) : 위와 같은 방법

테트로미노 : 1가지 모양 빼고 나머지는 재귀함수로. dfs처럼 보이지만 아니다.

두 동전

에너지 모으기:여기까지가 재귀함수 이용하는 브루트포스

N-Queen : 여기부터가 백트랙킹 - 강의는 재귀(연습)-2

대각선 배열 만드는거 별거아니지만 알면좋을듯

스도쿠

백트랙킹의 컨셉: 원래는 브루트 포스인데, 절대로 안될것 같은 케이스는 그냥 버리는것

원래 스도쿠는 백드래킹으로 풀수없다 여기는 인풋이 가능하기 때문임.

스도미노쿠

알파벳

11/10 : 스도미노쿠는 다시 봐야함, 백트랙킹, 브루트포스, DFS 명확히 비교하여 개념잡기

백트랙킹: 재귀로 했다가 나가면서, 뒤로 돌아가는것

브루트포스: 전체를 다 해보는것

DFS: 재귀함수, 특히 트리에서 깊이우선

12/8 : 재귀함수로 풀어보는 브루트포스 입니다. 하고 뒤에는 잘안들었음

12/10 : 테트로미노 설명중 : 브루트포스와 dfs의 가장 큰 차이점: dfs는 방문했던 칸을 다시 방문하지 않았다고 하는게 절대로 없음.

모든 브루트포스에 리셋 해주는 부분이 존재한다.

533 - 브루트 포스 - 재귀 (참고)

퇴사

11/10: 완료.

12/10: 퇴사문제를 재귀로 우선 풀었다고 가정하고, 퇴사문제가 왜 다이나믹이 될수있는지 설명하는 강의

-> 어떤 재귀함수의 호출이, 이전에 구한답이 앞으로 선택할 답에 영향을 주지 않는 경우는 디피로 구현가능하다.

541 - 브루트 포스 - 비트마스크 (연습)

부분수열의 합

가르침

구슬 탈출 2 : 구슬을 기울이는것에 대한 경우의 수를 잘 정의하는게 중요. 불가능한경우를 제거하다보면 경우의수가 그렇게 많지 않다는것을 알수있다.

2048 (Easy)

11/10: 구슬탈출2와 2048은 대충들은듯, 풀어보면 알겠지.

12/10: 비트마스크...두번들으니까 훨씬 낫다. 비트마스크 응용 예제를 배울수 있어서 좋았다. 언제풀어보려나.

기초강의를 듣지않았는데, 잘정리해주신분이 있어서 블로그를 참고하여 공부했다. 역시 기초강의를 듣는게 나았을듯.. instories.tistory.com/76

MIT BFS 강의 : youtu.be/s-CYnVz-uh4?t=368

- BFS 는 최소를 구한다는 성질이 있다. 하지만 여기서는 한정점에서 시작해 연결된 모든 정점을 방문한다는 성질을 이용한다.

611 - BFS (연습)

뱀과 사다리 게임

데스 나이트: BFS의 기본문제인 미로탈출과 비슷함.

DSLR : DFS,BFS, 최소값만 구하는것이 아니고 과정도 구해야한다. 그래서 how 배열 사용했음.

연구소 : 3개의 벽을 세우는데 (NM)^3, 다시 탐색하는데 NM, 그래서 총 (NM)^4가 걸린다.

N개에서 k개를 고르는 경우에는 2^N일때는 재귀를 이용하는데, k가 고정일때는 지금처럼 반복문이 더 나은편이다.(재귀는 머리가 복잡해서..)

돌 그룹 각 그룹 돌의 개수를 같게 만들수 있는지 없는지 구하는 문제 <- 이런 문제는 갈수 있는지/없는지 보는거라 DFS/BFS 모두 가능하다.// 여기까지 1강

벽 부수고 이동하기 <- 여기부터 2강

11/15: 4연산 2axb부분 이해제대로 한것인지 체크 필요

12/10: 복습1강만

710 - 그리디 알고리즘

동전 0 : 작은 동전부터 고르고 합친다.

회의실배정 : 일찍 끝나는 회의부터 고른다. 정렬필요, NlogN

ATM : 오름차순으로 정렬하고, 가장 짧은 시간이 걸리는 사람부터 인출한다.

행렬 : 0과 1로만 되어있을때는 두번하면 다시 원점으로 돌아가니까, 연산을 한번만 적용하도록 코딩하는것이 중요하다. 스위치 끄고 켜고 끄고 처럼 되는것.

전구와 스위치 : 1번 스위치를 누르는 경우와 안누르는 경우 모두 구하면 된다.

동전 뒤집기<- 여기까지 1

보석 도둑 <- 여기부터 2

순회강연

가장 긴 증가하는 부분 수열 2 14분

11/15: 그리디는 기존에 개념과 증명을 알고있다면 금방 들을 수 있다.
12/10: 그리디는 지금 봤을 때 가장 좋은것을 선택하는 것입니다.

어떻게 보면 쉽지만, 어떻게 보면 가장 어려운 알고리즘. 왜냐면 그것이 최선의 선택이라는것을 증명해야하기 때문이다.
거스름돈 문제 처럼 대소관계가 있을때 가능하다.
증명이 두개다.
1. 그리디 이다. : 증명하기 까다롭다.
2. 그리디가 아니다. : 반례만 찾으면 되서 증명하기 쉽다.
1강만들었다.

12/22: 가장 긴 증가하는 부분수열만 다시들음

1. 브르투포스, 길이별로 최적예시를 만들어준다 길이 1짜리, 2짜리,3 짜리 , 4짜리...

2. 가장 길이가 긴것만 알고있으면 중간에껀 다시 만들어낼수있다.

실제 배열을 구하는 방법은 앞에꺼의 인덱스를 저장함

711 - 그리디 알고리즘 (연습)

11/15 : 대회 인턴이 설명이 없었던것 같은데...? A와 B는 직접 풀어보기
11/25 : 병든나이트 부터 다시보기 시작함

712 - 그리디 알고리즘 (도전)

NMK- 플래티넘3

롤러코스터 - 플래티넘3 (LUNAPARK)

A와 B 2 - 실버3

11/25
- NMK는 그룹나누는 아이디어 생각못하면 문제를 아예 못품..
- 롤러코스터
NM이 둘다 짝수이면 모든칸 방문 못하는 아이디어를 알아야함
ㄹ자로 이동하는 아이디어를 알아야함.
모든칸을 이동할수없고, 그 칸은 검정칸이 되어야함
행을 먼저 다 이동하고, 열을 이동하는 아이디어를 알아야함.
롤러코스터의 증명을 꼭 기억하면 좋겠다고 함.
- A와 B2

800 - 분할 정복

숫자 카드 : 이건 안풀어줌, 그냥 이분탐색입니다~!그럼.

숫자 카드 2 : 앞에꺼와 비슷한데 상한과 하한을 적용하면 됩니다. 끝.

배열 합치기: 머지소트

11/15 : 1강은 개념설명이라 2배속으로 금방 봄
12/10: 다이나믹과 분할정복의 가장 큰 차이는 부분문제가 중복이 되냐(메모이제이션) 중복이 되지 않냐의 차이이다.
이분탐색 알고리즘이 가장 중요하다.
상한과 하한에 대해서 배움. 상한은 큰수중 첫번째 수, 하한 크거나 같은수 중 첫번째 수.

머지소트는 머지를 하면서 정렬한다는 뜻.
머지소트 구현도 보여준다.

퀵소트: 평균적인 상황에서 최고의 성능을 자랑하는 프로그램
스토어인덱스라는걸 이용한다.

퀵셀렉트: 왼쪽인지 오른쪽인지에 따라 하나만 호출하는 성격

801 - 분할 정복 (연습)

11/15 2배속... 트리에서 인오더의 인덱스를 저장한다는것은 색다른것 같았다(?)
z하고 사분면, 별찍기는 직접풀어보라고함. 버블소트는 한번 풀어봐야겠다.

802 - 분할 정복 (도전)

스카이라인 - 골드2

교차하는 부분의 아이디어가 있어야함. 이걸 기반으로 실루엣을 먼저 구하고, 계산한다.
넓이 구하는 부분은 다시 봐야함.

가장 가까운 두 점 - 플래티넘4

11/25 들었다.

810 - 정렬

11/16 정렬은 답을 구하기 위한 선처리이므로 라이브러리를 쓰는게 좋다.

820 - 이분 탐색

11/16 빠르게 2배속으로 아이디어만 훑어봤다. 즉 코드를 자세히 살펴보지는 않았다.
이분탐색은 : 최소의 최대, 최대의 최소 이런것을 구하는 문제에 많이 사용된다.
삼분탐색 코드 다시보기

821 - 이분 탐색 (연습)

11/16 2배속으로 쓱 봤는데 한번 풀고나서 다시 봐야할듯

● 알고리즘 중급 2/3 (11시간 3분 1초)

550 - 브루트 포스 - 문제

알고리즘 기초 2/2에서 공부한 브루트 포스 알고리즘을 여러가지 문제에 적용해봅니다.

612 - BFS (연습 2)

알고리즘 기초 2/2에서 공부한 BFS를 여러가지 문제에 적용해봅니다.

900 - 자료구조 2

스택을 조금 더 다양하게 응용해보고, 유니온 파인드, 힙, BST에 대해서 알아봅니다.

910 - 문자열 알고리즘 1

문자열 매칭 알고리즘 KMP, 라빈 카프, 해싱, 트라이, 아호 코라식에 대해서 알아봅니다.

1000 - 다이나믹 프로그래밍 2

기초 강의에 포함된 다이나믹보다 조금 더 어려운 다이나믹 문제를 풀어봅니다.

1100 - 수학 2

거듭 제곱과 관련된 내용들 입니다.

1110 - 기하 알고리즘 1

CCW를 이용해 선분 교차, 다각형의 넓이, 내부/외부 등을 구해봅니다. 볼록 껍질을 구하는 그라함 스캔과 라인 스위핑 알고리즘을 살펴봅니다.

550 - 브루트 포스 - 문제

차량 번호판 1
양념 반 후라이드 반
로마 숫자 만들기
십자가 찾기 <- 11/16
나3곱2
두 스티커
캠프 준비 <- 여기까지 들음 (문제1)
숫자 재배치 <- 여기부터 (문제2) // 큰수부터 배치하는건 왜 안되는가?
괄호 추가하기 // 쉬프트연산 쓰는 부분 체크필요
감시
등차수열 변환
치킨 배달
숫자판 점프
테트리스
한윤정이 이탈리아에 가서 아이스크림을 사먹는데
NxM 보드 완주하기
세 친구
배열 돌리기 4

11/17: 대충들어서 이거 참.. 캠프 준비는 꼭 다시 풀어보기.
11/20: 문제2를 듣고있다. 배열돌리기까지 다 보긴봄.

551 - 브루트 포스 - 문제 (연습)

파이프 옮기기 1 골드5
파이프 옮기기 2 골드5
괄호 추가하기 2 골드1 : 앞에꺼랑 관련있음
십자가 2개 놓기 실버1
계란으로 계란치기 실버2
Baaaaaaaaaduk2 (Easy) 골드3 <- 연습2 강의시작
사다리 조작골드5: 강의 듣기 전에는 사다리를 1,2,0으로 모델링하는게 상상이 안되었었다.
삼각형의 값 골드2
매직 스퀘어로 변경하기 실버4 : 먼저 배열을 코드에 넣어 놓는다.
A → B 실버1 : 두가지 방식이 있다. 입력의 크기가 크지 않기 때문에 가능한 BF, 연산을 특징을 파악하는(커진다, 끝에서 다르니까 역방향 등) 문제는 직관이 필요해서 어려운것 같다고 생각-백준

11/25 수강완료

552 - 브루트 포스 - 문제 (도전)

강의가 없음

560 - 브루트 포스 - 기타

12/23 '투포인터' 알려줌 ㅎㅎ 역시 설명을 너무 잘하심.

12/26 8분 소수의 연속합 부터 들음

'중간에서 만나기' meet in the middle, 분할정복이랑 헷갈리지 말라고 하심. 반으로 쪼개서 한쪽을 풀고 한쪽을 푼다음에 합쳐서 푸는것.

612 - BFS (연습 2)

12/29 빠르게 들었다.

늑대와 양 늑대의 위치에서 BFS/DFS를 하면 됨, 그러나 최소를 구하는 문제가 아니라서 BFS문제가 아님,(네트워크 플로우 민컷-mincut)

1. 양이 인접한 4개의 칸에 늑대가 있는지 확인 2. 늑대가 없었다면, 모든 빈칸을 울타리로 바꿔줌

탈옥 BFS: 하나의 위치에서 다른 위치로 이동하는것, 그래서 도착점이 필요하다.

문제를 특정지점에서 만나기 위한 최소 횟수 라는 것으로 변경

죄수가 1명이면 그냥 BFS 로 구할 수 있다.

로봇청소기 순서도 구해주어야한다. BFS이용해서 순서를 먼저 구해놓은다음에 마지막에 이용하는것이 특징

거울설치 다음 거울을 미리 찾아야한다.

900 - 자료구조 2

문자열 폭발 : C4라는 문자열을 삭제하는 건데, 괄호매칭이랑 똑같이 스택 사용하면 된다.

그런데, abc폭발 문자열은 조금 까다롭다.

일부가 사라졌을때 남은걸 빠르게 O(1)을 찾기 위해서 스택을 사용한다. abc맞 찾고 있는데 d가 나오면 스택을 비워버린다. 왜냐면 영원히 앞에꺼와 같이 폭발할수없기 때문이다.

히스토그램에서 가장 큰 직사각형 이 문제의 핵심은 스택을 이용해서 푸는 것이고, 스택에 모든 막대가 들어갔다 나와야 하므로 O(N)

간단한 문제지만 원리를 암기하는것이 좋을것 같다. 내 생각. 17분쯤.

기초과정에서 오등큰수 오큰수 이런거 유사문제라서 먼저 풀어보면 좋다.

오아시스 재결합 위 에꺼도 그렇지만, 1번은 일단 스택에 넣고 시작한다.

이것도 스택에 뭘 넣고 빼는지를 이해해야한다.

키가 같은 사람이 있을때는 스택이 두개 있어야 한다. 그래서 높이 따로 사람수 따로 이렇게 넣어주어야함.

집합의 표현<- 여기부터 2강, 유니온파인드

이건 그냥 유니온파인드에요 하고 넘어감.

바이러스 꼭 유니온 파인드를 써야하는게 아니고 여러 방법이 있고, 그중 하나가 유니온파인드다.

최대 힙 : 풀이없음

최소 힙 : 풀이없음

가운데를 말해요 :

왼쪽 오른쪽으로 그룹을 나눠서, (N/2) 홀수 인경우는 왼쪽 = 오+1 하고, 왼<=오 로 한다.

왼쪽에서 가장 큰 값을 오른쪽으로 보낸다.

회사에 있는 사람 <- 강의없음. 풀어보슈

듣보잡 <- 강의 없음. 풀어보슈

11/17 : 기존 강의들을 앞에 좀 건너뛰고 자료구조2 들으러옴. 상관없어야 할텐데. 재밌게 들었다. 마지막 문제는 따로 풀어보라고 하네.
12/10: 복습
스택, 설명없이 문자열폭발 풀이 시작.

유니온파인드
유니온파인드는 리트코드에 이지가 없네. 무조건 미디움 부터구나.
합치기연산과 루트찾기인 파인드 연산이 있다. 둘다 배열을 이용한다면 구현은 쉬운편이다.
트리가 기울여져있다면 O(N)이 걸린다 파인드가 엔이어서 유니온도 엔 걸림
그런데 경로압축이라는것을 이용하면 시간을 단축할 수 있다.
복잡도는 애커만 역삼수, 5보다 작다. 상수다

힙

최대힙 삽입: 자식에 넣어주고 루트로 올라가면서 비교해서 바꿔준다. 그래서 높이만큼 log(N)

최대힙 삭제: 루트를 가장 마지막에 있는 값으로 바꿈

이진검색트리(BST)
인오더석세서를 구해야한다.

균형잡힌밸런스트리가 필요하다. 근데 구현이 너무 길다.

AVL-Tree, Red-Black Tree, Splay Tree, Treap

901 - 자료구조 2 (연습)

11/17
카드구매하기 진지하게 다시 풀어봐야할듯, 스택이용, 유니온파인드 이용해서 모두 풀어줌
Ceiling Function은 강의에서 다루지 않았음.

♣ 문자열1 & 문자열2 정리: inner-game.tistory.com/380

910 - 문자열 알고리즘 1

911 - 문자열 알고리즘 1 (연습)

912 - 문자열 알고리즘 1 (도전)

빅 픽쳐

♣ 다이나믹 프로그래밍2 정리: inner-game.tistory.com/262

기초과정에서 보다 조금 더 어려운 다이나믹, DP2-1강의에 다이나믹개념 다시한번 잘 정리해줌

1100 - 수학 1

11/24 피보나치수 6이 가장 중요
어떤게 나오는지만 훑어봄. 다음에 다시 들어야 할듯

1102 - 수학 1 (도전)

11/25 완료

1103 - 수학 1 (참고)

pdf만 제공됨. 아직 안봄

1110 - 기하 알고리즘 1

12/?? 기하는 나중에 보자

● 알고리즘 중급 3/3 (8시간 59분 18초)

1200 - 그래프 2

위상 정렬, 크루스칼, 프림, 벨만 포드, 다익스트라, 플로이드 알고리즘과 관련 문제를 풀어봅니다.

1210 - 트리 2

트리의 LCA를 구하는 방법을 알아봅니다.

1230 - 세그먼트 트리, 1240 - 펜윅 트리

구간 쿼리를 구하는 세그먼트 트리와 펜윅 트리에 대해서 알아봅니다.

1300 - 다이나믹 프로그래밍 3

중급 2/3에 속해있는 다이나믹보다 조금 더 어려운 문제들을 풀어봅니다.

♣ 그래프 내용 정리 : inner-game.tistory.com/249

1200 - 그래프 2

1201 - 그래프 2 (연습)

1202 - 그래프 2 (도전)

배열 A 찾기

1210 - 트리 2

LCA

정점들의 거리

LCA 2

11/17 완료

12/29 LCA

1 번방법

1. 높이를 맞춰준다.

2. 공통조상을 찾는다.

정점들의 거리 : dist[u] + dist[v] - dist[lca(u,v)]

2번방법: BFS + 탐색

DP를 이용하면 lgN에 구할 수 있다.

3번방법: DFS+ tin/tout (백준선생님은 이방법을 선호)

1211 - 트리 2 (연습)

합성함수와 쿼리 : LCA와 2진수의 원리 (1 << i)를 이용해서 소스코드 구현

도로 네트워크

LCA와 쿼리

11/25

1220 - BFS 2

0과 1 덧셈의 나머지연산은 각각나머지구하고 더하고 나머지구한것과 같다

숨바꼭질 5 동생이 이동할때마다 BFS를 이용

퍼즐8퍼즐만 계산가능(3x3), 15퍼즐(4x4)이상은 너무 크다.

직사각형 탈출 누적합은 펜윅트리에서..// 1강 여기까지

체스판 여행 2 // 2강 여기까지

12/29 수업들었다.

♣ 세그먼트트리와 펜윅트리 정리 : inner-game.tistory.com/556

1230 - 세그먼트 트리

1240 - 펜윅 트리

구간 합 구하기 4 : 구간합을 알려줌
수들의 합 4: 구간합 diff로 구해도 o(N^2)인것이 문제.
- 변수 cnt[k]를 만들고, 카운트를 해준다음 합이 k가 되는것을 리턴하면된다.
나머지 합 :
구간 합 구하기 5 // 여기까지가 누적합
구간 합 구하기 // 여기부터 펜윅트리
구간 합 구하기 3

♣ DP3 정리 : inner-game.tistory.com/318

1300 - 다이나믹 프로그래밍 3

1301 - 다이나믹 프로그래밍 3 (연습)

1302 - 다이나믹 프로그래밍 3 (도전)

● 알고리즘 고급으로 1/2 (7시간 40분 42초)

1320 - 다이나믹 프로그래밍 4

비트마스크를 이용하는 상태 다이나믹에 대해서 알아봅니다.

1310 - 조합 게임 1

조합 게임을 DP를 이용해 풀어보고, 님 게임을 알아봅니다. 그 다음, Sprague–Grundy 이론에 대해서 알아봅니다.

1500 - 문자열 알고리즘 2

접미사 배열을 활용한 문제들을 해결해봅니다.

1600 - 세그먼트 트리와 펜윅 트리

두 트리를 이용해 문제를 해결해봅니다.

♣ DP4 정리 : inner-game.tistory.com/427

1320 - 다이나믹 프로그래밍 4

1321 - 다이나믹 프로그래밍 4 (연습)

1322 - 다이나믹 프로그래밍 4 (도전)

다이어그램과 태블로

직사각형 색칠

도로 건설

누가 이길것인가? 를 구하는것이 조합게임이다. Misére == 불행, 마지막에 가져가는건 불행이라는 뜻

주기를 찾아야함. 주기를 찾는 방법은? 어쨌뜬 2^22안에 찾을수있다고 한다. 이 경우에는...

1310 - 조합 게임 1

돌 게임 : 돌게임이란? 최적의 방법 구하기, 즉 optimal이 중요하다.
돌 게임 2
돌 게임 3
돌 게임 4
돌 게임 5
돌 게임 6
돌 게임 7
돌 게임 8 : 반복되는 주기 구하는 부분 다시 보기, 소스코드 비트마스크 부분도 잘 볼것.
박스 나누기 게임 : 2차원 DP
- 메모이제이션 배열 c[1][1] = true;
- d[1][1] = false;
재미있는 숫자 게임 ://여기까지 1강
- 2차원 DP -> 숫자도 중요하고 턴도 중요하기 때문이다. 즉 1234[0] 하고 1234[1]은 다른 결과
님 게임 2 플래티넘4 <- 님게임강의 // 님게임이 조합게임에서 가장 중요
- 님게임은 돌게임의 확장판
- 3차원 DP를 해야 할것 같지만, 하지 않아도 되는데, 그래서 가장 중요한 게임이라고 하는것이다.
- XOR해서 0이면 지는 위치다. 왜그런지는...직접 생각해봐야함.
- XOR테크닉은, 마지막 돌을 제거한 사람이 게임을 이기게 되는 경우에 적용 가능.
- 근데 마지막 돌을 제거한 사람이 게임을 지는경우에도 할수 있기는 있으므로 생각해보라고 함...(?)
- 윗줄의 답은 그런디정의 때문에 그런것이다.
님블 : 님게임이랑 똑같다. 동전이 돌더미이기 때문이다.
- 님게임과 똑같다. 동전이 돌더미를 의미하고 동전의 위치가 돌더미에 돌이 몇개있는지와 똑같다.
- 즉 XOR 이용해서 가능.
핌버
님 게임 홀짝
님 게임 나누기 : XOR의 의미는 여러개 중에 하나를 선택한다는 의미이다.