[백준/Python] 13023 ABCDE
문제 링크 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 풀이 5명이 한 번에 연결되어 있다면 1을 출력, 아니면 0을 출력한다. 리스트 안의 값을 처음부터 반복문을 돌리면서 탐색한다. 만약 깊이 우선 탐색을 진행하다가 더 이상 진행할 수 없을 때는 다시 돌아와야 하므로, 기존 방문했던 값을 다시 False로 바꿔야 한다. 전체 코드 import sys sys.setrecursionlimit(10 ** 7) def dfs(s, v, c): global res v[s] = True if c == 5: res = 1 return for i in arr[s]: if not v[i]: dfs(i, v, c+1) v[..
[백준/Python] 16564 히오스 프로게이머
문제 링크 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ Xi ≤ www.acmicpc.net 문제 풀이 일반적인 이분 탐색 문제이다. 여기서 주의해야 할 점은 end 값 설정이다. 만약 캐릭터 레벨의 총합(sum(arr))보다 k가 무수히 크다면 end 값은 단순히 총합이 아닌 총합과 k를 더한 값이 되어야 한다. 전체 코드 import sys n, k = map(int, sys.stdin.readline().split()) arr = [int(sys.stdin.r..
[백준/Python] 2170 선 긋기
문제 링크 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 문제 풀이 먼저, 입력 받은 리스트를 시작점(x[0])에 대해서 오름차순 정렬하고, 끝점(x[1])에 대해서 오름차순 정렬을 한다. 처음의 시작점과 끝점은 각각 리스트의 첫 번째가 되는데, 이 때, 총 길이의 값을 끝점에서 시작점을 뺀 값으로 저장한다. 이후 인접한 두 선분은 총 6가지의 케이스가 나오게 되는데, 각 2가지의 케이스씩 묶어서 생각할 수 있다. 첫 번째는 선분 l1의 끝점이 선분 l2의 시작점보다 큰 경우..
[백준/Python] 10026 적록색약
문제 링크 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 풀이 위 문제는 dfs, bfs 두 가지 방법으로 모두 풀이가 가능하다. 적록색약이 아닌 사람은 R, G, B 모두 다르게 인식하지만, 적록색약인 사람은 R, G를 구분하지 못하므로, 입력 받은 리스트에서 G인 부분을 R로 바꾸어 새로운 리스트를 생성하였다. 방문 처리 리스트(visited)를 통해서 시작 위치를 방문하지 않았으면 함수(dfs, bfs)를 실행한다. 이때, 해당 함수는 시작 위치와 동일한 위치에 대해서만 방문 처리를 하게 된..