본문 바로가기

내맘대로 코딩32

[08-1] 재귀(Recursion)란? 재귀. 파이썬 공부를 할 때, 재귀함수를 배우면서 아~뭔지 알겠다 하면서도 딥~하게 들어가면 정신을 못차렸다. 그래서 거리를 두고 지냈는데 재귀는 코딩 테스트에서 단독으로 나올정도로 중요하다. 그리고 이진탐색, 깊이, 완전 탐색 등 많은 부분에서 응용되어 활용된다. 트리, 그래프에서도 사용되니.. 재귀가 얼마나 중요한지 알겠지? 재귀함수란? 자기 자신을 재참조 하는 함수를 뜻한다. 재귀함수의 구성요소는 2가지가 있다. 1. 점화식: 호출하는 관계식으로 f(n) = f(n-1), f(n-2)... 이렇게 계속해서 표현하는 것 2. base case: 호출하지 않아도 게산값을 반환하는 상황 코드로 살펴보자. def factorial(n): if n==1: return 1 #base case return n*.. 2023. 11. 15.
[07-3] 해시 테이블을 활용해보자 이번에는 해시 테이블을 어떻게 활용하면 좋을지, 언제 활용하면 좋을지 알아보자. 특징: 1. "key:value" 쌍으로 저장 2. O(1)의 시간 복잡도로 복잡도가 낮음 3. in 을 활용할 수 있음 4. 추가, 수정, 불러오기 기능이 탁월 이러한 특징을 고려했을 때, 해시 테이블의 활용도는 정말 무궁무진하다. 1. 검증할 때 ⇒ 있는지, 해당 부분이 있는지, 맞는지 이렇게 검증할 때 쓸 수 있다. 이 부분이 가장 강력하다. 해당 부분을 '검증' 이란 키워드로 표현해서 이해하기 어려울 수 있는데 쉽게 설명하면 다음과 같다. 2. 리스트를 쓸 수 있지만, 시간 복잡도를 고려해야할 때 배열 중 2개의 숫자를 더해서 M가 만들어지면 True, 아니면 False를 출력해라 의 문제에서 포인터를 쓸 수도 있고,.. 2023. 11. 15.
[07-2] 해시 테이블(Hash Table)이란? (2) 앞서 해시 테이블의 정의와 간단한 사례를 봤다면, 언제 써야하는지? 어떤 연산이 중요한지 살펴보겠다. 그 전에 한번 요약정리 하고 넘어가보자. 1. key-value쌍이다 2. key를 index로 매칭하는 과정에서 hashfunction이 활용된다. 이유는 최적화와 효율성의 문제 3. 하지만 복잡하게 신경쓰지 말자. 파이썬에서 알아서 해주니, 우리는 key-value만 이해해도 충분하다!(적어도 코테에서는..) 해시 테이블의 대표적 사례는 딕셔너리이고, 딕셔너리의 장점을 확인해보자. 내가 운동 루틴을 만들어보려고 한다. 운동은 유산소, 가슴, 허리, 등, 유산소 의 순서로 이어진다. #오늘의 운동 루틴 만들기(리스트) routine = [30, 15, 60, 30, 10] #유산소, 가슴, 허리, 등,.. 2023. 11. 14.
[07-1] 해시 테이블(Hash Table)이란? (1) 해시 테이블은 코딩 테스트에서 사실상 필수적으로 나온다. 또한, 굉장히 강력한 자료구조 이다. 사용방법은 매우 간단하지만 언제? 어떠한 상황에서 활용해야 하는가? 를 판단할 줄 알아야 올바르게 본 자료구조를 활용할 수 있다. 사실 해시 테이블은 우리가 자주 활용하고 있다. 바로 Dictionary 구조가 해시 테이블이기 때문! 파이썬 코드를 작성하면서 딕셔너리 구조를 최소한 한번은 활용해보았기에 이번 해시 테이블 구조의 친밀감(?)은 다른 파트보다는 수월했다. 해시 테이블의 구현 방법은 크게 2가지 방법이 있다. 1. Array list: 파이썬의 딕셔너리 2. Find key: 코딩테스트에서 어떻게 딕셔너리를 활용할 지 참고용으로, 해시 테이블에서는 충돌이 발생하는데 이를 어떻게 해결할 것인가는 어떤 .. 2023. 11. 14.
[06-2] Stack은 어떻게 쓸까? 너무 익숙한 Stack. 그러면 Stack은 어떻게 쓸 수 있을까? 1. LIFO를 활용하는 문제들에서는 당연히 Stack을 쓴다. 2. DFS(깊이 우선 탐색)에서 사용된다. [재귀] * 대표적으로 유효성 문제 에서 Stack을 쓴다. A = ()[(())]{[]} 이게 유효한지 검사할 때를 생각해보자. 어떻게 해야하지? +1, -1 해서..0으로 할까? 이런 생각부터 시작하는 것이다. 하지만 그게 말이될까? ( ] 하면 0이되는데.. 어떡하지? 이렇다보면 아! LIFO 으로 하면 되는구나! 생각이 들것이다. 이렇게 생각을 할 수 있는 것이 코딩적 사고다. * 조건이 필요할 때 Stack을 쓴다. 예를 들어서, 다음 숫자보다 커질 때 까지 몇일이 걸리는지? [13, 15, 7, 9, 14, 17] ⇒[.. 2023. 11. 9.
[06-1] 스택(Stack)이란? 스택까지 왔다. 스택은 앞서 배웠던 Array, Queue와 달리 단독으로도 많이 나오는 유형이다. 그리고 다른 알고리즘, 자료구조에서도 많이 나온다. 그래서 스택은 꼭 꼭 알아두어라. 그렇다면 스택은 왜 자주 출제되고 사용되는가? 이유는 간단하다. Array list based로 제작되기 때문이다. 우리가 리스트는 참 많이 쓴다. 그래서 Stack 도 자연스럽게 쓴다는 것~ 그래서 많이 나오게 되는 것이다. Stack에 대해 알아두어야 할 내용은 다음과 같다. 1. LIFO(Last in First Out) 후입선출 2. 스택에서 top에 데이터를 추가하는 것을 push, top에서 데이터를 추출하는 것을 pop 이라고 한다. 여기까지만 봐도 우리가 일반적으로 사용하는 리스트와 매우 유사하다는 것을 확.. 2023. 11. 9.

티스토리툴바