재귀함수? 재귀함수란 자신을 정의할 때 자기 자신을 재참조하는 함수를 뜻한다 예시 1. 팩토리얼 구현 def factorial(n): if n == 1: return 1 return n * factorial(n-1) 2. 피보나치 수열 구현 def fibo(n): if n == 1 or 2: return 1 return fibo(n - 1) + fibo(n - 2) 💡 피보나치 수열?? https://m.blog.naver.com/prayer2k/222432519342 토끼의 번식에 관한 문제에서 시작되었다. 처음에 한쌍의 토끼가 있고 두 달이 지나면 번식이 가능하다고 해보자. 또한 이 토끼들을 죽지 않는다고 하였을 때 처음엔 한쌍, 두달이 지나면 두 쌍 다시 두달이 지나면 세쌍(처음 한쌍이 2달이 지나..
coding test
해시테이블 코테 적용 방법 메모리를 활용해서 시간복잡도를 줄이자! key in { } 가 핵심! 문제 해석 [100, 4, 200, 1, 3, 2] 이 숫자들을 사용해서 연속된 수를 만들어야한다. 연속된 수를 만들 수 있는 경우의 수는 [1, 2, 3, 4] 이다 [1, 2, 3, 4]가 가장 길기 때문에 4를 리턴해야한다. [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] 두번째 예시에서 문제는 0이 두번 있다는 것이다. 하지만 연속된 수를 찾을 때는 0이 한번만 들어가기 때문에 조심해야한다 제약 조건 nums가 커지면 커질수록 시간복잡도가 높아진다. 여기선 10^5승까지로 되어있는데 O(n^2)인 시간복잡도로는 시간 초과가 난다. 즉 완전 탐색같은 알고리즘은 쓸 수 없다. 또한 0일 수도 있는데..
문제 접근방법 원래는 완전 탐색(하나하나 탐색하기)식으로 문제를 풀었지만 이제는 접근을 똑똑하게 해보자. 컴퓨터가 아니라 암산으로 이 문제를 푼다고 하면 저 숫자들을 머리속에 저장해놓고 딱 한번만 보면서 풀 수 있을 것이다. 컴퓨터 상에도 메모리라는 머리속이 있기 때문에 거기에 저장해놓고 푼다고 생각하면 된다 풀이 def two_sum(nums, target): memo = {} # 딕션어리 만들기 for v in nums: # nums를 돌아가면서 딕션어리에 저장 # 이때 키값은 nums이고 벨류값은 1 # O(1)의 시간복잡도로 바로 키값 조회 가능 memo[v] = 1 #--------여기까지가 딕션어리저장---------- for v in nums : # v 값이 4이고 target이 14일때 필..
1. 해시테이블 종류 Array list based (Open addressing) => 파이썬에서 구현해 놓은 해시테이블 Array list + Linked list based (Seperate chaining) Find key O(1) 괄호에 들어간 내용은 해시테이블에서 나는 충돌을 해결하는 방법 (기술면접에서는 중요함) 2. 해시테이블? 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value 쌍의 데이터를 입력받는다. hash function h이 key 값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장합니다. 저장, 삭제, 검색의 시간 복잡도는 모두 O(1)입니다. 2-1. 예시 해시테이블은 어쨋든 list라서 인덱스가 있다. 해시테이블에서 인..
1. 문제 이해하기 temperatures 배열은 온도를 나타낸다 73도 에서 더 따뜻해 지는 날은 바로 다음날 74도로 1을 반환한다 다음날 74도에서 따뜻해 지는 날은 75도 하루면 된다 1 반환 다음 75도에서 더 따뜻해지는 날은 76도로 4일을 기다려야한다 . . . 마지막 이틀은 따듯해지는 날이 없기 때문에 0을 반환한다 제약조건 첫번째 제약조건은 temperatures의 원소가 많으면 많을 수록 시간 복잡도에 영향을 준다 즉 이 조건은 O(n^2)으로 풀지 말란 뜻임(10^8 을 넘어가면 안되기 때문에) 두번째 제약조건은 온도가 30도부터 100도까지임 2. 코드 설계 def daily_temperatures(temperatures): # teperatures의 길이만큼 0으로 초기화 # 저장..
Valid parentheses(괄호 유효성 검사) 1. 문제이해하기. 즉 괄호가 잘 열고 닫혔는지를 판단해야한다 제약조건 10^4 까지로 되어있으니까 n^2의 시간복잡도는 제외해야함(예를 들면 2중 반복문 같은거) 2. 접근방법 단순화 해보기 () : 유효 )(): 비유효 )( : 비유효 여는 괄호가 있으면 닫는 괄호가 있어야한다. 괄호의 개수는 짝수여야한다 항상 처음은 여는 괄호여야한다 확장 그러면 이걸 어떻게 판별하냐? 여는괄호 : +1 닫는 괄호: -1 예시 : () (()) ( : 1 ) : 0 --- ( : 1 ( : 2 ) : 1 ) : 0 즉 짝이 맞으면 값이 0 으로 끝난다 만약 0 이상으로 나오면 여는 괄호가 더 많았을 것으로 invaild 만약에 여는 괄호가 먼저 시작을 안하고 닫는 ..
1. Queue 먼저 저장한 데이터가 먼저 출력되는 FIFO형식으로 데이터를 저장하는 자료구조이다 enqueue Queue 뒤(rear)에 데이터를 저장하는 것 dequeue Queue 앞(front)에 데이터를 저장하는 것 1-1. LinkedList / ArrayList 큐는 보통 링크드 리스트로 구현한다 왜 어레이 리스트를 쓰지 않을 까??? 예를 들어보자 1부터 6을 하나씩 넣는다고 가정했을 때 enqueue(추가)할때는 뒤에서 apend함수로 넣어주면 되지만 dequeue 할때는 앞에서 하나씩 빼줘야 하기 때문에 뒤에있는 숫자들을 한칸씩 앞으로 옮겨줘야하는 상황이 발생한다 그래서 어레이 리스트로 구현했을 경우 enqueue는 O(1)의 시간복잡도를 가지고 dequeue는 O(n)의 시간복잡도를 ..
Linked List 구현 1. 문제 이해 1-1. 예시 우리가 흔히 작동 시키는 url 방문, 앞으로가기, 뒤로가기를 작동시키면 된다. 게임중에서 시장에 가면을 생각하자 input과 예시를 같이 보면 이해가 쉽다 1. 리트코드 접속 (홈페이지) 2. 구글 접속 ( 리트코드 -> 구글) 3. 페이스북 접속 ( 리트코드 -> 구글 -> 페이스북) 4. 유튜브 접속 (리트코드 -> 구글 -> 페이스북 -> 유튜브) 여기 까지는 모두 None을 반환한다 즉 반환값이 없다 5. 뒤로가기 한번 (유튜브 전 페이지인 페이스북 접속) 페이스북 주소 반환 6. 뒤로가기 한번 (페이스북 전 페이지인 구글 접속) 구글 주소 반환 7. 앞으로 가기 한번 (구글 앞 페이지인 페이스북 접속) 페이스북 주소 반환 8. 링크드인 ..
