개발자 아지트

https://school.programmers.co.kr/learn/courses/30/lessons/12978

문제설명

링크 참고

문제 해결 방법

다익스트라알고리즘을 적용해 문제를 해결하였음

코드 구현

def solution(N, road, K):
    answer = 0
    
    distances = [float("inf")] * (N+1) 
    distances[0] = 0 # 0과 1은 사용하지 않음
    distances[1] = 0
    
    
    for i in range(N-1):
        for i in range(1, N+1):
            for nodeSet in road:
                fromm, to, weight = nodeSet
                if fromm == i:
                    distance = distances[i] + weight
                    if distance < distances[to]:
                        distances[to] = distance

                to, fromm, weight = nodeSet
                if fromm == i:
                    distance = distances[i] + weight
                    if distance < distances[to]:
                        distances[to] = distance
                    

    # N개의 마을 중에서 K시간 이하로 배달이 가능한 마을에서만 주문을 받으려고함
    # 1번 마을에 있는 음식점이 음식 주문을 받을 수 있는 마을의 개수를 return 
    
    # a, b = 마을의 번호 c = 도로를 지나는데 걸리는 시간
    
    # 그래프 만들기 
    answer +=1
    for i in distances:
        if i <= K and i>0:
            answer+=1
    
    return answer

시간/공간 복잡도

O((N+E)N)

최적화 및 개선

하지않음... 

어려웠던 점

양방향 이동이라는 점을 잘 새겨봤어야 했다. 코드를 짜다보니 나도 모르게 단방향으로 코드를 작성했다. 

다익스트라 알고리즘은 n-1번 반복해야 하는 것을 잘 기억해야겠다. 

처음에 코드 작성후, 채점하니 40점이 나왔는데 혹시나 해서 최단거리 구하는 코드를 한번더 복사 붙여넣기 한 후 채점하니 50점이 나왔다. 그 후 힌트를 얻기위해 책을 한번더 보고, 그 후 한번 더 복사 붙여넣기 하니 80점이 나왔는데 그때 깨달았다.. 

https://school.programmers.co.kr/learn/courses/30/lessons/43162

문제설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

문제 해결 방법

이런 문제는 최적의 해 보다는 모든 요소를 탐색하는 것이 목적이다.

모든 요소를 탐색하기 위해 DFS가 좋다. 

computers를 그래프로 표현한 후, 방문 테이블을 만들고, 방문 테이블을 통해 그래프를 DFS로 몇번 탐색 했는지를 출력하면 된다. 

이 문제를 bfs로 풀려고 했던 과거의 내자신 ㅠㅠ 

코드 구현

주석 없는 버전

def dfs(computers, visited, node):
        visited[node] = True
        for idx, connected in enumerate(computers[node]):
            if connected and not visited[idx]:
                dfs(computers, visited, idx)

def solution(n, computers):
    answer = 0
    visited = [False] * n
    
    for i in range(n):
        if not visited[i]:
            dfs(computers, visited, i)
            answer += 1
    
    
    return answer

def dfs(computers, visited, node):
    # 조회를 하면 해당 노드에 대해 방문처리를 해준다. 
    # 해당 노드를 통해 computers에 딸린 다른 노드들을 반복문을 통해 조회하고,
        # 연결 여부와 방문 여부를 확인한다. 
    # 연결된 것을 통해 깊이 우선 탐색을 계속 해나간다. 
    visited[node] = True
    for index, connected in enumerate(computers[node]):
        if connected and visited[index] == False:
            dfs(computers, visited, index)
    
def solution(n, computers):
    answer = 0
    # 방문여부를 담는 크기 n만큼의 배열 
    
    visited = [False] * n
    
    for i in range(n):
        if visited[i] == False:
            dfs(computers, visited, i)
            answer+=1
    # 반복문을 통해 노드를 0~n까지 순회하며 깊이 우선 탐색을 한다. 
        # 깊이 우선 탐색 dfs에는 computers라는 그래프와, visited, 그리고 노드를 보내준다. 
    # 깊이 우선 탐색이 끝나면 answer +1 을 해준다. 
    return answer

시간/공간 복잡도

O(N^2)

최적화 및 개선

따로 하지 않음.

