본문 바로가기
[📚누구나 자료구조와 알고리즘] 12-1. 동적 프로그래밍 - 불필요한 재귀 호출 줄이기 재귀는 때로 O(2^N)과 같이 느린 빅오의 원인이 된다. 배열의 최댓값을 구하는 예제 코드로 재귀가 때로 얼마나 많은 비효율적인 호출을 만들어보는지 확인해볼 수 있겠다. def get_max_value(arr): if len(arr) ==1 : # 만약에 인수로 들어온 배열 원소의 갯수가 1개라면 return arr[0] # 최댓값은 해당 원소일 것이다 if arr[0] > get_max_value(arr[1:]) : # 만약 배열의 첫 원소가 나머지 모든 원소들의 최댓값보다 크다면 return arr[0] # 최댓값은 배열의 첫 원소일 것이다. else: # 만약 배열의 첫 원소가 나머지 원소들의 최댓값 보다 작다면 return get_max_value(arr[1:]) # 나머지 원소들 중의 최댓값이.. 2022. 10. 14.
Week02-03. 정말 최선을 다하고 있나. Week02 회고를 쓰지 못했다. Week02를 시작하고 Week03이 끝난 오늘까지도 회고 쓸 시간이 없었다. 정확히는 시간이 없었던 게 아니라 회고를 쓸 마음의 여유가 없었다. 2-3주차 모두 나보다 실력이 뛰어난 팀원들과 함께 팀을 이뤘는데, 팀원들과 속도를 맞춰야 한다는 부담감이 있었다. 정글의 알고리즘 주차에서는 중간 중간 팀원들과 코드 리뷰를 하는데 상대적으로 문제를 푸는 속도 느린 나는 코드 리뷰 속도를 맞추기 위해 매일 매일이 조급했다. 2주차에는 27문제, 3주차에는 23문제를 풀었어야 했는데 2-3주차 모두 4문제를 풀지 못했다. 이 블로그를 보시는 분들이 오해하실까봐 덧붙이자면, 정글에서 제공하는 문제를 오롯이 자기의 힘으로만 풀어야 하는 것은 아니다. 인터넷에서 답을 찾아봐도 되고,.. 2022. 10. 14.
Week01. 알고리즘 파티 + 최적의 공부 방법을 찾아서 Week01 금요일에 처음 백준 문제를 풀기 시작했는데 수요일에 6일만에 백준 실버가 되었다. (그 3일 뒤에 실버4로 또 레벨업ㅎ) 여러분 정글이 이렇게 무서운 곳입니다… 알고리즘을 많이 접해본 사람이라면 더 빠르게 레벨업할 수도 있겠지만, 나의 경우 알고리즘 경험이 거의 없어 하루에 13시간씩 풀었어야했다. 우리 조 모두 비슷한 실력이어서 첫 날에 input() 받는 것 조차 구글링을 하는 단계였는데, 하루하루 하면서 다들 조금씩 실력이 늘어가는 게 눈에 보였다. 알고리즘 커리큘럼을 좀 설명하자면 정글 Week01 부터는 4주동안 자료구조/알고리즘 주차이다. 이 주차들을 거치며 '어떻게 컴퓨터에게 일을 시킬 것인가'를 익히게 된다. WEEK01: 배열, 문자열, 반복문과 재귀함수, 계산복잡도, 정렬,.. 2022. 10. 3.
Week00. 쉴 틈이 없다. 사실 Week00 회고는 지난 주에 작성할 계획이었는데, 정글이 이렇게까지 바쁠지 몰랐다 ㅎ 그래도 간단히 00주차를 돌아보고자 한다. 정글에서는 목요일 ~ 수요일을 한 주로 친다. (정확히는 목요일 오후 ~ 그 다음주 목요일 오전 이 한 주) 월요일에 입소한 우리는 수요일까지 3일간 0주차를 보내게 되고, 정글에서의 4일째가 되는 목요일에 비로소 1주차를 시작한다. 1주차 시작 전 보내는 이 3일간, 사람들과 친해지기도 하고 주변 구경도 하고 그럴 것만 같지만, 우리 반 모두가 아마 0주차 때 가장 잠을 못 잤을 것이다. 다른 동기 한 명은 0주차 때 3일동안 총 10시간만 잤다고 한다. ㅎ 정글에서의 생활이 궁금해서 나의 블로그를 찾아오시는 분들도 많으니 가능한 한 자세히 기록해보겠다. 1일차 (월).. 2022. 10. 1.
[정글 TIL] 유클리드 호제법 , 재귀 알고리즘 오늘은 랜덤런치 날이라 다른 조원들과 함께 점심 식사를 했는데, 대부분 재귀함수에서 벗어나지 못하고 있었다. 나도 마찬가지라 (^.^) 재귀함수 문제 풀다가 도저히 공부없이는 해결을 못 할 것 같아서 교재를 펴서 재귀 알고리즘을 공부하기 시작했다. 재귀 알고리즘의 예제로 '유클리드 호제법'이 나왔는데 알고리즘은 고사하고 그냥 유클리드 호제법 자체가 이해가 안 가서 유클리드 호제법부터 공부했다. 어차피 이번주차 공부해야 할 내용중에 정수론도 있어서 겸사겸사 함께 공부! 유클리드 호제법은 youtube에서 쑤튜브 채널 영상을 참고해서 이해했다. 유클리드 호제법 유클리드 호제법은 A와 B의 최대공약수는 B와 A를 B로 나눈 나머지의 최대공약수와 같다는 것이다. 즉, A = qB + r 이라면 (q는 몫, r은.. 2022. 9. 26.
[정글 TIL] Week01 | 입출력, 산술연산자(/,//,%) 나의 TIL은 Today I Learned가 아닌 This week I Learned :-) 지난 기수 분들의 TIL을 보면, 대부분 10주차 정도까지만 TIL을 쓰시고 대부분 자취를 감추시더라. 하지만 정글에서 7일째를 보내고 있는 난 이제 알 것 같다. 그 분들이 초심을 잃거나 귀찮으셨던게 아니라 더이상 TIL을 쓸 시간조차 없으셨다는 것을..ㅎㅎ 나도 주차가 진행될 수록 바빠지겠지만 최대한 매주 배웠던 내용들을 정리하고 매 주마다의 깨달음과 마음가짐 등을 마지막 주차까지 꼭 적어보도록 노력해봐야지! 어쨌든 fresh한 마음으로 첫 TIL을 시작해본다! 이번 주부터 4주 간은 자료구조와 알고리즘에 대해 공부하고, python 언어로 백준 알고리즘 문제를 푼다. 나는 주로 javascript로 개발을 .. 2022. 9. 26.
[Week01] 특별한 과제. 나를 돌아보는 시간과 정글에서의 목표 정글에서 특별한 과제를 내주셨다. 지나온 과거를 성찰하고, 앞으로 다섯 달 동안 내가 얻어가고 싶은 것, 어떤 자세로 임하고 싶은지, 정글이 끝난 후 나의 모습은 어땠으면 좋겠는지를 생각한 후 이를 에세이로 작성해야 하는 과제이다. 사실 정글 과정을 준비하는 과정에서 여러 번 생각해 본 내용들이었는데, 이번 기회에 글로 한 번 잘 정리해보려 한다. 지나온 과거 난 태생적으로 욕심이 많은 사람이었다. 하고 싶은 것도, 이루고 싶은 것도 많은 사람. 욕심보다는 야망이라는 단어가 더 잘 어울릴지도 모르겠다. 나의 욕심은 '바라는 모습이 되지 못하면 어쩌지'라는 두려움을 항상 수반했기에 나를 발전시키는 원동력이기도 했지만 나 자신을 있는 그대로 받아들이지 못하게 하며 자존감을 해치는 칼날이기도 했다. 서른을 목.. 2022. 9. 24.
[📚누구나 자료구조와 알고리즘] 4. 버블 정렬과 O(N^2) 정렬이란 단어는 알고리즘을 몰라도 이미 익숙한 단어이다. 엑셀에도 여러 값이 있는 자료를 '정렬'하면 해당 값들이 오름차순 또는 내림차순으로 정렬된다. 정렬 알고리즘도 이와 같이 '정렬되지 않은 배열을 오름차순으로 정렬'하는 방법들이다. 컴퓨터 과학분야에서 오랜 기간동안 다양한 정렬 알고리즘들이 연구 & 개발되었다. 버블 정렬 (Bubble sort) 그 중 가장 기본적인 (그리고 상대적으로 비효율적인) 정렬 알고리즘인 버블 정렬은 아래 gif와 같이 진행된다.(출처) 버블정렬은 원소를 순서대로 두 개씩 비교하면서, 왼쪽 값이 오른쪽 값보다 큰 경우 두 값을 서로 교환하고(swap), 그렇지 않으면 그대로 둔다. 그 다음 오른쪽으로 한 칸 이동해서 똑같은 작업을 수행한다. 이렇게 가장 오른쪽 원소까지 이.. 2022. 9. 13.
[📚누구나 자료구조와 알고리즘] 3. Big-O Notation : O(N), O(1), O(logN), O(N^2) 빅오 (Big-O) 컴퓨터 과학자들이 알고리즘의 효율성(시간복잡도)을 표기하기 위해 수학적 개념을 차용한 방법이 빅 오 표기법이다. [1] 원소가 N개일 때, 알고리즘에 최대 몇 단계가 필요할까? [2] 원소가 N개일 때, 원소가 늘어남에 따라 알고리즘에 필요한 단계 수가 어떻게 늘어날까? 중요 ! 빅오표기법은 결국 위의 질문에 대한 답을 O()의 괄호 내에 나타내는 것이다. O(N) 선형검색 알고리즘의 경우, 최악의 경우 원소 갯수 만큼의 단계가 필요하다. 예를 들어 100개의 원소 중 찾는 원소가 맨 마지막에 있거나, 없는 경우 100번을 모두 검색해야 하기 때문이다. 고로 선형검색을 위의 1번 질문에 대입해보자면 (= 원소가 N개일 때, 선형 검색에는 최대 몇 단계가 필요할까?) 답은 N 이다. 이.. 2022. 9. 13.
반응형

티스토리툴바