파이썬 백준 4963번 실버2 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 보기 분류: 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 풀기 기존 상하좌우 이웃으로 연결된 문제에서 대각선 네 방향에 대해 추가적 처리를 생각한다. matrix 에서 처음으로 1을 발견하면 fnBFS() 를 실행하여 이웃된 8방향 모두 찾아가 1이 보이면 방문 처리한다. 이렇게 남은 matrix 에 대해 조건을 만족하여 fnBFS() 함수에 들어..

파이썬 백준 7576번 골드5 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 보기 분류: 그래프 탐색, 너비 우선 탐색 문제 풀기 BFS 를 사용하여 해결하는 문제이다. 익은 토마토의 위치 좌표를 2차원 deque() 로 먼저 저장을 한다. popleft() 를 통하여 첫 번째 익어있는 토마토의 위치들과 지속적으로 익어가는 토마토의 위치를 순차적으로 꺼내어 모든 매트릭스(그래프)를 탐색할 때까지 반복한다. 이웃하여 다음날..

파이썬 백준 11725번 실버2 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 보기 분류: 그래프 탐색, 트리, 너비 우선 탐색 문제 풀기 루트를 1로 정했기 때문에 1을 부모 노드로 시작하여 그 바로 아래 노드는 1의 자식 노드가 되면서 그 다음 아래 노드의 부모가 된다. 이 규칙을 적용하여 너비 우선 탐색을 이용하여 문제를 해결하였다. 예제 1을 그림으로 나타내면 위와 같다. 위에서 부터 부모 노드 방문을 표시하고 그 아래 자식 노드를 하나씩 deque 에서 꺼내어 부모 노드가 될 수 있는지 (그..

파이썬 백준 2743번 브론즈 https://www.acmicpc.net/problem/2743 2743번: 단어 길이 재기 알파벳으로만 이루어진 단어를 입력받아, 그 길이를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 보기 분류: 구현, 문자열 문제 풀기 입력 데이터를 문자로 저장하고 len() 함수를 이용하여 그 문자의 길이를 출력한다. 코드 보기 import sys inputdata = sys.stdin.readline word = str(inputdata().strip()) print(len(word))

파이썬 백준 14935번 브론즈4 https://www.acmicpc.net/problem/14935 14935번: FA 정수 x가 FA수 라면 FA를 출력하고, 아니라면 NFA를 출력한다. www.acmicpc.net 문제 보기 분류: 수학, 구현, 애드 혹 문제 풀기 주어진 F(x) 함수의 규칙에 따라 코드를 작성한다. int 로 입력받은 주어진 숫자는 리스트에 각 자리별로 나누어 저장하고 리스트 첫 번째 숫자 x_ls[0] 와 리스트 길이 (x 의 자릿수) len(x_ls) 를 곱하여 변수 fx 에 저장한다. fx = x_ls[0] * len(x_ls) 주어진 x 와 계산되어 나온 fx 가 다르면 재귀적으로 fnFXFunction(fx) 를 다시 실행하여 x == fx: 가 될 때까지 반복한다. 생..

파이썬 백준 5063번 브론즈3 https://www.acmicpc.net/problem/5063 5063번: TGN 첫째 줄에 테스트 케이스의 개수 N이 주어진다. 다음 N개의 줄에는 3개의 정수 r, e, c가 주어진다. r은 광고를 하지 않았을 때 수익, e는 광고를 했을 때의 수익, c는 광고 비용이다. (-106 ≤ r,e ≤ 106 www.acmicpc.net 문제 보기 분류: 수학, 사칙연산 문제 풀기 r: 광고를 하지 않았을 때 수익 e: 광고를 했을 때의 수익 c: 광고 비용 r 과 (e - c) 의 크기 비교를 하여 조건에 따라 "advertise", "do not advertise", "does not matter" 를 프린트 한다. 코드 보기 import sys inputdata =..

파이썬 백준 1373번 브론즈1 https://www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 문제 보기 분류: 수학 문자열 문제 풀기 2진수를 3자리씩 묶어 8진수로 변환하는 방법을 사용하였다. https://www.rapidtables.com/convert/number/binary-to-octal.html Binary to Octal Converter From Binary Decimal Octal Hexadecimal Text To Binary Decimal Octal Hexadecimal Text www.rapidtables.com 입력받은 2진수를 문자로..

파이썬 백준 10569번 브론즈3 https://www.acmicpc.net/problem/10569 10569번: 다면체 수학자가 구를 깎아서 볼록다면체를 만들었다. 이 수학자는 임의의 볼록다면체에 대해 (꼭짓점의 수) - (모서리의 수) + (면의 수) = 2가 성립한다는 것을 알고 있다. 그래서 구를 깎는 게 취미인 www.acmicpc.net 문제 보기 분류: 수학, 기하학, 사칙연산, 오일러 지표 문제 풀기 주어진 수식 (꼭짓점의 수) - (모서리의 수) + (면의 수) = 2 를 (면의 수) 에 대해 정리한 후 간단한 사칙 연산 계산으로 해결한다. 테스트의 수 T 를 입력받아 그 수 만큼 for loop 을 실행하고 V 와 E 를 입력받아 수식 NoP = 2 - V + E 에 대입하여 계산 후..

파이썬 백준 1946번 실버1 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 보기 분류: 그리디 알고리즘, 정렬 문제 풀기 순위를 2차원 리스트로 입력받아 오름차순 정렬을 하고 순차적인 서류 등수 순번대로 면접 등수를 비교하여 우위에 있는 지원자를 찾는다. 조건을 만족할때 hired 를 하나씩 늘려 선발되는 지원자의 수를 출력한다. 코드 보기 import sys inputdata = sys.stdin.readline..

파이썬 백준 13023번 골드5 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 보기 분류: 그래프 탐색, 깊이 우선 탐색 문제 풀기 사람 다섯명이 연속적으로 주루룩 4번 이상의 연결이 형성되면 문제에서 제시한 관계가 만족한다. 맞으면 1, 아니면 0. 주어진 입력을 graph (relationships) 로 저장하여 모든 사람에 대해 연속 4번의 관계가 만족하는지 모두 탐색해 본다. 이때, DFS 가 재귀함수로 4번이 실행되면 fnDFS 를 result == True 로 나와 관계를 만족하여 1 을 출력하고, 그렇지 않고 4번의 재귀가 일어나..