Goyummy

문제 링크 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 함수에서 마지막에 ‘이미 방문했던 노드는 방문하지 않는다.’에 그 두개의 노드가 같은 집합(색)인지 판단하는 코드를 추가해야함. 이분 그래프가 아니면 더이상 탐색하지 않아야함. 이분 그래프를 몰라서 유튜브 영상과 블로그 글을 보고 이해했다. ..

문제 링크 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net dfs를 이용하여 1이 들어있는 연결된 요소 하나를 찾고 for문과 if를 활용해서 만약 연결되지 않은 노드가 있다면 그 요소들끼리 또 묶어주었다. 그리고 그 연결된 요소가 몇개인지 알기 위해 result 리스트를 사용하였다. 자꾸 recursion error가 났었는데 이는 파이썬에서 설정한 재귀 깊이를 넘어서 그런 것이었..

문제 링크 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS, BFS 유형을 처음 접해보는 내 입장에서는 정말 어려운 문제였다. 이 문제를 반복해서 풀어봐야 할 것 같다. 정답 코드 import sys from collections import deque N, M, V = map(int, sys.stdin.readline().split()) graph = [[0]*(N+1) for i in range(..

문제 링크 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net n과 m의 수 범위가 굉장히 크기 때문에, 이전에 팩토리얼 0의 개수 문제를 풀 때 썼던 방법을 그대로 쓰면 시간 초과가 났다. 그래서 다른 방법을 찾아보았다. 조합은 ‘n! / (n-m)!*m!‘ 이다. 여기서 생기는 2와 5의 개수를 통해 뒷자리에 생기는 0의 개수를 구해야한다. 조합 공식을 참고해서, ‘n!의 2의 개수 - (n-m)!의 2의 개수 - m!의 2의 개수' 를 이용하여 2의 개수를 구해야한다. 5의 개수도 마찬가지다. coun..

문제 링크 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 숫자는 인덱싱이 안되기 때문에 str(factorial)을 이용해 문자로 만들고 인덱싱이 되게 하였다. 정답 코드 import sys N = int(sys.stdin.readline()) factorial = 1 for i in range(1,N+1): factorial *= i factorial = str(factorial) result = 0 for i in range(len(factorial)-1,-1,-1): if factorial[i] == '0': result ..

문제 링크 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 정답 코드 import sys N = int(sys.stdin.readline()) result = 1 for i in range(1,N+1): result *= i print(result)