매일 성장하는 블로그

1. 문제

  매우 유명한 (알고리즘 풀이 입문 시 자주 맞닥뜨리는) 문제이다.

정수들이 담긴 배열 nums와 목표 target이 주어질 때, 배열 nums 내의 특정 두 수의 합은 target이 된다.

해당 두 수의 index를 return해라.

2. 풀이

  2가지 풀이 방법으로 풀어보자.

  1) Two Pointer : 두개의 포인터를 가지고 배열을 탐색하는 기법이다.         a. 배열을 오름차순으로 정렬한다. 이 때, 기존 idx를 보존할 수 있도록 [num, idx] 형태로 저장 후 정렬한다.     b. 두개의 포인터(left = 0, right = len(nums)-1)를 만들고 합(nums[left][0] + nums[left][1])을 구한다.     c. (반복) 합이 target보다 작은 경우 left를 오른쪽으로 한칸, 클 경우에는 right를 왼쪽으로 한칸 이동시킨다.     d. 합이 target과 일치하면, 두 수의 idx를 반환한다.

  시간 복잡도 : O(nlogn)

  공간 복잡도 : O(1)

  2) Hash Map :  배열을 순차적으로 탐색하며 확인한 내용을 해시 맵에 기록한다. Two Pointer 보다 속도가 빠르지만, 메모리를 추가적으로 사용한다.

    a. nums를 순차적으로 탐색하며 아래의 과정을 수행한다.      탐색 과정의 정수 : num      a-1) Hash Map의 key들 중 num이 있는지 확인한다.      a-2) 있다면 해당 key의 value와 num의 idx를 return하고, 없다면 Hash Map에 key : target - num. value : idx 로 기록한다.          시간 복잡도 : O(n)    공간 복잡도 : O(n)

알고리즘 문제 풀이를 1년 전에 1~2달 동안 열심히 했었지만, 안 푼지 오래되니 생각이 잘 나지 않는다. 꾸준히 해야할 것 같다.

부트캠프 진행 시에는 매주 특정 주제를 정해서 관련된 문제들을 풀었는데, 이렇게 푸는 방법이 꽤 괜찮은 것 같다.

여기에 더해서 아래 영상에 나온 방식을 가지고 알고리즘 풀이를 연습할 예정이다.

1. 문제와 문제의 Topic을 적는다.

2. 문제의 풀이방식을 적는다.

3. 다음 문제를 풀 때 같은 Topic의 풀이들을 살펴본다.

영상에서 말하는 바는, 같은 Topic의 문제들은 비슷한 방법으로 풀린다는 것이다.

우선 아래 영상에서 추천하는 75문제를 먼저 푼 뒤, 주차별로 관련 문제들을 학습해보자. 올해도 화이팅-!

https://www.youtube.com/watch?v=SVvr3ZjtjI8 

1. 문제

  LinkedList A(size : m)와 B(size : n)와 변수 a,b(a,b<m)가 주어질 때, 리스트 A의 a번째 원소부터 b번째 원소를 잘라내고, 그 공간에 LinkedList B를 연결하는 함수를 만들어라.

ex) 

A : 1 -> 2 -> 3 -> 4

B : 10 -> 11

a : 1

b : 2

=> A의 두번째부터 세번째 원소를 잘라내고, 그 공간에 B를 갖다 붙인다.

output : 1 -> 10 -> 11 -> 4

2. 방법

  1) A의 자르는 위치의 시작점(aStart), 끝점(aEnd)을 기록한다.

  2) aStart의 next에 bStart를 연결, bEnd의 next에 aEnd를 연결한다.

3. 풀이

class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        #시작점 기록
        aStartIdx = a - 1
        aStart = list1
        while(aStartIdx > 0 and aStart.next):
            aStart = aStart.next
            aStartIdx -= 1
        
        #끝점 기록
        aEndIdx = b + 1
        aEnd = list1
        while(aEndIdx > 0 and aEnd.next):
            aEnd = aEnd.next
            aEndIdx -= 1
        
        #시작점 연결   
        bStart = list2
        aStart.next = bStart
        
        bEnd = list2
        while(bEnd.next):
            bEnd = bEnd.next
        
        #끝점 연결
        bEnd.next = aEnd
        
        return list1

