Goyummy

문제 링크 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net __init__ : 생성자라고 불리는 초기화를 위한 함수. 인스턴스화를 할 때 반드시 처음 호출되는 함수. 오브젝트 생성(인스턴스 생성)과 관련하여 데어터의 초기화를 실시하는 함수. __init__은 반드시 첫번째 인수로 self를 지정해야함. 클래스 생성할 때에 지정된인수는 초기화 메소드의 2번째 부터 작성. 전위 순회, 중위 순회, 후위 순회를 하는 코드를 작성할 때, 각..

문제링크 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net bfs를 두번 쓰는 문제는 처음이라 어려웠다. 한 섬에서 다른 섬으로 가는 최단 거리를 찾는 문제다. 그래서 이 문제에서 해야 할 일은 섬 구분하기, 최단 거리 찾기가 있다. 이를 위해 bfs를 두번 사용해야한다. 나중에 한번 더 풀어봐야 할 문제다. 정답 코드 import sys from collections import deque dx = [-1,1,0,0] dy = [0,0,-1,1] d..

문제 링크 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 7576번 토마토 문제와 유사하다. 앞에서 선언한 미로의 크기에서만 움직일 수 있도록 if 문을 사용하였다. 그리고 (0,0)에서 한 칸씩 나아갈 때마다 그 미로 칸의 값에 +1씩 해주어 최종적으로 마지막 칸에 도착했을 때의 값을 출력하면 얼마나 이동했는지 알 수 있다. 정답 코드 import sys from collections import deque def bfs(x,y): dx = [-1,1,0,0] dy = [..

문제링크 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 여러 개의 익은 토마토로부터 시작하기 위해, 큐를 함수 밖에서 선언하고 큐 삽입을 선언한다. 정답 코드 import sys from collections import deque def bfs(): while queue: x, y = queue.popleft() for i in range(4): pointX = x + dx[i] pointY = y + dy[i] if 0

문제 링크 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 2667번과 아주 유사한 문제다. 2667번에서는 델타값을 dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] 으로 주었지만 이번 4963번 문제에서는 대각선 방향만 추가해주어야 한다. 그래서 델타 값을 dx = [0, 0, -1, 1, -1, -1, 1, 1] dy = [-1, 1, 0, 0, -1, 1, -1, 1] 로 주었다. 계속 list out of ran..

문제 링크 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 파이썬 델타 값 이용하기 dx = [0,0,-1,1] dy = [-1,1,0,0] for i in range(4): pointX = x + dx[i] pointY = y + dy[i] => i = 0 pointX = x , pointY = y - 1 : 왼쪽 노드 i = 1 pointX = x , pointY = y + 1 : 오른쪽 노드 i = 2 pointX = x - 1 , poin..

문제 링크 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net dfs를 실행하고, 방문되지 않는 노드를 no_team에 추가한다. 그리고 순환의 시작점과 마지막이 같으면 no_team에서 제외하려고 했었다. 하지만, 순환하지 않으면서 다시 방문되지 않는 노드가 결과에 포함이 안되어 오답이었다. 잘못 작성한 코드 import sys sys.setrecursionlimit(10 ** 6) T = int(sys.stdin.readline()) def dfs(..

문제 링크 https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net A를 문자열로 바꾸고 인덱싱하여 수열 계산을 진행시켰다. 그리고 반복되는 구간이 나타나게 되는(똑같은 수가 나타나는 때)에 index()를 활용하여 그 반복되는 숫자가 배열에 처음 나타나는 인덱스를 저장시켰다. 정답 코드 import sys A, P = map(int,sys.stdin.readline().split()) arr = [A] while True: result = 0 for i in range(len(str(A))): result += int(str(A)[i])**P A = result..

문제 링크 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 배열의 인덱스 1,2,3,…을 이용하는 것이라서 graph를 따로 만들어서 풀 필요가 없었다. dfs를 한번 실행했어도 방문하지 않은 노드가 남아있는 것이라면 순열 사이클의 개수가 더 남아있는 것이다. 정답 코드 import sys sys.setrecursionlimit(10 ** 6) T = int(sys.std..

문제 링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프: 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프. 모든 노드로 DFS 해보아야함. DFS 함수에서 마지막에 ‘이미 방문했던 노드는 방문하지 않는다.’에 그 두개의 노드가 같은 집합(색)인지 판단하는 코드를 추가해야함. 이분 그래프가 아니면 더이상 탐색하지 않아야함. 이분 그래프를 몰라서 유튜브 영상과 블로그 글을 보고 이해했다. ..