어려웠던 점

아직 DFS, BFS사용에 서툰것 같다. 

https://school.programmers.co.kr/learn/courses/30/lessons/1844

문제설명

링크 참고

문제 해결 방법

bfs를 통해 문제를 해결하였음

코드 구현

과거에 작성한 코드 

from collections import deque

def solution(maps):
    answer = 0
    # map은 2차원 배열이라고 생각하면 됨 
    n = len(maps) #가로 
    m = len(maps[0]) #세로 

    # 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
    dx = [-1, 1, 0, 0] #세로축
    dy = [0, 0, -1, 1] #가로축 
    
    def bfs(x,y):
        #큐 구현을 위해 deque라이브러리 사용
        queue = deque()
        queue.append((x,y))
        # 큐가 빌 때까지 반복하기 
        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                # 공간을 벗어난 경우 무시
                if nx  < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                # 벽인 경우 무시
                if maps[nx][ny] == 0:
                    continue
                # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록 
                if maps[nx][ny] == 1:
                    maps[nx][ny] = maps[x][y] + 1
                    queue.append((nx, ny))
        # 가장 오른쪽 아래 까지의 최단 거리 반환 
        return maps[n-1][m-1]
    
    
    if bfs(0,0)==1:
        answer=-1
    else:
        answer=bfs(0,0)
    
    return answer

from collections import deque

def solution(maps):
    answer = 0
    n = len(maps) 
    m = len(maps[0]) 
    
    # 최단 거리 구하기.
    # bfs - deque
    # 1,1 부터 시작
    dx = [1, -1, 0, 0] # 동, 서, 남, 북
    dy = [0, 0, -1, 1]
    
    # 게임 맵 벗어난 길은 갈 수 없음
    queue = deque([(0, 0)])
    distance = 0
    
    visited = [[False] * n for _ in range(m)]
    visited[0][0] = True
    
    while 1:
        if len(queue) == 0: 
            break
            
        x, y = queue.popleft()
        
        if x == n-1 and y == m-1:
            check = 1
            break   
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx >= n or ny >= m or nx < 0 or ny < 0:
                continue 
            
            if maps[nx][ny] == 0:
                continue
            
            if maps[nx][ny] == 1:
                queue.append([nx, ny])
                maps[nx][ny] = maps[x][y] +1
    
    answer = maps[n-1][m-1]
    if answer == 1:
        return -1
    return answer

시간/공간 복잡도

O(N*M)

최적화 및 개선

.

어려웠던 점

가로 세로가 헷깔렸음.

예전에 풀어봤던 문제인데도 처음엔 느낌조차 없다가 점점 느낌 살아났지만, 예전에 고민했던 부분을 또 고민하며 문제를 풀었다. 

주석 있는 코드 

def solution(graph, source):
    # 1. 그래프의 노드 수
    num_vertices = len(graph)
    # 2. 거리 배열 초기화 
    distance = [float("inf")] * num_vertices
    distance [source] = 0
    # 3. 직전 경로 배열 초기화 
    predecessor = [None] * num_vertices

    # 4. 간선 수 만큼 반복하여 최단 경로 갱신
    for temp in range(num_vertices - 1):
        for u in range(num_vertices):
            for v, weight in graph[u]:
                # 5. 현재 노드 u를 거쳐서 노드 v로 가는 경로의 거리가 기존에 저장된 노드 v까지의
                # 거리보다 짧은 경우
                if distance[u] + weight < distance[v]:
                    # 6. 최단 거리를 갱신해줌.
                    distance[v] = distance[u] + weight
                    # 7. 직전 경로를 업데이트해줌.
                    predecessor[v] = u

    # 8. 음의 가중치 순회 체크 
    for u in range(num_vertices):
        for v, weight in graph[u]:
            # 9. 현재 노드 u를 거쳐서 노드 v로 가는 경로의 거리가 기존에 
            # 저장된 노드 v까지의 거리보다 짧은 경우
            if distance[u] + weight < distance[v]:
                # 10. 음의 가중치 순회가 발견됐음, [-1] 반환
                return [-1]

    return [distance, predecessor]

주석 간소화 코드