Search : 어떤 조건을 만족하는 데이터를 찾아내는 것

고려해야 할 사항 : 추가/삭제 같이 검색 이외의 작업에 들어가는 비용, 주어진 자료구조, 데이터의 형태 등을 종합적으로 평가하여 최적의 검색 알고리즘을 선택해야 한다. 배열이 주어지고 그 안에서 특정한 Key값을 찾는다고 할 때, 아래와 같은 방법들을 고려할 수 있다.

선형 검색(Linear Search)

무작위로 주어진 데이터에 대하여 순차적으로 검색하는 방법. 검색 시간이 데이터의 크기에 선형적으로 비례한다.

방법 : 맨 앞, 혹은 맨 뒤부터 순차적으로 Key 값을 찾는다.

종료 조건 : 1. Key와 일치하는 원소를 찾은 경우

                2. 배열의 길이를 넘어선 경우

시간복잡도 : O(n)

* 보초법 : 배열의 맨 끝에 찾는 원소를 추가하여 매번 배열의 끝인지 확인할 필요를 줄이는 방법.

이진 검색(Binary Search)

정렬된 데이터에 대하여 효율적으로 검색할 수 있는 알고리즘. 한번 비교를 수행할 때마다 비교 대상의 데이터 수가 반으로 줄어든다.

방법 : 맨 왼쪽 끝 원소의 Index를 Left, 맨 오른쪽 끝 원소의 index를 Right라고 한 뒤, Center의 값과 Key값을 비교한다. 대소 여부에 다라 Left, Right 값을 변경한다.

종료 조건 : 1. a[Center]가 key와 일치하는 경우

               2. 검색 범위가 더이상 없는 경우

시간복잡도 : O(logn)

해시(Hashing)

데이터를 저장할 위치를 해시 함수를 사용하여 결정하는 방법. 키값을 해시 함수를 통과시켜 해시값을 얻어낸 뒤, 해시값에 해당하는 인덱스에 키를 저장한다. 키를 해시값으로 변환하는 함수를 해시 함수, 해시 테이블에서 만들어진 원소를 버킷이라고 한다.

해시 함수의 예시 : 13으로 나눈 나머지

위와 같은 해시 함수에 대하여 같은 해시 값을 가진 키가 존재하는 경우 충돌이 일어날 수 있다. 예를 들어, 14도 13으로 나눈 나머지가 1이고, 27도 13으로 나눈 나머지가 1이기 때문에 해시 값이 같은 Key가 존재하게 된다. 이를 해시 충돌이라고 하고, 다음과 같은 두가지 방법으로 처리한다.

1) 체인법 : 해시값이 같은 원소를 연결 리스트로 관리한다.

2) 오픈 주소법 : 버킷이 가득 찬 경우를 대비하여, rehash 함수를 정의한다. 이후 가득찬 버킷에 추가할 일이 생기면, 빈 버킷을 찾을 때까지 rehash를 반복한다. 

  Dynamic Programming(동적 프로그래밍)은 구하고자 하는 최적해가 부분문제들로 이루어져있고 부분문제들이 또다른 작은 부분문제들로 이루어졌을 때 풀이시간 단축을 위해 사용된다. 반복되는 부분문제들을 한번씩만 계산하여 저장한 뒤, 저장한 값을 사용하여 중복되는 부분문제들의 계산을 줄이는 방법이다. 저장된 값을 재사용함에 따라 풀이시간은 감소하지만, 저장하는 값들의 공간만큼 메모리 공간이 더 소모된다는 단점이 있다.

DP 문제를 풀때의 일반적인 접근은 아래와 같다.

1. 최적해의 구조적 특징을 찾는다.

2. 최적해의 값을 재귀적으로 정의한다.

3. 최적해의 값을 Bottom-Up으로 계산한다.

4. 계산된 정보들로부터 최적해를 구성한다.

정의만 읽어보면 두루뭉실하니, 예제를 보면서 이해해보자.

Problem : 피보나치 수열의 N번째 숫자를 구하라.

1. 피보나치 수열의 구조적 특징 : n번째 숫자는 n-1번째 숫자와 n-2번째 숫자를 더한 값이다.

