새싹프로그래머의 이야기

문제: cache 사이즈와 문자열 리스트가 주어졌을 때, 캐시 교체에 드는 총 실행시간을 구하는 문제입니다.

풀이 코드:

from collections import deque


def solution(cacheSize, cities):
    answer = 0
    q = deque(maxlen=cacheSize)

    for i in cities:
        i = i.lower()
        if i in q:
            q.remove(i)
            q.append(i)
            answer += 1
        else:
            q.append(i)
            answer += 5
    return answer

문제 풀이:

문제 풀이의 핵심은 maxlen 옵션을 활용한 deque 사용입니다.

문제에서 캐시 교체 알고리즘은 LRU 알고리즘을 활용한다고 명시해주었습니다.

예를 들면, 길이가 3인 ['a', 'b', 'c'] 라는 리스트에 'd' 라는 원소가 추가된다면 'a'라는 원소가 없어지고 'd'가 추가되는 것입니다.

deque의 maxlen 옵션을 활용한다면 위와 같이 동일하게 동작하는 deque를 구현할 수 있습니다.

from collections import deque

q = deque(maxlen=3)

for i in range(6):
    q.append(i)
    print(q)

위와 같은 코드가 있을 때, 데크에 담기는 원소를 확인해보면 다음과 같습니다.

따라서, 문제 풀이는 maxlen이 정의된 deque를 통해 풀어주었습니다. 

def solution(cacheSize, cities):
    answer = 0
    q = deque(maxlen=cacheSize)

    for i in cities:
        i = i.lower()
        if i in q:
            q.remove(i)
            q.append(i)
            answer += 1
        else:
            q.append(i)
            answer += 5
    return answer

maxlen이 설정된 deque에 append 할 경우, LRU 알고리즘과 맞게 동작하므로 원소가 있는지 여부만 판단하여 실행시간을 구해주었습니다.(원소가 있을 경우, 'cache hit'. 없을 경우, 'cache miss'.)

* 해당 문제는 https://www.youtube.com/watch?v=orf9ailzXvI 을 듣고 작성하였습니다.

문제: 문자열이 주어졌을 때, 문제에서 주어진 방식으로 압축 시킬 수 있는 모든 방법중에서 가장 짧은 문자열의 길이를 구하는 문제입니다.

풀이 코드:

