아이테킨의 끄적끄적

빠트리지 않고 탐색하는 것과 이미 탐색했던 조합은 Pass할 수 있도록 알고리즘을 짜야 한다. 마지막으로 물통사이를 왔다갔다할 때 물이 넘치는지 모자라는지 체크하고 문제에서 요구한 조건(A의 통이 비어있을때)에 부합할때 C통에 남아있는 물을 저장해두면 된다. 참고 : https://pacific-ocean.tistory.com/392 # 2251번: 물통 a,b,c = map(int,input().split()) ans = [] from collections import deque q = deque() q.append([0,0,c]) check = [[0] * 201 for i in range(201)] ans = [0 for i in range(201)] def bfs(): while q: x,y,z ..

기본적인 탐색문제로 DFS,BFS알고리즘중 하나를 선택해서 풀면 된다. 나는 DFS를 이용해서 풀었고 DFS알고리즘은 재귀함수를 사용하기 때문에 미리 재귀깊이를 늘려놓는것이 편하다. dfs함수를 만들어주고 check라는 리스트에 계속해서 숫자를 더하는 방법으로 촌수를 계산해보았다. # 2644번: 촌수계산 import sys sys.setrecursionlimit(10*5) def dfs(node): for n in graph[node]: if check[n] == 0: check[n] = check[node]+1 dfs(n) n = int(input()) graph = [[] for _ in range(n+1)] s,e = map(int,input().split()) for _ in range(int(..

이 문제는 루트노드가 1로 가정하고 있으므로 2번부터 n-1번까지 순서대로 노드들의 부모노드를 찾아서 출력해주면 되는 문제이다. 탐색문제이므로 dfs,bfs 등 편한 알고리즘을 사용하면 될 것 같다. 나는 dfs알고리즘을 이용해서 풀어보았다. 우선 dfs알고리즘을 사용할 때는 재귀의 깊이를 늘려놓는 것이 편하다. 그리고 트리구조를 표현할 때 인접리스트(adjacent list)방식으로 표현했다. 인접리스트만으로는 부모와 자식노드의 관계를 알 수는 없다. 따라서 parent리스트를 따로 만들어서 순서대로 부모노드를 넣어주었다. # 11725번: 트리의 부모 찾기 import sys sys.setrecursionlimit(10**6) n = int(input()) adj_list = [[] for _ in ..

dfs방법으로 풀어보았다. 이번 문제에서는 print(*list)에 대해서 알 수 있게 되었다. 원래는 for 루프를 이용해서 sep연산자와 함께 사용해서 리스트를 출력했었는데 블로그를 통해서 리스트를 파이썬 *연산자와 함께 출력하면 깔끔하게 보기좋게 출력된다. 더 알아보고 싶으신 분들은 https://www.askpython.com/python/list/print-a-python-list https://www.daleseo.com/python-lists-print/ 위의 링크들 참조하면 좋을것 같다. import sys sys.setrecursionlimit(10000) m,n,k = map(int,input().split()) # 1. 그림그리기 graph = [[0]*n for i in range(..

dfs로 탐색문제이다. dfs는 재귀,스텍 자료구조를 이용하는 알고리즘인데 어짜피 같은 원리이지만 나는 주로 재귀를 사용해서 문제를 푼다. dfs알고리즘은 문제를 반복적으로 풀어보게 되면 익숙해질것이고 이 문제는 적록색약(녹색과 빨간색을 구분 못하는 사람)을 신경써서 풀어줘야 하는데 나는 그냥 graph를 딥카피 한후에 R를 G로 바꿔버렸다. 반복문을 많이 쓰게 되서 시간초과가 날까 걱정이 되기도 했는데 일단 통과는 되었다. :) import copy import sys sys.setrecursionlimit(100000) n = int(input()) graph = [] for _ in range(n): i = list(map(str,input())) graph.append(i) graph2 = cop..

bfs탐색 알고리즘을 통해서 풀 수 있는 문제다. 이 문제에서 신경써야 하는 부분은 보통은 상하좌우만 탐색을 하는 문제가 많았는데 이번 문제는 대각선까지 탐색을 해야 한다. # 4963번: 섬의 개수 # 상하좌우대각선까지 dx = [0,0,-1,1,1,1,-1,-1] dy = [1,-1,0,0,1,-1,1,-1] from collections import deque def bfs(w,h): cnt = 0 for x in range(h): for y in range(w): if graph[x][y] == 1: cnt += 1 q = deque() q.append([x,y]) while q: a,b = q.popleft() for i in range(8): nx = a + dx[i] ny = b + dy[i..

2가지 알고리즘을 이용하여 풀 수 있다. 1. BFS 2. bruteforce 첫번째로 BFS알고리즘은 주어진 그래프에서 탐색을 하기 위한것이므로 BFS문제를 많이 풀어본 사람이라면 쉽게 풀 수 있을것이다. 두번째로 이 문제에서 bruteforce는 벽을 세울 때 사용한다. 문제에서 입력값의 범위가 크지 않으므로 모든 범위를 계산해서 제일 큰 값을 고르면 된다. 참고로 제출할 때 python3이 아닌 pypy3로 제출해야 통과된다. python은 시간초과가 뜬다. 왜 이렇게 다른지는 나중에 ㅠㅠ 아이디어를 코드로 구현하는 것과 여러가지 환경설정에 대해서 알아야 할 부분도 많다 ㅠㅠ 가야할 길이 많지만 차근차근 꾸준히 걸어가자! # 14502번: 연구소 from collections import deque..

기본적인 탐색문제인 듯 하다. 이 문제는 DFS로 풀 수 있는데 푸는 방법을 굳이 나눠보자면 인접행렬과 인접리스트 방식으로 풀 수 있다. 이 차이는 그래프를 표현하는 방식의 차이일뿐 본질적인 차이는 없다. 표현 방식에 따라서 코딩을 해주면 된다. 나는 인접행렬 형식으로 풀어보았다. 인접리스트 방식으로 푼 풀이가 궁금하신 분들은 https://hjp845.tistory.com/33 여기 블로그에 코드가 있으니 참고하면 된다. 그러나 알고리즘이 아닌 다른 부분에서 좀 해맸다. 1. sys.setrecursionlimit(10000) 재귀를 사용할 땐 항상 재귀의 깊이를 넉넉하게 설정해주는 것을 잊지 말아야 한다. 이걸 안해주면 런타임에러(recursuionerror)가 뜬다. 2. sys.stdin.read..

최단거리를 찾는 문제이므로 bfs탐색 알고리즘을 사용하면 쉽게 풀수 있다. 또 시간초과가 떳다. 이게 시간초과가 뜬 내가 만든 코드이고 from collections import deque import sys input = sys.stdin.readline def bfs(): while queue: x,y = queue.popleft() for step in range(8): nx,ny = x + dx[step], y+dy[step] if 0

이 코드로 했더니 테스트케이스의 답들은 잘 나오는데 시간초과가 떠버렸다. 3차원 배열을 사용해야 하는 문제라서 반복문 3개를 썻다고 시간초과가 나오는 건 아닐거라고 생각한다. 확실한 이유는 아닐 수도 있지만 내 생각에 중간에 zip내장함수를 이용해서 좌표를 만들어낼때 내부적으로 연산이 더 되는게 아닌가 싶다. 사실 잘 모르겠다. 어떤 부분에서 시간 초과가 나는지...ㅠㅠ # 7569 토마토 3차원 문제 import sys input = sys.stdin.readline m,n,h = map(int,input().split()) graph = [[] for _ in range(h)] for i in range(h): for _ in range(n): graph[i].append(list(map(int,in..