def solution(graph, source):
    vLen = len(graph)
    distances = [float("inf")] * vLen
    distances[source] = 0 # 최단거리 리스트, 시작은 0
    predecessor = [None] * vLen # 직전 노드 
    print("")

    # 일단 최단거리 그거 구해야함. 
    for i in range(0, vLen-1): # n-1번 반복함
        for v, node in enumerate(graph):
            for oneNode in node:
                currNode, weight = oneNode
                distance = distances[v] + weight
                if distance < distances[currNode]:
                    distances[currNode] = distance
                    predecessor[currNode] = v

    # 음의 순환 잡기 
    for v, node in enumerate(graph):
        for oneNode in node:
            currNode, weight = oneNode       
            distance = distances[v] + weight
            if distance < distances[currNode]:
                return [-1]

    return [distances, predecessor]

import heapq

def solution(graph, start):

# 1. 시작 노드 설정, 시작 노드부터 특정 노드까지 최소 비용을 저장할 공간과 직전 노드를 저장할 공간 마련
# 1-1. 최소 비용을 저장할 공간은 모두 매우 큰 값으로 초기화
# 무한대 약자는 INF 로 표현, 직전 노드를 저장할 공간 또한 INF로 초기화 
# 1-2. 시작 노드의 최소 비용은 0, 직전 노드는 자신으로

# 2. 해당 노드를 ㅌ오해 방문할 수 있는 노드 중, 아직 방문하자ㅣ 않는 노드 중 현재까지 구한 최소 비용이 
# 가장 작은 노드를 선택
# 2-1. 해당 노드를 거쳐 각 노드까지 가는 최소 비용과 현재까지 구한 최소 비용을 비교해 작은 값을
# 각 노드의 최소 비용으로 갱신함
# 2-2. 이때 직전 노드도 같이 갱신함.
# 3. 노드 개수에서 1을 뺀 만큼 반복함.
    
    distances = {node: float("inf") for node in graph}
    # 1. 모든 노드의 거리 값을 무한대로 초기화 
    # print(distances)

    distances[start] = 0 
    # 2. 시작 노드의 거리 값은 0으로 초기화 

    queue = []
    heapq.heappush(queue, [distances[start], start]) 
    # print('queue', queue) # [[0, 'A']]

    # 3. 시작 노드를 큐에 삽입
    paths = {start: [start]} # paths:  {'A': ['A']} 이렇게 나오는게 맞나,,? 
    # 4. 시작 노드의 경로를 초기화 

    # print('paths: ', paths)

    while queue:
        # 5. 현재 가장 거리 값이 작은 노드를 가져옴
        current_distance, current_node = heapq.heappop(queue)
        # 6. 만약 현재 노드의 거리 값이 큐에서 가져온 거리 값보다 크면,
        # 해당 노드는 이미 처리한 것이므로 무시

        if distances[current_node] < current_distance:
            continue

        # 7. 현재 노드와 인접한 노드들의 거리 값을 계산하여 업데이트
        
        for adjacent_node, weight in graph[current_node].items():
            distance = current_distance + weight
            # 8. 현재 계산한 거리 값이 기존 거리 값보다 작으면 최소 비용 및
            # 최단 경로 업데이트 
             
            if distance < distances[adjacent_node]:
                distances[adjacent_node] = distance # 최소 비용 업데이트
                paths[adjacent_node] = paths[current_node] + [adjacent_node]
                # 최단 경로 업데이트

                # 9. 최소 경로가 갱신된 노드를 비용과 함께 큐에 푸시
                heapq.heappush(queue, [distance, adjacent_node])

    # 10. paths 딕셔너리를 노드 번호에 따라 오름차순 정렬하여 반환
    sorted_paths = {node: paths[node] for node in sorted(paths)}

    return [distances, sorted_paths]

주석 없는 버전 

import heapq
def solution(graph, start):

    distances = {node: float("inf") for node in graph}
    distances[start] = 0

    queue = []
    heapq.heappush(queue, [distances[start], start])
    paths = {start: [start]}

    while queue:
        currDis, currNode = heapq.heappop(queue)

        if distances[currNode] < currDis:
            continue 

        for injeop, weight in graph[currNode].items():
            distance = currDis + weight
            if distances[currNode] > distance:
                distances[currNode] = distance
                paths[injeop] = paths[currNode] + [injeop]
                heapq.heappush(queue, [distance, injeop])

        
        sorted_paths = {node: paths[node] for node in sorted(paths)}


            
   
    return [distances, sorted_paths]

