카테고리 없음

코딩 테스트 기본 개념 복습

전한준 2025. 5. 31. 15:53

 

시간 복잡도 : 입력한 거에 따라 런타입이 어느 정도 들어가는  지 계산한다. 

공간 복잡도 : 입력한 거에 따라 메모리가 어느 정도 들어가는 지 계산한다.

 

 

O(1) : 이 가장 빠르다. 

O(logN) : 이진 트리인 경우 여러 개의 방향으로 생김

O(n^2) : matrix 를 풀 때 이용

 

 

2^10 ===> 1KB

2^20 ===> 1MB

2^30 ===> 1GB

2^40 ===> 1TB

 

 

 

String 불변 객체이다. (자바에서는 변경을 원한다면 StringBuilder를 사용하면 된다. )

String str = "ICON";

 

str.length();

str.charAt(2);

str.indexOf("o");

여기는 조금 더 나중에 자세히 쓰자.

 

 

 

Linked Lists

 

Singly Linked List 

각각의 노드가 그 다음 노드를 가리키고 있다. 

Doubly Linked List

각각의 노드가 서로 양쪽을 가리키고 있다. 

Circular Linked List

마지막 노드가 헤드 노드를 가리키고 있다. 

 

 

배열과 리스트의 차이 

ArrayList는 배열과 달리 연속적이지 않는다. 

그리고 저장소를 늘이고 줄이는 게 쉽다. 

(노드와 링크로 이루어 졌고 불연속적이다.) 

 배열과 달리   가변이다.

 

 

Binary Tree: 각각의 노드가 2명의 아이들을 갖고 있다. 

Binary Search Tree: 각각 트리가 가지고 있는 값이 왼쪽 부모 오른쪽 순으로 값 차이가 난다. 

AVL Tree: Height ( 리프 부터 셋을 때 높이의 값) 이 1이상 차이가 나지 않는 것들 

 

 

Heap 

이진트리로 구성되어 있다.

 

minHeap: root에 값이 가장작은 노드 (자바에서 기본이다.)

maxHeap: 반대로 root의 값이 가장 작은 노드이다. 

 

 

Inorder : left -> value -> right

Preorder : value -> left -> right

Post : left -> right -> value

 

힙의 삭제 ,삽입 O(logn)  min/max 는 뽑는다. (Peek min/max로 뽑는 O(1))

 

자바에서 

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(1);
pq.add(2);
System.out.println(pq.poll()); // 출력: 1

 

Python에서 

 

 

Graph 

루트 ,리프 개념이 없고 

노드랑 엣지만 있다. 

방향 그래프랑 무방향 그래프

각 엣지마다 weith가 있을 수도 있다. 

DAG : 방향은 있지만 사이클이 없다. 

 

사용예시는  DFS,BFD,Dijkstra's Algorithm , Topological Sort  등이 있다. 

다익스트라 : A point에서 B point 까지 가는 가장 짧은 경로는 무엇인가 이다. 

 

 

어떤 거랑 어떤 게 주로 연결이 되어 있나 ? 

vertex는 노드이다. 

 

List로 구현 한거 

 

 

matrix 로 구현하고 [row] [col ] 이고 col은 가로로 증가한다. 

 

Hash Map을 사용할때 

Key → Value 형태로 데이터를 저장하고, 빠르게 값을 찾고 싶을 때

  1. 빈도 수 계산
    • 예시: top K frequent elements, 문자 등장 횟수 계산 
    • 사용 이유: map.get(key)로 O(1) 시간에 빈도 증가 가능
  2. 빠른 조회 + 값도 함께 필요할 때
    • 예시: Two Sum 문제에서, 숫자와 인덱스를 빠르게 매핑할 때
    • map.containsKey()와 map.get()을 같이 씀
  3. 캐싱 (LRU Cache 구현 등-> 최근 검색)
    • key로 빠르게 value를 꺼내야 하므로 HashMap 필수
    • LinkedHashMap 같이 조합하여 LRU 구현 가능

Hash Set을 사용할때 

단일 값의 존재 여부 확인, 중복 제거 등

  1. 중복 존재 여부 확인
    • 예시: 배열에서 중복 원소가 있는지 확인
    • set.contains(value)를 통해 O(1) 시간에 체크 가능
  2. 배열에서 중복 제거할 때
    • Set은 중복을 허용하지 않기 때문에 자동 필터링
  3. 빠른 멤버십 확인이 필요할 때 (상태 방문 여부 등)
    • 예시: DFS/BFS 중 visited 상태를 저장
    • seen.contains(state) 형태로 사용

 

Stack 을 사용할때 

 

push,pop,peek,top,isEmpty() 

 

브라우저 히스토리 , DFS 탐구 , 포토샵 편집기 ,이전페이지 보기 , ()[]{} 이거 코테 문제 풀때

 

 

Queue / Deque 나중에 따로 자세히 공부하자 Deque는 Queue 랑 달리 양 옆에서 뺼 수 있는 거다. 

 

 

'카테고리 없음'의 다른글

  • 현재글코딩 테스트 기본 개념 복습

티스토리툴바