본문 바로가기

코딩 테스트15

[09-1] 트리(Tree)란? 벌써 트리구조까지 왔다. 트리(Tree)구조는 말그래도 트리모양으로 생각하면 된다. 가지치기 된 모양이다. 그림으로 이해해보자. 트리란? 서로 연결된 노드의 계층형 자료구조이며, 부모-자식 관계로 구성되어 있다. 트리를 올바르게 이해하기 위해선 용어들을 이해해야 한다. - 각 노드들이 있고, 노드들을 연결해서 트리를 만든다. - 루트노드(root): 맨 처음(시작) 노드(A) - 리프노드(leaf): 더이상 뻗어나갈 수 없는 노드 - 자식노드(child), 부모노드(parent), 형제노드(sibling): 계층 구조를 확인하며 상대적 개념 - 차수(degree) : 노드가 갖는 자식의 수. 모든 노드가 n개 이하의 트리를 가진 n진 트리라고 정의.(그림은 3진 트리) - 높이(height): 가장 멀리.. 2023. 11. 15.
[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.

티스토리툴바