Merge branch 'master' of https://github.com/ndb796/python-for-coding-test

ndb796 · ndb796 · commit 0cf0412d8c8b · 2020-08-10T02:04:42.000+09:00
diff --git a/17/1.py b/17/1.py
@@ -1,38 +1,38 @@
-INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정합니다.
+INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
 
-# 노드의 개수 및 간선의 개수를 입력 받습니다.
+# 노드의 개수 및 간선의 개수를 입력받기
 n = int(input())
 m = int(input())
-# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화합니다.
+# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
 graph = [[INF] * (n + 1) for _ in range(n + 1)]
 
-# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화합니다.
+# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
 for a in range(1, n + 1):
     for b in range(1, n + 1):
         if a == b:
             graph[a][b] = 0
 
-# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화합니다.
+# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
 for _ in range(m):
-    # A에서 B로 가는 비용은 C라고 설정합니다.
+    # A에서 B로 가는 비용은 C라고 설정
     a, b, c = map(int, input().split())
-    # 가장 짧은 간선 정보만 저장합니다.
+    # 가장 짧은 간선 정보만 저장
     if c < graph[a][b]:
         graph[a][b] = c
 
-# 점화식에 따라 플로이드 워셜 알고리즘을 수행합니다.
+# 점화식에 따라 플로이드 워셜 알고리즘을 수행
 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 a in range(1, n + 1):
     for b in range(1, n + 1):
-        # 도달할 수 없는 경우, 0을 출력합니다.
+        # 도달할 수 없는 경우, 0을 출력
         if graph[a][b] == INF:
             print(0, end=" ")
-        # 도달할 수 있는 경우 거리를 출력합니다.
+        # 도달할 수 있는 경우 거리를 출력
         else:
             print(graph[a][b], end=" ")
     print()
diff --git a/17/2.py b/17/2.py
@@ -1,30 +1,30 @@
-INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정합니다.
+INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
 
-# 노드의 개수, 간선의 개수를 입력 받습니다.
+# 노드의 개수, 간선의 개수를 입력받기
 n, m = map(int, input().split())
-# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화합니다.
+# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
 graph = [[INF] * (n + 1) for _ in range(n + 1)]
  
-# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화합니다.
+# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
 for a in range(1, n + 1):
     for b in range(1, n + 1):
         if a == b:
             graph[a][b] = 0
  
-# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화합니다.
+# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
 for _ in range(m):
-    # A에서 B로 가는 비용을 1로 설정합니다.
+    # A에서 B로 가는 비용을 1로 설정
     a, b = map(int, input().split())
     graph[a][b] = 1
  
-# 점화식에 따라 플로이드 워셜 알고리즘을 수행합니다.
+# 점화식에 따라 플로이드 워셜 알고리즘을 수행
 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])
 
 result = 0
-# 각 학생을 번호에 따라 한 명씩 확인하며 도달 가능한지 체크합니다.
+# 각 학생을 번호에 따라 한 명씩 확인하며 도달 가능한지 체크
 for i in range(1, n + 1):
     count = 0
     for j in range(1, n + 1):
diff --git a/17/3.py b/17/3.py
@@ -1,41 +1,41 @@
 import heapq
 import sys
 input = sys.stdin.readline
-INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정합니다.
+INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
 
 dx = [-1, 0, 1, 0]
 dy = [0, 1, 0, -1]
 
-# 전체 테스트 케이스(Test Case)만큼 반복합니다.
+# 전체 테스트 케이스(Test Case)만큼 반복
 for tc in range(int(input())):
-    # 노드의 개수를 입력 받습니다.
+    # 노드의 개수를 입력받기
     n = int(input())
 
-    # 전체 맵 정보를 입력 받습니다.
+    # 전체 맵 정보를 입력받기
     graph = []
     for i in range(n):
         graph.append(list(map(int, input().split())))
 
-    # 최단 거리 테이블을 모두 무한으로 초기화합니다.
+    # 최단 거리 테이블을 모두 무한으로 초기화
     distance = [[INF] * n for _ in range(n)]
 
-    x, y = 0, 0 # 시작 위치는 (0, 0)입니다.
-    # 시작 노드로 가기 위한 비용은 (0, 0) 위치의 값으로 설정하여, 큐에 삽입합니다.
+    x, y = 0, 0 # 시작 위치는 (0, 0)
+    # 시작 노드로 가기 위한 비용은 (0, 0) 위치의 값으로 설정하여, 큐에 삽입
     q = [(graph[x][y], x, y)]
     distance[x][y] = graph[x][y]
 
-    # 다익스트라 알고리즘을 수행합니다.
+    # 다익스트라 알고리즘을 수행
     while q:
-          # 가장 최단 거리가 짧은 노드에 대한 정보를 꺼냅니다.
+          # 가장 최단 거리가 짧은 노드에 대한 정보를 꺼내기
           dist, x, y = heapq.heappop(q)
-          # 현재 노드가 이미 처리된 적이 있는 노드라면 무시합니다.
+          # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
           if distance[x][y] < dist:
               continue