2. 최적해의 값을 재귀적으로 정의한다.

def fib(n):
    if n==1 or n==2:
    	result = 1
    else:
    	result = fib(n-1) + fib(n-2)
    return result

  이 상태로도 풀이가 가능하지만, 시간초과 / Recursion Limit 초과로 불가능한 경우가 많다. 위의 코드대로 풀이를 진행하면, fib(5)를 구할 때 아래와 같이 반복된 계산을 수행하게 된다.

  따라서, 현재 구현된 재귀 방식의 시간복잡도는 O(2^n)이다. 계산 횟수를 줄이기 위해 계산값들을 memo라는 배열 안에 저장하고, 저장된 값들을 사용해보자.

def fib(n):

    memo = [0, 1, 1]
    memo.extend([0 for _ in range(n)])
    
    def find(n):
        if memo[n]:
            return memo[n]
        else:
            result = find(n-1) + find(n-2)
            memo[n] = result
        return result

    return find(n)

  우선 memo라는 배열을 만들어준 뒤, 계산한 값은 memo[n]에 저장한다. memo[n] 값이 존재하는 경우, 계산하지 않고 바로 이 값을 사용한다. 이렇게 중복되는 부분문제들의 결과값을 저장하여 사용하는 방법을 Memoization이라고 한다.

위와 같은 방식의 시간복잡도는 O(n)이 된다.

3. 최적해의 값을 Bottom-Up으로 계산한다.

  위와 같은 방법은 재귀적으로 호출하기 때문에 Max Recursive Limit에 걸리는 문제가 발생할 수 있다. 따라서 그냥 1부터 n까지 순차적으로 memo 배열을 채워가는 방식을 생각할 수 있는데, 이를 Bottom-up 방식이라고 한다. 재귀를 사용한 것보다 더 간단하고, 빠르다.

def fib(n):

    memo = [0, 1, 1]
    memo.extend([0 for _ in range(n)])
    
    for i in range(3, n+1):
        memo[i] = memo[i-1] + memo[i-2]

    return memo[n]

물론 피보나치보다 더 어려운 문제들을 접할 때는, 최적해의 구성을 통해 부분문제들을 정의하는 것이 매우 어려울 때가 많다. 추후 다른 문제들 Review를 통해 알아본다

위상 정렬이란, 비순환 방향 그래프를 순서대로 정렬하는 방법이다.

1. 위상 정렬 조건

* 비순환 : 그래프에 시작과 끝이 존재해야 한다.(순환 가능하면 안된다.)

* 방향성 : 노드들 사이에 방향이 존재해야 한다.

2. 위상 정렬 특성

* 위상 정렬을 사용하여 정렬된 결과는 여러가지가 있을 수 있다.

3. 방법

위와 같은 그래프의 모든 노드를 방향에 따라 순서대로 방문한다고 할 때, 위상 정렬은 아래와 같은 간단한 성질을 이용한다. 

특정 노드로 들어오는 간선(Edge)이 없다면, 방문 가능한 상태이다.

위의 성질을 이용하여, 아래와 같이 구현할 수 있다.

1. 방향 정보를 저장하는 배열을 생성한다.

주어진 방향 정보 : (1 → 2), (2 → 3), (2 → 4), (3 → 4), (4 → 5)

dir_list = [[1, 2],[2,3], [2,4], [3,4], [4,5]]

2. 각 노드들로 들어오는 간선의 개수(진입 차수)를 저장한다.

ex) 1번 노드로 들어오는 간선 : 0개

     2번 노드로 들어오는 간선 : 1개

     3번 노드로 들어오는 간선 : 1개

     4번 노드로 들어오는 간선 : 2개

     5번 노드로 들어오는 간선 : 1개

inDegree = [0, 1, 1, 2, 1]

3. 빈 큐를 생성하고, 들어오는 간선의 개수가 0인 노드들을 추가한다.

4. (Loop Start) 큐에서 순차적으로 deque한다.

5. deque된 노드에 연결된 간선들을 제거한다.(= inDegree 배열을 업데이트한다.)

6. 각 노드로 들어오는 간선의 개수(진입차수)가 0인 노드를 큐에 추가한다.(Loop End)