def solution(s):
    answer = 0
    length = len(s)
    lst = [[] for _ in range((length - 1) // 2 + 2)]
    string = ''
    l = 1

    while l <= (length - 1) // 2 + 1:
        strlst = [s[i:i + l] for i in range(0, len(s), l)]  # 1부터 (length - 1) // 2 + 1까지 길이에 맞춰 문자열 쪼개기
        pos = strlst[0]
        cnt = 0
        for i in range(len(strlst)):
            if strlst[i] == pos:    # 앞선 문자열과 동일한 문자열이 들어온다면 갯수를 count하며 추가
                cnt += 1
                string += strlst[i]
            else:
                if cnt > 1:     # 앞선 문자열과 다른 문자열이 들어온다면 문자열 압축 및 새로운 문자열 추가
                    string = string.replace(pos * cnt, '{}{}'.format(cnt, pos))
                cnt = 1
                string += strlst[i]
                pos = strlst[i]

            if i == len(strlst) - 1:    # 동일한 문자가 반복되며 종료될 경우에 대한 처리 진행
                if cnt > 1:
                    string = string.replace(pos * cnt, '{}{}'.format(cnt, pos))

        lst[l] = list(string)
        string = ''
        cnt = 1
        l += 1
    answer = 1001

    for i in lst[1:]:
        if len(i) < answer:
            answer = len(i)

    return answer

풀이 방법:

• 첫번째는 문자열이 있을 때, 앞에서 부터 문자열 길이의 반 이상으로 쪼갠다면 중복되는 것이 생길 수 없으므로 범위를 (문자열 길이 -1)//2 +1 로 정의했습니다.

-> 'abcdefg' 를 'abcde' 'fg'로 쪼갠다면 앞의 문자열에 중복되는 문자열이 뒤에 나올 수 없습니다.

• 두번째로는, 쪼개진 문자열을 앞에서 부터 탐색하면서 다른 문자열이 나올 경우 앞선 문자열에 대한 압축과 동시에 새로 들어온 문자열을 추가해주었습니다.
• 마지막으로,동일한 문자('ababccc'에서 'c') 가 반복되며 종료될 경우를 위해 마지막 index에 대하여 처리하는 코드를 추가해주었습니다.

문제: 주어진 점수를 계산하여 성격유형 검사 결과 출력하기.

풀이 코드:

def solution(survey, choices):
    answer = ''
    dic1 = {'R': 0, 'T': 0, 'C': 0, 'F': 0, 'J': 0, 'M': 0, 'A': 0, 'N': 0}
    lst = 'RTCFJMAN'

    for string, score in list(zip(survey, choices)):
        if score == 4:
            continue
        elif score > 4:
            dic1[string[1]] += abs(score - 4)
        else:
            dic1[string[0]] += abs(score - 4)
    for i in range(0, len(lst), 2):
        if dic1[lst[i]] >= dic1[lst[i + 1]]:
            answer += lst[i]
        else:
            answer += lst[i + 1]

    return answer

풀이 설명:

성격 유형에 대한 점수를 확인하기 위해 다음과 같이 탐색을 해주었습니다.

또한, 탐색 결과를 바탕으로 문제 조건에 맞게 점수를 배분하였습니다.

• 4점 이상일 경우, 'RT'(예시)에서 T에 점수를 배정
• 4점 이하일 경우, 'RT'에서 R에 점수를 배정

for string, score in list(zip(survey, choices)):
    if score == 4:
        continue
    elif score > 4:
        dic1[string[1]] += abs(score - 4)
    else:
        dic1[string[0]] += abs(score - 4)

이후, 각 성격 유형에 대해 점수가 다 반영되면 각 카테고리 별로 강한 성향을 보이는 성격 유형을 answer에 담아주었습니다.

for i in range(0, len(lst), 2):
    if dic1[lst[i]] >= dic1[lst[i + 1]]:
        answer += lst[i]
    else:
        answer += lst[i + 1]

문제: LZW 압축

풀이 코드:

import string


def solution(msg):
    answer = []
    alphabet = list(string.ascii_uppercase)
    dic = {c: i + 1 for i, c in enumerate(alphabet)}
    pos = 27

    while msg:
        length = 1

        while msg[:length] in dic.keys() and length <= len(msg):
            length += 1
        if msg[:length] not in dic.keys():
            dic[msg[:length]] = pos
            pos += 1

        answer.append(dic[msg[:length - 1]])
        msg = msg[length - 1:]

    return answer

문제풀이:

alphabet = list(string.ascii_uppercase)
dic = {c: i + 1 for i, c in enumerate(alphabet)}

먼저, 알파벳에 대한 index가 필요하기 때문에 다음과 같이 enumerate 함수를 통해 딕셔너리 형태로 알파벳:index 형태로 저장해주었습니다.

while msg:
    length = 1

    while msg[:length] in dic.keys() and length <= len(msg):
        length += 1
    if msg[:length] not in dic.keys():
        dic[msg[:length]] = pos
        pos += 1

    answer.append(dic[msg[:length - 1]])
    msg = msg[length - 1:]

가장 핵심이 되는 코드는 문제 조건에 따라 다음과 같이 구현하였습니다.

• 문자열의 시작점으로부터 문자를 탐색하여 딕셔너리에 담긴 최대 길이의 문자열을 구합니다. 즉, 해당 문자열에 한 글자가 추가된다면 해당 문자열은 딕셔너리에 담기지 않은 문자열이 됩니다.
• 딕셔너리에 담기지 않는 문자열에 대해서는 새로운 index와 함께 딕셔너리에 추가해줍니다.
• 딕셔너리에 담긴 최대 길이 문자열에 대한 index를 answer 배열에 담습니다.

위 과정을 반복하여, 문자열을 압축합니다.

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. 플로이드 워셜 알고리즘이란?

최단 경로 알고리즘 중 하나로, 모든 노드에서 모든 노드까지의 최단 경로를 모두 구하는 알고리즘 입니다.

플로이드 워셜 알고리즘은 거리 정보를 계산할 때, 점화식을 활용한다는 점에서 다이나믹 프로그래밍이 적용되어 있다고 할 수 있습니다.

점화식은 다음과 같습니다.

$$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$$

동작과정은 다음과 같습니다.

1. 초기 값 입력. 

각 간선(edge)에 대한 cost가 주어진다고 가정하였을 때, 이차원 배열에 해당 cost를 갱신 시킵니다.

자기 자신에 대한 cost는 0이며, 갈 수 없는 노드는 INF로 초기화 합니다.

2. 각 노드를 순회하며, 해당 노드를 거쳐갈 수 있는 경로 확인 및 갱신

예를 들어, 모든 1번 노드에 대해서 거쳐갈 수 있는 경로는 다음과 같습니다.

$$D_{23} = min(D_{23}, \, D_{21}+D_{13}) \qquad =>min(2,7+4) == 2$$

$$D_{24} = min(D_{24}, \, D_{21}+D_{14}) \qquad =>min(2,7+INF) == 2$$

$$D_{32} = min(D_{32}, \, D_{31}+D_{12}) \qquad =>min(INF,5+1) == 6$$

↑update

$$D_{34} = min(D_{34}, \, D_{31}+D_{14}) \qquad =>min(3,5+INF) ==3$$

$$D_{42} = min(D_{42}, \, D_{41}+D_{12}) \qquad =>min(INF,1+1) == 2$$

↑update

$$D_{43} = min(D_{43}, \, D_{41}+D_{13}) \qquad =>min(INF,1+4)==5$$

↑update

이와 같이 거쳐가는 경로를 계산하여, 기존 담겨있는 cost보다 더 낮은 cost가 든다면 table을 갱신하여 줍니다.

이 과정을 모든 노드에 대하여 반복하여 줍니다.

2. 코드구현

코드는 백준 알고리즘 11404번을 기반으로 작성되었습니다.

• 이차원 배열(= 거리 테이블)에 대하여, 자신한테로의 경로를 0으로 초기화 해줍니다.
• 간선와 cost에 대한 정보를 입력받아 거리 테이블에 갱신하여 줍니다.
• 3중 for문을 통해, 각 노드별로 거쳐가는 경로(점화식 기반)를 모두 탐색하고 거리 테이블을 갱신합니다. 

import sys

INF = sys.maxsize

n = int(input())    # number of city
m = int(input())    # number of bus

graph = [[INF] * (n+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0  # path to self = 0

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a][b] = min(graph[a][b],c)    # update array about initial path

# D_ab = D_ak + D_kb
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for i in range(1,n+1):
    for j in range(1, n+1):
        if graph[i][j] == INF:
            graph[i][j] = 0
for i in range(1, n+1):
    print(*graph[i][1:])
    # print(' '.join(map(str,graph[i][1:])))

• Reference

https://freedeveloper.tistory.com/385

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

다익스트라(dijkstra) 알고리즘은 최단 경로를 구하는 알고리즘 중 하나입니다.

1. 최단 경로(Shortest Path) 알고리즘이란?

Path와 cost가 주어졌을 때, cost가 제일 적게 드는 경로를 찾는 알고리즘 입니다.

특히, 다익스트라 알고리즘은 한 지점에서 특정 지점까지의 최단 경로를 구하는 알고리즘으로 시작점과 끝점을 필요로 합니다.

자료구조로는 graph를 사용하며, 지점을 그래프의 node로 표현하고 경로를 그래프의 edge로 표현합니다.

2. 다익스트라 알고리즘

1. 시작 노드가 1이라고 했을 때, 알고리즘이 동작하는 원리는 다음과 같습니다.
2. 1에서 cost가 가장 가까운 노드 3에 대한 distance를 업데이트 합니다
3. 1에서 가장 가까운 노드를 모두 업데이트 합니다. 즉, 1에 대해서 1 -> 3, 1 -> 2, 1 -> 5 의 cost가 업데이트 됩니다.
4. 코스트가 낮은 3으로 이동하지만 연결된 노드가 없으므로, 2로 이동합니다.
5. 2 -> 5의 cost = 1이므로, 1 -> 5 의 최소 cost는 6 입니다. 따라서, 기존의 cost 9 짜리 1 -> 5 경로는 폐기되고 6으로 새로 업데이트 됩니다.

*다익스트라 알고리즘은 모든 cost가 음의 정수가 아니어야만 동작 가능합니다. 음의 정수가 포함되어 있을 경우, 최단거리를 구하는 알고리즘은 Bellman-Ford 알고리즘으로 향후 포스팅 하도록 하겠습니다.

*시간복잡도는 우선순위 큐를 사용할 경우, O($ElogV$)입니다.

3. 코드구현

• 노드에 대한 정보를 담을 때는, graph를 활용합니다.
• 우선순위 큐와 거리 정보를 담을 list를 사용합니다.
• 반복문을 통해, 출발 노드 부터 최소거리 순으로 거리 정보를 업데이트 해줍니다.
• 위 그림의 1 -> 2 -> 5와 같이 거쳐서 가는 경로에 대한 거리 정보도 업데이트 해줍니다.
• 거리정보 업데이트가 완료되면, 수행을 종료합니다.

코드는 백준 알고리즘 1753번 문제 풀이를 통해 작성하였습니다.(https://www.acmicpc.net/problem/1753)

import sys
import heapq

INF = 1E10

v, e = map(int, sys.stdin.readline().split())
k = int(input())

graph = [[]for _ in range(v+1)]
heap_q = [(0, k)]
distance = [INF] * (v+1)
distance[k] = 0

for _ in range(e):
    start, end, cost = map(int, sys.stdin.readline().split())
    graph[start].append((cost,end))


def dijkstra():
    while heap_q:
        nowCost, node = heapq.heappop(heap_q)

        if distance[node] < nowCost:    # if distance is updated
            continue

        for newCost, newNode in graph[node]:    # check adjacent node
            dist = distance[node] + newCost
            if distance[newNode] > dist:    # update lower cost
                distance[newNode] = dist
                heapq.heappush(heap_q, (dist, newNode))

dijkstra()

for i in range(1,v+1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])

Reference

https://jaemunbro.medium.com/algorithm-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-with-python-20f061fdc8f1

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. BFS란?

그래프를 탐색하는 알고리즘의 한 종류로, leaf 노드에 도달할 때 까지 깊이 우선 탐색을 하는 DFS와 달리 인접한 노드부터 탐색하는 방법입니다. 그래프의 각 깊이 별로 탐색을 하게 되므로, 넓이 우선 탐색이라고 부릅니다.

*시간복잡도는 DFS와 마찬가지로 인접리스트 방식은 모든 노드(n)와 간선(e)을 탐색하므로, O(n+e) 입니다.

구체적으로 단계를 설명해보자면 다음 그림과 같습니다.

2. 구현 방법

• queue를 통해 인접한 배열을 담아가며 탐색합니다.
• visited 배열을 통해 방문 여부를 확인합니다.
• 인접한 노드를 우선적으로 탐색하며, 방문하지 않은 노드만 탐색합니다.

백준알고리즘 1260번을 기반으로 구현한 코드입니다.(https://www.acmicpc.net/problem/1260)

import sys
from collections import deque

n,m,v = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
    node1, node2 = map(int, sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

for i in range(1,n+1):
    graph[i].sort()

visited_bfs = [False]*(n+1)

def bfs(n):
    q = deque([n])
    visited_bfs[n] = True

    while q:
        node = q.popleft()
        print(node, end=' ')

        for new_node in graph[node]:
            if visited_bfs[new_node]:
                continue
            q.append(new_node)
            visited_bfs[new_node] = True

bfs(v)

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. DFS란? 

그래프를 탐색하는 알고리즘의 한 종류로, leaf node(자식이 없는 노드)에 도달할 때까지 한 방향으로 탐색하는 기법입니다.

*시간 복잡도는 인접리스트 방식의 DFS는 모든 노드(n)와 모든 간선(e)을 탐색했다고 할 수 있으므로, O(n+e)의 복잡도를 가집니다.

구체적으로 보자면, 다음과 같은 탐색과정을 거칩니다.

2. 코드 구현

• 재귀적 구현을 통하여 구현합니다.
• visited 배열을 통해 방문 여부를 확인하여야 합니다.
• 노드를 방문할 경우 방문처리를 해주며, 방문하지 않은 노드만 방문합니다.
• 방문하는 방향으로 leaf node에 도달할 때 까지 탐색을 진행합니다.
• 위, 과정을 모든 leaf node를 방문할 때 까지 반복합니다.

백준 알고리즘 1260번을 통하여 구현한 코드입니다.(https://www.acmicpc.net/problem/1260)

import sys
from collections import deque

n,m,v = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
    node1, node2 = map(int, sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

for i in range(1,n+1):
    graph[i].sort()

visited_dfs = [False]*(n+1)

def dfs(n):
    print(n, end=' ')
    visited_dfs[n] = True

    for node in graph[n]:
        if visited_dfs[node]:
            continue
        dfs(node)
dfs(v)

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. 이진 탐색(Binary Search)이란?

오름차순으로 정렬된 배열에서 찾고자하는 element를 탐색하는 알고리즘 입니다.

데이터를 반으로 나눠가며 탐색을 진행합니다.

시간 복잡도는 O( log N ) 입니다.

 2. 구현 방법

• 배열에서 중간 값을 찾고자하는 target 값이랑 비교한다
• 중간 값 < target 이라면, 중간 값보다 오른쪽에 있는 배열로 범주를 좁혀 과정을 반복한다
• 중간 값 > target 이라면, 중간 값보다 왼쪽에 있는 배열로 범주를 좁혀 과정을 반복한다

3. 코드

백준 알고리즘 10815번을 기준으로 작성하였습니다.

myCard - 오름차순으로 정렬 되어 있는 배열

Binary Search - 반복문

def binarySearch(target):
    start = 0
    end = len(myCard) - 1

    while start <= end:
        mid = (start + end) // 2
        if myCard[mid] == target:
            return 1
        elif myCard[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return 0

Binary Search - 재귀

def binarySearch(target,start,end):
    mid = (start+end)//2

    if start > end:
        return 0
    if myCard[mid] == target:
        return 1
    elif myCard[mid] < target:
        start = mid + 1
    else:
        end = mid -1

    return binarySearch(target,start,end)

문제를 푸시다보면 다양한 에러를 만나실텐데요. 

오늘은 백준알고리즘 1697번을 풀면서 발생한 메모리 초과에 대해서 글을 써보려고 합니다.

메모리 초과가 발생하는 이유를 간단히 말씀드리자면 '스택 오버플로우'가 발생하기 때문입니다.

문제를 푸시면서 가장 많이 접할 수 있는 경우는 다음 두 경우라고 생각합니다.

1.  너무 많은 변수들을 배열 등에 저장할 경우.

2. DFS 등에서 재귀적 호출을 통해 너무 많은 함수들을 호출할 경우.

저 같은 경우에는, 백준 알고리즘 1697번에서 1번에 의한 메모리 초과가 발생하였는데요.

시작점으로부터 도착점까지 도달할 때 까지, (시작점-1, 시작점+1, 시작점*2)에 해당하는 값들을 탐색하는 과정에서 실수를 했습니다.

시작점 = 5, 도착점 =17을 기준으로 처음 들어간 (5-1,5+1,5*2)에 대해서 다음 싸이클 값들이 어떻게 저장되는지 출력한 것인데요.

아래 스크린샷을 보시면, 하나의 경우의 수에 대하여 계속해서 3가지의 새로운 경우의 수가 들어가고 있습니다.

해당 문제의 시작점과 도착점이 될 수 있는 정수의 범위가 0~100,000 이었으니, 시작점이 1이고 도착점이 100,000일 경우 엄청나게 많은 값들이 큐에 저장되었겠죠?

이로 인해, 계속해서 메모리 초과가 발생하였습니다.

메모리 초과에 대한 해결 방안은 다음과 같습니다.

1. 배열에 너무 많은 값들이 들어가는 경우에는 값이 들어갈 수 있는 범위 제한 및 들어가는 데이터 수를 제한 하는 조건 등을 통해서 해결하실 수 있습니다.

1697번을 예시로 들자면,

Max = 10 ** 5
visitedCnt = [0]*(Max+1)

배열을 선언할 때, 적당한 크기로 배열의 사이즈를 할당합니다.

for i in pos:
    if 0 <= i <= Max and not visitedCnt[i]:
        visitedCnt[i] = visitedCnt[idx] + 1
        queue.append([i,visitedCnt[i]])

두번째로는 들어갈 수 있는 값들의 범위를 지정하여 무한 루프를 방지해주고, 해당 값을 처리한 적이 있는지 확인하여 중복된 데이터가 처리되지 않도록 하였습니다.

위, 두가지 방법을 통해 메모리 초과를 해결 할 수 있었습니다.

2. 재귀 등으로 인한 너무 많은 함수 호출로 인한 메모리 초과의 경우에는 다음과 같습니다.

첫번째로는 재귀가 너무 많은 횟수가 반복되지 않도록 적절한 조건 설정 해주어 메모리 초과가 발생하지 않도록 하는 방법이 있고,

두번째로는 재귀함수를 반복문으로 푸는 것입니다.

재귀함수를 통해 호출된 함수는 메모리 영역의 스택에 저장되는데, 동일한 함수여도 호출 될 때마다 스택영역에 계속해서 메모리가 할당되게 됩니다. 너무 많은 함수가 호출이 된다면 스택 영역의 메모리를 초과하게 되는 '스택 오버플로우'가 발생합니다.

즉, 핵심은 스택 영역의 메모리를 초과하지 않게 사용하는 것이죠.

첫번째 방법은 스택 영역을 활용하되 사용하는 메모리 영역을 초과하지 않게 하는 방법이고, 두번째 방법은 아예 스택 영역을 사용하지 않는 방법입니다.

메모리 초과라는 문제에 대해 조금이나마 도움이 되었으면 좋겠습니다. 

읽어주셔서 감사합니다.