1주차부터 4주차까진가? 는 백준 문제로 알고리즘을 배우는 주차이다.
1주차에는 간단하게 정렬, 완전탐색, 재귀를 배운다. 물론 스스로 해야한다. 정글에서는 누가 가르쳐 주지 않는다.
이 스스로 공부하는 방법이 나는 어렵다. 이제까지는 학교에서 교수님이(비록 설명은 친절하지 않더라도) 지식을 떠먹여주셨고, 나는 그걸 제대로 받아먹기만 하면 됐었다.
이제까지는 이미 학교에서 모두 배운 내용이라 어려운 부분은 딱히 없었지만, 내 지식을 코드로 옮기는 연습을 해야겠다는 생각을 했다.
백준에서 여러 문제들을 풀어보면서 코드로 옮기는 능력을 조금은 성장시킨 것 같다.
1주차 공부 키워드
- 배열, 문자열
기초니까 생략하자
- 반복문과 재귀함수
반복문이야 기초니까 생략
재귀함수는 스스로를 호출하는 함수이다.
어떠한 작업을 완료할때까지 이 함수가 계속 필요할때 사용하면 된다. 물론 중단점(완료 시점)을 제대로 잡지 않으면 무한재귀로 스택 오버플로우가 발생할 수 있다.
https://www.acmicpc.net/problem/1780
예를 들어 이 문제를 보자. 3^K 크기의 정사각형에서 모두 같은 수가 아니라면, 이를 9개의 영역으로 나누어 그 영역에서 모두가 같은 수인지 확인해야 한다.
여기서 완료 시점은 '같은 영역 내의 수의 모두 같은 수인가?' 이고, 재귀는 depth 한번에 9번(!!!)이 발생한다.
만약 K가 크다면 스택으로 푸는 방법도 고려해야 할 것 같다...
처음 9 x 9 영역에서 만족하지 못해서 3 x 3 영역을 9개 만들었다. 여기서 완료 시점을 만족한다면, COUNT를 1 증가시키고 종료한다. 여기서도 만족하지 못하면 위 3 x 3 영역에서 1 x 1 영역으로 나누어 확인해야 한다.
1 x 1 영역은 어차피 같은 수일수밖에 없기 때문에 무조건 종료된다.
이렇게 재귀함수를 사용하면 사람이 이해하기 편하게 문제를 분할하여 풀 수 있고, 직관적으로 이해하기 쉽다.
메모리는 그만큼 더 쓴다
- 복잡도
for문이 몇 개 중첩되어있는지, 문제가 얼마만큼 줄어들고 늘어나는가를 확인하자
- 정렬
학교다닐때 자료구조 시간에 배웠던 기억이 난다. 그때는 C로 구현한다고 정말 애먹었던 기억이 난다.
배우면서 틈틈히 노션에 정리해두었다.
https://verdant-bathtub-bae.notion.site/1b77bb7778c9807db786e0c2dc9a1437?pvs=4
정렬 | Notion
정렬 알고리즘은 동일한 순위의 데이터들이 정렬 후에도 순서가 보장되는 안정된(stable) 알고리즘과 그렇지 않은 알고리즘 두가지가 있다
verdant-bathtub-bae.notion.site
- 완전탐색
이번 주차 완전탐색 문제는 안전 영역, 외판원 순회, 차이를 최대로, 일곱 난쟁이 총 4문제가 나왔다.
완전탐색은 가능한 모든 경우를 따져 정답을 찾는 문제다. 어떻게 보면 재귀 문제랑 결이 거의 비슷한것 같다.
이 중 외판원 순회 문제는 처음에는 조금 애를 먹었다. 내가 기존에 알던 문제는 시작하는 정점을 주고 시작했었는데, 모든 정점에서 시작할 수 있는 문제는 처음 풀어봤다.
완전탐색으로 처음 풀었을 떄는 시간초과가 나서 DP로 겨우겨우 풀었는데, 다시 찬찬히 문제를 들여다보니 완전탐색으로도 풀렸다.
내가 좋아하는 완전탐색 기법은 백트래킹을 사용한 DFS이다. 사실 웬만한 패턴이 있는 문제는 다 이걸로 풀리는 것 같다.
- 정수론
이건 정말 이해하지를 못하겠다. 소수와 소인수분해 등이 이 영역에 들어가는 것 같은데... 공부하는 교재인 'Introduction to Algorithms'를 보면 정말 이게 수학책인지 알고리즘 책인지 분간이 가질 않는다...
그 중 RSA 공개키 암호 시스템을 따로 정리해봤다.
https://verdant-bathtub-bae.notion.site/RSA-1ba7bb7778c98011a74bcb8b5a26124c?pvs=4
RSA 공개키 암호 시스템 | Notion
사용자들은 모두 서로 PublicKey(공개 키)와 SecretKey(비밀 키)를 가지고 있다. 이 중 공개키는 누구나 볼 수 있도록 오픈된 공간에 둔다.
verdant-bathtub-bae.notion.site
퀴즈와 시험
내용은 노코멘트 하겠다... 족보를 좀 타는것 같기도 하고 후기수가 이걸 보고 미리 알아놓으면 불공평하니까
사실 정글에서 공부하라는 부분만 공부하면 정말정말정말 쉽게 풀 수 있다.
1주차 후기
사실 0주차가 너무 재밌었어서... 이번 주차에 혼자 공부하는 부분은 루즈한 감이 없지 않아 있었다...
그래도 평소 코테를 제대로 연습하지 않아서 문제에서 보이지 않던 패턴이 눈에 보이니까 성과가 확실히 있긴 한듯