5. deque된 순서대로 출력한다.

위의 예시로 순차적으로 진행해보자.

[t = 0] : 초기 Set-up

1) inDegree 배열에서 들어오는 간선의 수(진입차수)가 0인 노드인 1번 노드를 찾아 큐에 추가한다.

[t = 1] : Loop Start

1) 큐에서 가장 왼쪽에 있는 노드를(1번 노드) deque한 뒤, 1번 노드에 연결된 간선들을 제거한다.

2) 들어오는 간선이 0이 된 2번 노드를 큐에 추가한다.

[t = 2]

1) 큐에서 가장 왼쪽에 있는 노드를(2번 노드) deque한 뒤, 2번 노드에 연결된 간선들을 제거한다.

2) 들어오는 간선이 0이 된 3번 노드를 큐에 추가한다.

[t = 3]

1) 큐에서 가장 왼쪽에 있는 노드를(3번 노드) deque한 뒤, 3번 노드에 연결된 간선들을 제거한다.

2) 들어오는 간선이 0이 된 4번 노드를 큐에 추가한다.

[t = 4]

1) 큐에서 가장 왼쪽에 있는 노드를(4번 노드) deque한 뒤, 4번 노드에 연결된 간선들을 제거한다.

2) 들어오는 간선이 0이 된 5번 노드를 큐에 추가한다.

[t = 5]

1) 큐에서 가장 왼쪽에 있는 노드를(5번 노드) deque한 뒤, 5번 노드에 연결된 간선들을 제거하려고 보니, 제거할 것이 없다. 그대로 deque한다.

아래 deque된 노드들을 그대로 출력하면 위상정렬이 완료되었다. 결과는 [1, 2, 3, 4, 5]이다. 

이 그래프의 경우는 답이 한가지밖에 나오지 않지만, 아래와 같은 그래프는 위상정렬하면 여러가지의 결과가 나올 수 있다. 처음 시작을 6에서 해도 되고 1에서 해도 되기 때문이다.

가능한 결과 : [1, 6, 2, 3, 4, 5], [6, 1, 2, 3, 4, 5]

위상정렬을 파이썬으로 구현하면 아래와 같다.

# n은 노드의 개수, m은 간선의 개수
# 생각의 편의를 위하여 0번 index는 비워놓고 진행

n,m = map(int, r().split())
inDegree = [0 for i in range(n+1)]
dir_list = [[] for i in range(n+1)]

for i in range(m):
    s, e = map(int, r().split())
    dir_list[s].append(e)
    inDegree[e] += 1

q = deque()

while True:
    for i in range(1, n+1):
        if inDegree[i] == 0:
            q.append(i)
    for i in range(1,n+1):
        x = q.popleft()
        answer.append(x)
        for j in dir_list[x]:
            inDegree[j] -= 1
            if inDegree[j] == 0:
                q.append(j)
    if not q:
        break
print(*answer)

BFS : Breadth-First Search(너비 우선 탐색)

DFS : Depth-First Search(깊이 우선 탐색)

최단 경로나 순위 선정 같은 문제에서 만날 수 있는 탐색 알고리즘들이다.

그래프의 개념과 표현법(인접 리스트, 인접 행렬)에 대해서는 아래 글을 참고하면 된다.

one-step-a-day.tistory.com/116

간단한 예시를 통해 각 방법이 어떻게 그래프를 탐색하는지 보자.

아래와 같이 트리가 주어진다고 하자.

BFS와 DFS를 사용하여 전체 트리를 탐색하는 과정을 보자. 특정 노드에 도착하면 노드의 색을 칠한다.

BFS(Breadth-First-Search) : 너비 우선 탐색

  주어진 트리를 BFS로 방문하는 과정은 위 그림과 같다. BFS의 경우 Level을 기준으로 탐색을 진행하게 된다.

Level 1 탐색이 완료되면 Level 2를 순차적으로 탐색하고, Level 2 탐색이 완료되면 Level 3를 탐색한다. (이 때 각 Level에서 오른쪽부터 검색할지, 왼쪽부터 검색할지는 알고리즘에 따라 달라진다.)

위와 같은 탐색을 진행하려면 다음과 같이 시작하면 된다.