-          # 현재 노드와 연결된 다른 인접한 노드들을 확인합니다.
+          # 현재 노드와 연결된 다른 인접한 노드들을 확인
           for i in range(4):
               nx = x + dx[i]
               ny = y + dy[i]
-              # 맵의 범위를 벗어나는 경우 무시합니다.
+              # 맵의 범위를 벗어나는 경우 무시
               if nx < 0 or nx >= n or ny < 0 or ny >= n:
                   continue
               cost = dist + graph[nx][ny]
diff --git a/17/4.py b/17/4.py
@@ -1,47 +1,47 @@
 import heapq
 import sys
 input = sys.stdin.readline
-INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정합니다.
+INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
 
-# 노드의 개수, 간선의 개수를 입력 받습니다.
+# 노드의 개수, 간선의 개수를 입력받기
 n, m = map(int, input().split())
-# 시작 노드를 1번 헛간으로 설정합니다.
+# 시작 노드를 1번 헛간으로 설정
 start = 1
-# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만듭니다.
+# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
 graph = [[] for i in range(n + 1)]
-# 최단 거리 테이블을 모두 무한으로 초기화합니다.
+# 최단 거리 테이블을 모두 무한으로 초기화
 distance = [INF] * (n + 1)
 
-# 모든 간선 정보를 입력 받습니다.
+# 모든 간선 정보를 입력받기
 for _ in range(m):
     a, b = map(int, input().split())
-    # a번 노드와 b번 노드의 이동 비용이 1이라는 의미입니다. (양방향)
+    # a번 노드와 b번 노드의 이동 비용이 1이라는 의미(양방향)
     graph[a].append((b, 1))
     graph[b].append((a, 1))
 
 def dijkstra(start):
     q = []
-    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입합니다.
+    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
     heapq.heappush(q, (0, start))
     distance[start] = 0
     while q: # 큐가 비어있지 않다면
-        # 가장 최단 거리가 짧은 노드에 대한 정보를 꺼냅니다.
+        # 가장 최단 거리가 짧은 노드에 대한 정보를 꺼내기
         dist, now = heapq.heappop(q)
-        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시합니다.
+        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
         if distance[now] < dist:
             continue
-        # 현재 노드와 연결된 다른 인접한 노드들을 확인합니다.
+        # 현재 노드와 연결된 다른 인접한 노드들을 확인
         for i in graph[now]:
             cost = dist + i[1]
             # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
             if cost < distance[i[0]]:
                 distance[i[0]] = cost
                 heapq.heappush(q, (cost, i[0]))
 
-# 다익스트라 알고리즘을 수행합니다.
+# 다익스트라 알고리즘을 수행
 dijkstra(start)
 
-# 가장 최단 거리가 먼 노드 번호 (동빈이가 숨을 헛간의 번호)
+# 가장 최단 거리가 먼 노드 번호(동빈이가 숨을 헛간의 번호)
 max_node = 0
 # 도달할 수 있는 노드 중에서, 가장 최단 거리가 먼 노드와의 최단 거리
 max_distance = 0
diff --git a/18/1.py b/18/1.py
@@ -14,9 +14,9 @@ def union_parent(parent, a, b):
     else:
         parent[a] = b
 
-# 여행지의 개수와 여행 계획에 속한 여행지의 개수 입력 받기
+# 여행지의 개수와 여행 계획에 속한 여행지의 개수 입력받기
 n, m = map(int, input().split())
-parent = [0] * (n + 1) # 부모 테이블 초기화하기
+parent = [0] * (n + 1) # 부모 테이블 초기화
 
 # 부모 테이블상에서, 부모를 자기 자신으로 초기화
 for i in range(1, n + 1):
@@ -29,7 +29,7 @@ def union_parent(parent, a, b):
         if data[j] == 1: # 연결된 경우 합집합(Union) 연산 수행
             union_parent(parent, i + 1, j + 1)
 
-# 여행 계획 입력 받기
+# 여행 계획 입력받기
 plan = list(map(int, input().split()))
 
 result = True
diff --git a/18/2.py b/18/2.py
@@ -14,11 +14,11 @@ def union_parent(parent, a, b):
     else:
         parent[a] = b
 
-# 탑승구의 개수 입력 받기
+# 탑승구의 개수 입력받기
 g = int(input())
-# 비행기의 개수 입력 받기
+# 비행기의 개수 입력받기
 p = int(input())
-parent = [0] * (g + 1) # 부모 테이블 초기화하기
+parent = [0] * (g + 1) # 부모 테이블 초기화
 
 # 부모 테이블상에서, 부모를 자기 자신으로 초기화
 for i in range(1, g + 1):
diff --git a/18/3.py b/18/3.py
@@ -14,9 +14,9 @@ def union_parent(parent, a, b):
     else:
         parent[a] = b
  
-# 노드의 개수와 간선의 개수 입력 받기
+# 노드의 개수와 간선의 개수 입력받기
 n, m = map(int, input().split())
-parent = [0] * (n + 1) # 부모 테이블 초기화하기
+parent = [0] * (n + 1) # 부모 테이블 초기화
 
 # 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
 edges = []
