1주차 키워드
배열, 문자열, 반복문과 재귀 함수, 복잡도(BigO,시간,공간), 정렬, 완전 탐색, 정수론
이분 탐색, 분할 정복, 스택, 큐, 우선순위 큐, Linked List, 해시 테이블
자료구조는 이미 알고 있는 게 많아서 알고리즘 위주로 리마인드를 진행한다.
1. 분할 정복(DAC)
2^32를 어떻게 구할까?🧐
2를 32번 곱하는 방법도 있지만, (2^16)^2로 해서 풀면 2를 16번 곱한 것을 다시 2번 곱하니 17번의 연산만으로 끝낼 수 있어 시간이 훨씬 적게 든다.
이를 계속 해보면 {(2^8)^2}^2 이렇게 풀면 10번만에, [{(2^4)^2}^2]^2 이렇게 풀면 7번만에 끝낼 수 있어 시간이 획기적으로 주는 것이다.
A, B, C = map(int, input().split())
def power(a,b):
if b==1:
return a % C
else:
temp = power(a, b // 2)
if b % 2 == 0:
return temp * temp % C
else:
return temp * temp * a % C
res = power(A,B)
print(res)2. 완전 탐색
N-QUEEN
퀸은 행마다 하나만 반드시 존재해야 한다. 당연하지만, 문제를 푸는 첫 단추.
일곱 난쟁이
모든 경우의 수를 해볼 수 있겠다는 가능성을 함부로 배제하지 말자.
3. 이분 탐색
이분 탐색으로 찾을 대상이 없는 경우, 오차가 주어진다. 그 오차를 고려해서 마지막 한번 더 비교가 요구될 수 있다.
4. 재귀
하노이 탑
num = 0
def hanoi(n, start, target, sub):
if n == 1:
print(f'{start} {target}')
return
hanoi(n-1, start, sub,target)
print(f'{start} {target}')
hanoi(n-1, sub, target, start)
n = int(input())
print(2**n - 1)
if n <= 20:
hanoi(n,1,3,2)4. 우선순위 힙
가운데를 말해요
최대와 최소를 관리하는 두개의 힙이 존재함 → 풀이에 쓰이는 자료구조가 2개 이상일 수 있다.
WEEK REVIEW
- 성장은 확실히 진행중
1주차의 문제들을 많이 풀어보았지만, 아직도 실력이 많이 부족함을 느낀다.
특히, 이분 탐색과 재귀에 대한 보충이 필요한 것으로 파악된다.
그럼에도 불구하고, 많이 성장했음을 느낀다.
하면 할수록 더 잘하고 싶다는 욕심이 생긴다. 긍정적이고 고무적이다.
- 익숙함에 속지말자
2주차로 접어들면서 슬슬 정글에 익숙해지고 있다.
그러면서 초심을 잃거나 목표를 잊는 실수를 범하지 않도록 주의해야 할 것이다.
정글은 누가 하라고 강요하지 않는다. 그렇기에 내가 주체가 되어 나 스스로를 컨트롤해야만 한다.
정글에 온 이유 중 하나, 자기 주도 학습을 꾸준히 하는 법을 배우기 위해 이 곳에 왔다는 목표의식을 꾸준히 상기하자.
- 좋은 인간관계를 유지하는 것 역시 중요하다
개발자의 공부는 입시와 같이 나 혼자만의 공부가 전부가 아니다. 동료와 함께 고민하고 성장해야만 더 좋은 개발자로 거듭날 수 있다.
한편, 좋은 협업을 하는 사람의 전제 조건은 좋은 인간관계를 유지할 수 있는 사람이다. 그렇기에 인간관계에 노력과 시간을 할애하는 것에 대해 좀 더 관대해졌으면 좋겠다.