1. 시작 노드를 방문한다.(Level 1)

2. 방문한 노드의 자식 노드들을 추가한다.(Level 2)

3. 추가된 자식 노드들을 차례로 방문하며 손자 노드들을 추가한다(Level 3)

4. 추가된 손자 노드들을 차례로 방문한다.

위와 같은 기능은 큐로 아래와 같이 구현할 수 있다.

1. 우선 빈 큐를 생성한 뒤 시작 노드를 추가한다.

2. 큐가 비어있지 않은 경우 아래 과정을 반복한다.

3. (Loop Start) 큐에서 Dequeue한다.(큐의 Front에 있는 원소를 pop) 

4. Dequeue한 원소의 자식 노드들을 큐에 append한다. (Loop end)

5. 큐가 비어있으면 종료한다.

위를 코드로 구현하면 아래와 같다. Visited를 표시하는 이유는 방문한 곳을 다시 방문하지 않기 위함이다.

(하나의 자식 노드가 2개의 부모 노드를 갖는 경우 중복 탐색이 발생할 수 있다.)

def bfs(arr, start):
    visited = defaultdict(bool)
    deq = deque([start])
    answer = []
    visited[start] = True
    while deq:
        x = deq.popleft()
        answer.append(x)
        for i in v_list[x]:
            if visited[i] == False:
                visited[i] = True
                deq.append(i)
    return answer

DFS(Depth-First-Search) : 너비 우선 탐색

BFS는 트리의 Level 순서대로 방문하는 알고리즘이었다면, DFS는 경로 순서대로 끝까지 탐색하는 알고리즘이다.

DFS로 위에서 주어진 노드 방문 순서는 아래와 같다.

처음 방문한 노드를 기준으로 모든 경로들을 따라나간 뒤, 다음 노드를 방문한다.

DFS는 스택을 사용하여 아래와 같이 구현할 수 있다.

1. 우선 빈 스택를 생성한 뒤 시작 노드를 추가한다.

2. 스택이 비어있지 않은 경우 아래 과정을 반복한다.

3. (Loop Start) 스택에서 pop한다.(스택의 Top에 있는 원소를 pop)

4. pop한 원소의 자식 노드들을 스택에 append한다. (Loop end)

5. 큐가 비어있으면 종료한다.

위의 코드를 구현해보면 아래와 같다.

def dfs(arr, start):
    visited = defaultdict(bool)
    stk = [start]
    answer = []
    while stk:
        x = stk.pop()
        if visited[x] == False:
            visited[x] = True
            answer.append(x)
            stk.extend(v_list[x][::-1])
    return answer

www.acmicpc.net/problem/2493

탑들이 일렬로 서있다. 각 탑의 꼭대기에서 왼쪽을 보았을 때, 높이가 같거나 높은 가장 가까운 탑을 출력하는 문제이다. 만약 없다면, 0을 출력한다.

* 힌트

1. 스택을 활용한다.

2. i번째 탑의 높이보다 i+1번째 탑의 높이가 높다면, i번째 탑은 i+1번 이후 탑들의 신호를 수신하지 못한다.

* 풀이

스택을 생성하고, 신호를 수신할 가능성이 있는 탑들은 스택에 추가한다. 

  1. 앞에서부터 순차적으로 탐색한다. 0<=i<len(tower_list)

  2. 스택이 비었을 때는 수신 가능한 탑이 없다는 뜻이므로 0을 출력하고 스택에 i번째 탑의 [높이, index]를 추가한다. 

  3. 스택이 비지 않았다면, 스택에 들어있는 탑들에 대하여 높이가 현재 탑의 높이보다 같거나 높은지 비교한다.(현재 탑의 신호를 수신할 수 있는지 확인)

  4. 현재 탑보다 높이가 낮은 것은 스택에서 pop하고, 높은 것이 있다면 해당 탑의 Index를 출력하고 스택의 현재 탑을 추가한다. 스택 탐색을 멈춘다.

  5. 1~4번을 tower_list의 끝까지 반복한다.

* 예제  

탑들이 위 그림과 같이 주어져 있다.

각 탑들의 신호를 몇번째 탑에서 수신하는지 확인해본다.

첫번째 탑의 신호 : 받을 수 있는 탑이 없다. → 0을 출력