@@ -26,7 +26,7 @@ def union_parent(parent, a, b):
 for i in range(1, n + 1):
     parent[i] = i
 
-# 모든 간선에 대한 정보를 입력 받기
+# 모든 간선에 대한 정보를 입력받기
 for _ in range(m):
     x, y, z = map(int, input().split())
     # 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
diff --git a/18/4.py b/18/4.py
@@ -14,9 +14,9 @@ def union_parent(parent, a, b):
     else:
         parent[a] = b
  
-# 노드의 개수 입력 받기
+# 노드의 개수 입력받기
 n = int(input())
-parent = [0] * (n + 1) # 부모 테이블 초기화하기
+parent = [0] * (n + 1) # 부모 테이블 초기화
 
 # 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
 edges = []
@@ -30,7 +30,7 @@ def union_parent(parent, a, b):
 y = []
 z = []
 
-# 모든 노드에 대한 좌표 값 입력 받기
+# 모든 노드에 대한 좌표 값 입력받기
 for i in range(1, n + 1):
     data = list(map(int, input().split()))
     x.append((data[0], i))
diff --git a/18/5.py b/18/5.py
@@ -66,7 +66,7 @@
                 if indegree[i] == 0:
                     q.append(i)
 
-    # 사이클이 발생하는 경우 (일관성이 없는 경우)
+    # 사이클이 발생하는 경우(일관성이 없는 경우)
     if cycle:
         print("IMPOSSIBLE")
     # 위상 정렬 결과가 여러 개인 경우
diff --git a/4/3.cpp b/4/3.cpp
@@ -12,7 +12,7 @@ int main(void) {
     // 현재 나이트의 위치 입력받기
     cin >> inputData;
     int row = inputData[1] - '0';
-    int column = inputData[0] - 'a';
+    int column = inputData[0] - 'a' + 1;
 
     // 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
     int result = 0;
diff --git a/4/3.java b/4/3.java
@@ -8,7 +8,7 @@ public static void main(String[] args) {
         // 현재 나이트의 위치 입력받기
         String inputData = sc.nextLine();
         int row = inputData.charAt(1) - '0';
-        int column = inputData.charAt(0) - 'a';
+        int column = inputData.charAt(0) - 'a' + 1;
 
         // 나이트가 이동할 수 있는 8가지 방향 정의
         int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
@@ -29,4 +29,4 @@ public static void main(String[] args) {
         System.out.println(result);
     }
 
-}
+}
diff --git a/README.md b/README.md
@@ -3,8 +3,7 @@
 
 * 이 저장소는 <b>이것이 취업을 위한 코딩 테스트다 with Python</b> (나동빈 저, 한빛미디어) 전체 소스코드를 포함합니다.
 * 본 책은 Python 3.7 문법을 활용하였으나, 추가적으로 Java, C++11 소스코드를 제공합니다.
-    * 이론 파트에 대한 C++/Java 코드는 2020년 08월 05일까지 모두 업로드 완료됩니다. (완료)
-    * 전체 기출 문제 풀이에 대한 C++/Java 코드는 2020년 08월 08일까지 모두 업로드 완료됩니다.
+    * 전체 책에 대한 C++/Java 코드는 2020년 08월 10일까지 모두 업로드 완료됩니다.
 * 책 내용 및 소스코드와 관련한 궁금한 점은 [Issues](https://github.com/ndb796/python-for-coding-test/issues) 탭을 이용하여 남겨주세요.
 * 책의 오류 사항을 발견하시면 dongbinna@postech.ac.kr로 보내주시면 감사하겠습니다.
     * 이 경우, 원하신다면 <b>[정오표](/notice.md)</b>에 독자님의 이름(혹은 아이디)을 함께 기재해드립니다.
diff --git a/notice.md b/notice.md
@@ -8,12 +8,16 @@
 
 * 맵의 세로 크기 N과 가로 크기 M의 입력 범위는 (3 ≤ N, M ≤ 50)입니다.
 
+#### (143p) BFS 원어 오탈자
+
+* BFS는 Breadth First Search의 약자인데, 책에 d가 빠져 기재되어 있습니다.
+
 #### (197p) '부품 찾기' 문제의 입력 조건 및 소스코드 오류
 
 * 문제의 조건에서 N개의 정수와 M개의 정수 모두 크기는 1보다 크고 1,000,000이하입니다.
 * '계수 정렬'을 이용한 답안에서 array 리스트 변수의 크기는 1,000,001입니다.
 
-#### (221p) 
+#### (221p) 그림 내 오탈자
 
 * 그림 ⓑ에서 그림의 오른쪽 부분은 '털 수 있음'인데 잘못 기재되어 있습니다.
 
@@ -32,3 +36,9 @@
 [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
 [[0, 5, 0, 0], [0, 5, 0, 0], [0, 5, 0, 0]]
 ```
+
+#### (483p) 세 번째 쿼리 설명 오류
+
+* 세 번째 쿼리는 세 번째 수부터 <b>네 번째 수</b>까지의 구간 합을 물어보는 [3, 4]입니다. 
+
+
