알고리즘
[백준/알고리즘] #2178: 미로탐색 [파이썬(python)/그래프/BFS]
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net #2178_미로탐색 from collections import deque N, M = map(int, input().split()) maze = [] for _ in range(N): maze.append(list(map(int, input()))) def bfs(x,y): dx=[-1,1,0,0] dy=[0,0,-1,1] q=deque() q.append((x,y)) while q: x,y=q.popleft() for i in..
[백준/알고리즘] #1110: 더하기 사이클 [파이썬(python)/수학]
https://www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net #1110_더하기 사이클 n = int(input()) num=n cnt = 0 while (1): ten = num // 10 one = num % 10 plus = (ten+one) % 10 num = one*10 + plus cnt +=1 if (num==n): break print(cnt)
[백준/알고리즘] #5639: 이진검색트리 [파이썬(python)/트리]
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net #5639_이진검색트리 import sys sys.setrecursionlimit(1000000000) input = sys.stdin.readline def postorder(left,right): if left > right: return else: root=preorder[left] div = right+1 for i in range(left+1,right+1): if root
[백준/알고리즘] #1991: 트리순회 [파이썬(python)/트리]
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net #1991_트리순회 import sys input = sys.stdin.readline N = int(input()) def preorder(root): if root != '.': print(root, end='') preorder(tree[root][0])#left preorder(tree[root][1])#right def inorder(root): #중위 if root!='.':..
[백준/알고리즘] #9934: 완전 이진 트리 [파이썬(python)/트리]
https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net #9934_완전이진트리 import sys input = sys.stdin.readline K=int(input()) tree = list(map(int,input().split())) bin_tree = [[] for _ in range(K)] def binary_search(tree,depth): if len(tree)==1:#last layer bin_tree[dep..
[백준/알고리즘] #11279: 최대 힙 [파이썬(python)/자료구조/우선순위 큐]
https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net #11279_최대힙 #https://www.daleseo.com/python-heapq/ import sys import heapq input = sys.stdin.readline N = int(input()) heap = [] for _ in range(N): num = int(input()) if num==0: if heap: print(heapq.heappop(heap)[..
[백준/알고리즘] #2475: 검증수 [파이썬(python)/수학]
https://www.acmicpc.net/problem/2475 2475번: 검증수 컴퓨터를 제조하는 회사인 KOI 전자에서는 제조하는 컴퓨터마다 6자리의 고유번호를 매긴다. 고유번호의 처음 5자리에는 00000부터 99999까지의 수 중 하나가 주어지며 6번째 자리에는 검증수가 들 www.acmicpc.net import sys input = sys.stdin.readline s = [i ** 2 for i in map(int, input().split())] print(sum(s) % 10)
[백준/알고리즘] #2576: 홀수 [파이썬(python)/수학]
https://www.acmicpc.net/problem/2576 2576번: 홀수 7개의 자연수가 주어질 때, 이들 중 홀수인 자연수들을 모두 골라 그 합을 구하고, 고른 홀수들 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어, 7개의 자연수 12, 77, 38, 41, 53, 92, 85가 주어지 www.acmicpc.net import sys input = sys.stdin.readline xx=[] for _ in range(7): x = int(input()) if x % 2 != 0: xx.append(x) if xx: print(sum(xx)) print(min(xx)) else: print(-1)
[백준/알고리즘] #10164: 격자상의 경로 [파이썬(python)/수학/DP]
https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 32점을 받아서 부분성공했다... 100점을 어떻게 해야 받는건지 모르겠다.. 점화식 세운다고 굿노트 한장을 꽉 채워서 계속 적어보았는데.. 난 아무래도 돌머리인거같다 허헣 ^___^ #10164_격자상의경로 import sys input = sys.stdin.readline N, M, K = map(int, input().split()) #N:행, M:열 (..
[백준/알고리즘] #2583: 영역 구하기 [파이썬(python)/그래프/DFS/BFS]
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net #2583_영역 구하기 import sys from collections import deque input = sys.stdin.readline M, N, K = map(int, input().split()) #M:세로, N:가로 (상하반전) dy = [-1,1,0,0] dx = [0,0,-1,1] graph = [list([0]*N) for _ in range(M)] def ..
[백준/알고리즘] #1009: 분산처리 [파이썬(python)/수학]
https://www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net #1009_분산처리 import sys input = sys.stdin.readline T = int(input()) A=[] B=[] for _ in range(T): a,b = map(int,input().split()) A.append(a) B.append(b) for i in range(T): one = A[i] % 10 if one == 0: print(10) elif one in [1,5,6]: ..
[백준/알고리즘] #2750: 수정렬하기 [파이썬(python)/정렬]
https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net import sys input = sys.stdin.readline N = int(input()) n = [] for _ in range(N): n.append(int(input())) n.sort() for i in range(N): print(n[i], end='\n')
[백준/알고리즘] #2468: 안전 영역 [파이썬(python)/DFS/BFS]
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 처음엔 문제를 대충 읽고 단순히 4를 기준으로 물이 잠기고 안 잠기는거를 BFS로 카운트하는 문제인줄 알았다. 답이 자꾸 다르게 나와서 다시 읽어보니 '물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. ' 라고 적혀있었다. 기존의 BFS문제 구현과 다르게 행열크기만큼 반복문을 "그 최대인 크기"만큼 또 매번..
[백준/알고리즘] #7576: 토마토 [파이썬(python)/DFS/BFS]
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이 문제는 시작 지점이 2곳 이상인 좌표를 동시에 BFS 구현하는 문제다. 기존에 풀었던 BFS 유형과 다르게 재귀가 아니라 큐에 토마토 판을 백업해둔 후, 방향좌표로 색칠하고 개수를 세는 문제다. 파이썬 코드 #7576_토마토 import sys from collections import deque input = sys.stdin.readline def bfs(): dx = [-..
[백준/알고리즘] #5622: 다이얼 [파이썬(python)/문자열]
https://www.acmicpc.net/problem/5622 5622번: 다이얼 첫째 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 단어의 길이는 2보다 크거나 같고, 15보다 작거나 같다. www.acmicpc.net 처음엔 아스키코드로 바꿔 정수로 계산할까 했었는데, 더 복잡해질 것 같아서 그냥 인덱스별 묶은 리스트를 선언해서 인덱스로 계산했다. 이게 훨씬 간단한 것 같다. 1은 비어있는 다이얼이라 그냥 _ 널값을 넣었고 마지막 2초도 따라서 계산해주지 않았다. 파이썬 코드 #5622_다이얼 import sys input = sys.stdin.readline word = input() alph = ['_','ABC','DEF','GHI','JKL','MNO','PQRS','TUV','WXYZ'..
[백준/알고리즘] #18352: 특정 거리의 도시 찾기 [파이썬(python)/DFS/BFS]
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 첫 번호를 지정하는 문제는 처음이라 deque() 선언하고 append로 X를 넣었었는데 채점하다가 60%쯤에서 자꾸 틀렸습니다 로 떴다. 다른 풀이들 참고해서 처음 큐 선언부터 deque([X])로 해주니 해결되었다. visited를 다 0으로 채워서 선언하는 게 익숙했었는데, visited에 카운트하는 경우에는 아예 in..
[백준/알고리즘] #1890:점프 [파이썬(python)/DFS/BFS]
https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 처음에 문제를 이해 못해서... 결국 예제 하나하나 그려보고나서야 이해했다...ㅎㅎ 예제 따라 저렇게 3가지 경우의 수가 나오므로 답이 3이다. 간단한 DFS/BFS 정석적인 문제 같은데 또 새로운 풀이의 DFS/BFS 문제여서 고민했다. (많이 많이 풀어보는 수 밖에......) 갈 수 있는 방향이 목표지점까지로만 갈 수 있도록 제한되어있다. 사이클은 안된다. 오른쪽과 아래쪽으로만 움..
[백준/알고리즘] #2667: 단지붙이기 [파이썬(python)/DFS/BFS]
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net DFS/BFS를 이용해서 각각의 기준점 별 거리계산하는 문제다. 문제에 "오름차순으로 정렬하여 출력"을 제대로 못 봐서 첫시도에 틀렸다. 문제를 똑바로 잘 읽자! ^^ dfs와 bfs 둘다 이용하여 풀어보았다. bfs는 큐를 두고 좌표로 이동하며 카운트하고 dfs는 카운트를 글로벌 변수로 두고 재귀로 풀이하였다. 이런 문제에서는 둘 다 수행시간이 비슷한가보다. 파이썬 코드 #2667_단지번호붙이기_..
[백준/알고리즘]#4963: 섬의 개수 [파이썬(python)/그래프/DFS/BFS]
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net https://hidemasa.tistory.com/136 [백준/알고리즘]#1303: 전쟁-전투 [파이썬(python)/그래프/DFS/BFS] https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 ..
[백준/알고리즘]#1303: 전쟁-전투 [파이썬(python)/그래프/DFS/BFS]
https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 그래프 DFS/BFS이론을 통해 푸는 문제다. BFS/DFS도 유형별로 푸는 방법이 달라지는데, 이 문제의 경우는 각각 기준점 별로 거리를 계산하는 문제다. 이와 비슷한 문제로는 #2667: 단지번호 붙이기 https://www.acmicpc.net/problem/2667 #4963: 섬의 개수 https://www.acmicpc.net/problem/4963 가 있다. ..