가중치가 있는 그래프에서는 일반적으로 시작 노드에서 끝 노드까지 이동할 때 거치는 간선의 가중치의 총 합이 최소가 되는 것을 말한다. 

최단 경로는 구하는 대표적인 알고리즘에는 다음과 같은 두가지 알고리즘이 있다. 

• 다익스트라 알고리즘
• 벨만-포드 알고리즘

다익스트라 알고리즘

가중치가 있는 그래프의 최단 경로를 구하는 문제는 대부분 다익스트라 알고리즘을 사용한다고 보면 될 정도로 중요한 알고리즘이다. 

[다익스트라 알고리즘의 동작 과정]

1. 시작 노드를 설정하고 시작 노드로부터 특정 노드 까지의 최소 비용을 저장할 공간과 직전 노드가 뭔지 저장할 공간을 마련한다. 

        1-1. 최소 비용을 저장할 공간은 모두 매우 큰 값으로 초기화 한다.

               (여기서는 무한대(infinite)를 의미하는 약자 INF로 표현할 예정이다. )

        1-2. 시작 노드의 최소 비용은 0이고, 직전 노드는 자기 자신으로 한다. 

2. 해당 노드를 통해 방문할 수 있는 노드 중(아직 방문하지 않은 노드 중), 현재까지 구한 최소 비용이 가장 적은 노드를 선택한다. 

        2-1. 해당 노드를 거쳐서 각 노드까지 가는 최소 비용과 현재까지 구한 최소 비용을 비교하여 작은 값을 각 노드의 최소 비용으로 갱신한다.  

        2-2. 이때 직전 노드로 어떤 노드였는지도 같이 갱신한다. 

3. 노드 개수에서 1을 뺀 만큼 반복한다. 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

[관련 의문]

Q. 힙큐를써서 현재 구한 최단거리중에 젤 짧은걸 먼저 방문한다 하더라도 결국 모든 노드를 다 방문하는데 힙큐를 왜 쓰는것인가?

A. 힙큐를 쓰는 이유는 효율적으로 최단 경로를 찾기 위해서이다. 필요한 노드만 우선 방문한다. 다익스트라 알고리즘은 가장 짧은 거리의 노드를 우선적으로 방문하고 그 노드의 인접 노드들만 탐색한다. 이렇게 함으로써 필요하지 않은 노드를 최대한 적게 방문할 수 있게 된다.

Q. 그럼 예를들어서 힙큐를 사용하지 않으면 결국 모든 노드를 비효율적으로 돌게돼서, 결국 돌아봤자 최단거리가 아닌 경우에는 거리 갱신을 할 필요도 없기 때문에 비효율적으로 돌게 된다는건지?

A. YES

힙큐를 사용하지 않는다면, 매번 모든 노드를 확인해서 가장 짧은 거리를 가진 노드를 찾는 과정이 필요하다. O(N)의 시간이 걸리고, 이를 모든 노드에 대해 반복하므로 전체 복잡도가 커진다. 

반면, 힙큐를 사용하면 가장 짧은 거리의 노드를 O(log N) 시간에 찾아낼 수 있습다. 이 차이로 인해 노드 수가 많아질수록 힙큐를 사용한 다익스트라 알고리즘이 훨씬 빠르게 동작하게 된다.

거리가 확정되지 않은 노드들을 계속 방문하게 됨

최단 거리의 노드를 먼저 방문하면 그 주변 노드들의 거리가 효율적으로 갱신되지만, 힙큐 없이 임의의 노드를 방문한다면 거리가 확정되지 않은 상태로 노드를 계속 방문하는 일이 발생한다. 이렇게 되면 사실상 거리 갱신이 필요 없는 노드들도 방문하게 되고, 결국 불필요한 계산과 방문이 계속 일어난다.

from collections import defaultdict, deque