두번째 탑의 신호 : 받을 수 있는 탑이 없다. → 0을 출력

세번째 탑의 신호 : 두번째 탑이 수신한다.  → 2을 출력

네번째 탑의 신호 : 두번째 탑이 수신한다. → 2을 출력

다섯번째 탑의 신호 : 네번째 탑이 수신한다 → 4을 출력

정답 : 0 0 2 2 4

그럼 위의 예제를 실제 코드로 테스트해본다.

* Index에 주의 : 첫번째 탑의 Index  0* 

tower_list = [6, 9, 5, 7, 4]

[1] 첫번째 탑 : index = 0, 탑의 높이 = 6, 스택 = []

  1) 스택이 비어 있으므로, 스택에 [6(탑의 높이), 0(탑의 Index)]를 추가한다.

  2) 스택이 비어있다는 뜻은, index 0번 탑의 신호를 수신할 수 있는 탑이 없다는 것을 의미하므로 0을 출력한다.

output = '0'

[2] 두번째 탑 : index = 1, 탑의 높이 = 9 스택 = [ [6,0] ]

  1) 스택이 비지 않았으므로, 비교를 시작한다. 

  2) 스택의 첫번째 원소 : [6,0]

      현재 탑의 높이 : 9 > 6 이므로 첫번째 원소를 pop한다.

  3) 스택이 비었으므로 두번째 탑의 신호를 수신할 수 있는 탑은 없다.

     현재 탑의 높이와 인덱스를 스택에 추가한다.

output = '0 0'

[3] 세번째 탑 : index = 2, 탑의 높이 = 5 스택 = [ [9,1] ]

  1) 스택이 비지 않았으므로, 비교를 시작한다.

  2) 스택의 첫번째 원소 : [9,1]

      현재 탑의 높이 : 5 < 9 이므로 해당 탑에서 세번째 탑의 신호를 수신한다.

      높이 9인 탑의 index +1(2)를 출력하고, 현재 탑의 높이와 인덱스 [5,2]를 스택에 추가한다.

output = '0 0 2'

[4] 네번째 탑 : index = 3, 탑의 높이 = 7, 스택 = [ [9,1], [5,2] ]

  1) 스택이 비지 않았으므로, 비교를 시작한다. (스택의 오른쪽부터 탐색한다. 이는 가장 가까운 탑부터 탐색한다는 의미이다.)

  2) 스택의 첫번째 원소 : [5,2]

      현재 탑의 높이 : 7 > 5이므로, 해당 탑을 pop하고 다음 탑과 비교한다.

  3) 스택의 두번째 원소 : [9,1]

      현재 탑의 높이 : 7 < 9이므로, 해당 탑에서 네번째 탑의 신호를 수신한다.

      높이가 9인 탑의 index + 1(2)을 출력하고, 현재 탑의 높이와 인덱스 [7,3]을 스택에 추가한다.

output = '0 0 2 2'

[4] 다섯번째 탑 : index = 4, 탑의 높이 = 4, 스택 = [ [9,1], [7,3] ]

  1) 스택이 비지 않았으므로, 비교를 시작한다.

  2) 스택의 첫번째 원소 : [7,3]

      현재 탑의 높이 : 4 < 7이므로, 해당 탑에서 다섯번째 탑의 신호를 수신한다.

      높이가 7인 탑의 index + 1(4)를 출력하고 현재 탑의 높이와 인덱스 [4,4]를 스택에 추가한다.

최종 output = '0 0 2 2 4'

스택 : [ [9,1], [7,3], [4,4] ]

import sys
r = sys.stdin.readline

# 입력 받기
n = int(r())
t_list = list(map(int, r().split()))
answer = []
stk = []
for i in range(n):
    h = t_list[i]
    if stk:
        #print(stk)
        while stk:
            if stk[-1][0] < h :
                stk.pop()
                if not stk:
                    print(0, end=' ')
            elif stk[-1][0] > h:
                print(stk[-1][1]+1, end=' ')
                break
            else : 
                print(stk[-1][1]+1, end=' ')
                stk.pop()
                break
        stk.append([h, i])
    else:
        print(0, end=' ')
        stk.append([h,i])