2021.11.10 WED
수욜 목표
내가 푼 알고리즘 복습 / 다시 써보기
상1 문제, 중 6문제 무조건, 하 29문제
컴퓨터시스템 교재 읽기
bfs ? 이거 다시 보기
시간복잡도를 계산하는 방법
저녁 플랜
단어정렬 - 일곱난장이
하노이탑 - Z - NQueen 훑기
기초 2~19번 복습/써보기
하노이탑 - Z - NQueen 제대로
공대생이 자주 쓴다는...^^
c 세타 : 각도 Γ
d 델타 : 변화량 (Δ 삼각형 모양으로 그림)
9663 N-Queen (재귀)
https://www.acmicpc.net/problem/9663
대각선으로도 세보면 총 15줄이 나온다
1514 하노이 탑 (재귀) / 1074 Z (재귀)
https://www.acmicpc.net/problem/1514
https://www.acmicpc.net/problem/1074
기타 메모
2021년 11월 10일 수요일
오늘의 TMI
목요일은 시험이었다
그래서 수요일 하루는 풀었던 알고리즘 코드를 복습하는데에 하루를 쏟았다
그래도 다시 보면 또 생각이 안나곤한다,, 😥
내가 아직 짬이 안차서 그런 듯 ㅎㅎ
1주차 팀원들과 일주일간 브레인스토밍 하듯 알고리즘을 해결해나갔다보니 나도 이제 혼자서도 풀이를 보면서 같은 문제를 풀어도 그럼 이럴 땐 어케 코드를 쓸까 하는 생각이 생겼다
그리고 복습을 하면서 든 생각인데
지난 5-6일간 문제를 푸는데만 급급했다.
내가 여유가 없었던 것이니 그럴 만도..
그동안 나름 과탑하면서 체득한 노하우는 교수님의 마음에 드는 답안지는 절대 꼼수를 쓰는 답안지가 아니라는 것이다
책 하나를 봐도 목록을 보면 그 작가가 책에서 뭘 말하고자 하는지를 파악 할 수 있다
정글 역시 주차마다 주어지는 키워드가 있다
WEEK01 : 정수론, 배열, 문자열, 재귀함수, 정렬, 완전탐색, 시간복잡도
잘 보면 문제를 다루는 주제 이외에 시간복잡도 라는 키워드가 같이 있다.
그리고 코치님께서 계속해서 recursion(재귀함수)에 대해 강조하신다.
나는 이걸 2주차가 끝나기 전에 무조건 터득해야 하는 것이다.
그래서 시간복잡도에 대해 더 공부해봤다.
시간복잡도
밑으로 갈수록 느린 순서
- O(N) : 리스트 등에서 값을 하나 찾을 때. for문으로 찾으니까,, n번 돌린다해서 O(N)
- O(NlogN) : 이진탐색, 퀵정렬, 병합정렬
- O(N²) : 반복문이 2개 중첩된 경우, 리스트 정렬 시 : 리스트에서 N만큼 찾고 그다음 다른 자리에 넣는 것 까지 O(N), 이걸 리스트 길이만큼 반복하니까 그래서 N x N = N²
- O(N³) : 반복문이 3개 중첩..
시간복잡도(최대 경우의 수) 계산
EX1 )
1 ≤ N ≤ 1000 이면 N을 1000(최대개수)으로 보고
문제에 들어갈 연산이 뭐 있는지 생각
for i in range(n): 이 있으면 for문이 1000번 돎
for j in range(n): 반복문이 2개 있으면 결국 1000*1000번을 돌게됨
→ 1,000,000 ⇒ 이 프로그램은 최악의 경우 백만번 돈다
1초에 천만or백만 도는거랑 해서 계산 (끝)
EX2) 백준 10819 https://www.acmicpc.net/problem/10819
N (3 ≤ N ≤ 8) 순열 문제일 때
최대 8개의 숫자 배열(리스트)를 받을 수 있으니까
8 7 6 5 4 3 2 * 1 가지의 경우 → 4만 몇 가지..의 경우의 수가 있다
그래서 이건 시간 안에 되겠다 (끝)
자세히 티칭해준 원종이와 종호오빠 넘넘 감사감사.......
ㅎㅎ
그래서 내가 5개월동안 꼭 기억해야 할 사항이 추가되었다
주차별 키워드를 잊지 말 것
생각난김에 0주차에 나온 키워드인 서버사이드렌더링 이랑 JWT jinja2를 제대로 다시 보고싶은데
시간이.........시간이..
오늘꺼 하기에도 벅차다.. 아직 많이 느리다.
사실 복습한다고 10일차에도 3시에 들어감 ㅎㅎ;;; 그래도 부족해
그러니 뭐든 미루면 안된다
계획한 것은 이틀 내에 다 실행하자.
DAY10 끝. 내일 조 바꾸는데 좋은 조원들과 정들어서 벌써 아쉽다.