def solution(graph, start):
    # 트리 생성 
    tmp_tree = defaultdict(list)
    for i, v in graph:
        tmp_tree[i].append(v)

    print(tmp_tree)
    
    def dfs(start):
        visited = set()
        queue = deque([start])
        visited.add(start)
        result.append(start)

        while queue:       
            node = queue.popleft() # 순차적으로 처리함 
            for injeop in tmp_tree.get(node, []):
                print('node', node, 'injeop', injeop)
                if injeop not in visited:
                    queue.append(injeop)
                    visited.add(injeop)
                    result.append(injeop)

    result = []
    dfs(start)  
    return result

from collections import defaultdict

def solution(graph, start):

    adj_list = defaultdict(list)
    for u, v in graph:
        adj_list[u].append(v)


    def dfs(node, visited, result):
        visited.add(node)
        result.append(node)
        for neighbor in adj_list.get(node, []):
            print('neighbor', neighbor)

            if neighbor not in visited:
                dfs(neighbor, visited, result)

    
    visited=set()
    result = []
    dfs(start, visited, result)

    return result

https://school.programmers.co.kr/learn/courses/30/lessons/42577

문제설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119

박준영 : 97 674 223

지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.

각 전화번호의 길이는 1 이상 20 이하입니다.

같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

입출력 예 설명

입출력 예 #1

앞에서 설명한 예와 같습니다.

입출력 예 #2

한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3

첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

문제 해결 방법

그래서 연속된 두 문자씩 비교함

코드 구현

def solution(phone_book):
    answer = True
    phone_book.sort()

    count=0
    for num in phone_book:
        if count==0:
            count+=1
            pass
        else:
            preNum = phone_book[count-1]
            if preNum in num and num.startswith(preNum):
                answer = False
            count+=1
    
    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

그래서 연속된 두 문자씩 비교를 위해 문자열 상태에서 sort를 하여 찾는 효율을 높임.

시간 초과 개선을 위해 모든 문자열 비교하려고 하지않음.

특정 문자열이 문자열 접두사로 붙는 것을 확인하기 위해 startswith함수를 사용함.

어려웠던 점 및 느낀점

없음. 확실히 예전에 푼문제라 그런가 이해가 빨리되고, 풀때 헤메는 것도 잠깐이고 코드가 간결해짐.

https://school.programmers.co.kr/learn/courses/30/lessons/12981?language=python3

문제설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.

마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.

앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.

이전에 등장했던 단어는 사용할 수 없습니다.

한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.

2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.

3번 사람이 자신의 첫 번째 차례에 know를 말합니다.

1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.

(계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

제한 사항

끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.

words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.

단어의 길이는 2 이상 50 이하입니다.

모든 단어는 알파벳 소문자로만 이루어져 있습니다.

끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.

정답은 [ 번호, 차례 ] 형태로 return 해주세요.

만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

문제 해결 방법

문제를 풀기위한 조건들을 하나하나 생각해서 하나하나 제외해가면서 풀었음

코드 구현

def solution(n, words):
    answer = []
    # 1번부터 마지막 순서까지 돌고돈다.
    # 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야한다. 
    # 이전에 등장했던 단어는 사용할 수 없다. 
    # 한 글자 단어 인정안해줌
    newWords=[] #스택에 쌓음
    newWords.append(words[0]) 
    
    cnt = 1 #words에서 어디를 가리키는지 
    big_phase=0
    check = 0
    check2 = 0
    while 1:
        big_phase+=1
        for i in range(1, n+1):
            if check ==1:
                answer.append(i)
                answer.append(big_phase)
                return answer
            
            if check2 == 1:
                answer.append(i)
                answer.append(big_phase)
                return answer
            
            if cnt == len(words):
                break
            
            if words[cnt][0] == newWords[-1][-1]:
                pass
            else:
                check = 1
                
            
            if words[cnt] in newWords:
                check2 = 1
            else:
                newWords.append(words[cnt])  
                cnt+=1
                
        if cnt == len(words):
                break

    answer.append(0)
    answer.append(0)
    
    return answer

시간/공간 복잡도

O(n)

최적화 및 개선

최적화 및 개선하지 않음

어려웠던 점

예전에 작성한 코드랑 그닥 로직이 다른거 같진 않다.. 

스스로 더 로직을 잘 이해하고 풀었다는 차이점이 존재할뿐?