Goyummy

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

다음에 풀어볼 백준 문제는 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/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 잘못 짠 코드 import sys N_2 = sys.stdin.readline() N_10 = int(N_2, 2) N_8 = '' while N_10 != 0: N_8 += str(N_10 % 8) N_10 = N_10 // 8 print(N_8[::-1]) 이렇게 짜니 시간 초과가 나왔다. 알고보니 oct()라는 8진수로 바꾸어주는 함수가 있어서 이를 활용했다. 정답 코드 import sys print(oct(int(sys.stdin.readline(), 2))[2:])

문제 링크 https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net int(‘문자’,숫자) 로 해야하기 때문에 N과 B를 문자로 받고 이후에 B를 정수로 바꿔주었다. int(N,B) -> B진수인 N을 10진수로 나타내주세요. 정답 코드 import sys N, B = sys.stdin.readline().split() print(int(N, int(B)))

문제 링크 https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net N을 더이상 나눌 수 없을 때까지 36으로 나누고 거기서 나온 나머지를 바꿀 진법의 수(문자)로 바꾸었다. 그대로 출력하면 거꾸로 나오기 때문에 순서를 뒤집어서 출력해주어야 제대로 나온다. 정답 코드 import sys tmp = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" N, B = map(int, sys.stdin.readline().split()) ..