Goyummy

문제 링크 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(..

다음에 풀어볼 백준 문제는 DFS, BFS 와 관련된 것인데 처음 들어보는 것이라 공부를 해보았다. ( 참고 : https://youtu.be/7C9RgOcvkvo ) 1. 스택과 큐 스택 : 선입 후출, 입구와 출구가 동일한 형태로 스택을 시각화한다. 파이썬에서는 append()와 pop() 메소드를 이용하면 스택 구현이 가능하다. print(stack[::-1]) 최상단부터 출력, print(stack) 최하단부터 출력할 수 있다. c++에서는 push()와 pop()으로 구현할 수 있다. 큐 : 선입 선출, 입구와 출구가 모두 뚫려있는 터널 형태로 스택을 시각화한다. from collections import deque => 큐 구현을 위해 deque 라이브러리를 사용한다. 코드를 작성할 때, ‘q..

문제 링크 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)

문제 링크 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 수를 나눌 수 있을 만큼 계속 나누고 나눌 수 없을 때, m에 1을 더한다. 정답 코드 import sys number = int(sys.stdin.readline()) m = 2 while number != 1: if number % m == 0: print(m) number //= m else: m += 1

문제 링크 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 소수를 판별하는 함수는 저번 1929번 문제의 ‘에라토스테네스의 체’ 를 그대로 가져왔다. b = number - a를 하고 에라토스테네스의 체 방식을 사용하여 a와 b가 소수인지 판별하였다. 정답 코드 import sys def isPrime(num): if num==1: return False else: for i in range(2, int(num**0.5)..

문제 링크 잘못 짠 코드 import sys M, N = map(int,sys.stdin.readline().split()) def prime_number(number): if number != 1: for i in range(2,number): if number % i == 0: return False else: return False return True for i in range(M, N+1): if prime_number(i) == True: print(i) 직전의 문제와 비슷해서 비슷하게 풀었는데 시간 초과가 나왔다. 다른 사람들의 질문을 보니 ‘에라토스테네스의 체’를 이용하면 시간을 줄일 수 있다고 한다. num**0.5을 하는 이유는 모든 약수들은 대칭 형태를 가지고 있기 때문이다. ( 8 ..

문제 링크 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net def prime_number(number): if number != 1: for i in range(2,number): if number % i == 0: return False else: return False return True 이 함수를 먼저 작성해서 문제에 적용시켰다. 먼저 1이 아닌 숫자를 1과 자기 자신으로 나누어지면 False를 반환시켜서 한번 거르고, else를 이용하여 1을 걸렀다. 마지막에 return True 를 이용하여 두 조건에..