땃쥐네

문제 플랫폼 : 백준 번호 : 01074 제목 : Z 난이도 : Silver 1 N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력 문제 : 링크 필요 지식 분할 정복 풀이 삽질 n = 0 r = 0 c = 0 find = False count = -1 def main(): global n, r, c n, r, c = map(int, input().split()) divide_and_conquer(0, 0, 2 ** n) print(count) def divide_and_conquer(start_r, start_c, length): global count, find if find: return if length == 1: count += 1 if start_r == r and start_c == ..

문제 플랫폼 : 백준 번호 : 02230 제목 : 수 고르기 난이도 : Gold 5 차이가 M이상인 두 수들의 차 중 가장 작은 차이를 출력 문제 : 링크 필요 지식 이분탐색 투 포인터 풀이 입출력 import sys src = sys.stdin.buffer def main(): _, m = map(int, src.readline().split()) nums = sorted(set(int(x) for x in src.read().splitlines())) print(solution(nums, m)) main() 첫 줄 읽기는 sys.stdin.buffer.readline() 나머지 줄 읽기는 sys.stdin.buffer.read().splitlines()를 사용하였다. 이렇게 구한 값들을 int로 변환..

문제 플랫폼 : 백준 번호 : 01865 제목 : 웜홀 난이도 : Gold 3 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력 문제 : 링크 필요 지식, 해석 벨먼-포드 알고리즘 출발 정점에서 어떤 정점에 도착하기까지 기껏 많아봐야 N-1번의 간선을 순회하게 된다. 따라서 n-1번 모든 간선을 탐색하면서 이동비용을 최적화시키면 비용이 완전히 최적화된다. 그런데, 음의 사이클이 발생한다면 여기서 한 번 더 간선을 탐색했을 때 비용이 더 줄어드는 지점이 발생한다. 음의 가중치를 간선이 포함됐을 때 음의 사이클 발생여부 감지는 이 방식을 통해 수행하면 된다. 벨먼 포드 알고리즘의 시간복잡도는 O(NE)이다. 문제의 특수성 이 문제는 시작점이 주어지지 않았다. 각 지..

문제 플랫폼 : 백준 번호 : 02606 제목 : 바이러스 난이도 : Silver 3 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성 문제 : 링크 필요 알고리즘 DFS BFS 풀이 풀이1 : DFS import sys print = sys.stdout.write input = sys.stdin.readline n = int(input()) graph = {i: [] for i in range(1, n + 1)} check = [False] * (n + 1) for _ in range(int(input())): s, e = map(int, input().split()) graph[s].append(..

문제 플랫폼 : 백준 번호 : 02018 제목 : 수들의 합 5 난이도 : Silver 5 자연수 N을 연속된 자연수의 합으로 나타내는 가지수를 출력 문제 : 링크 필요 알고리즘 투포인터 0부터 시작한 연속된 정수에게 남은 수를 균등하게 분할하기 풀이 풀이1 : 투포인터 사용 n = int(input()) lt, rt = 1, 2 count = 1 # 자기 자신을 센 것 sum = 3 while lt 15 15 = (0 + 1) + 14 -> 연속된 숫자 2개에 14를 둘로 나눠서 분배 가능 (o) -> 7 + 8 15 = (0 + 1 + 2) + 12 -> 연속된 숫자 3개에 12를 셋으로 나눠서 분배 가능 (o) -> 4 + 5 + 6..

문제 플랫폼 : 백준 번호 : 24389 제목 : 2의 보수 난이도 : Bronze 1 2의 보수는 해당하는 숫자의 모든 비트를 반전시킨 뒤, 1을 더해 만들 수 있다. 이때, 32비트 기준으로 처음 표현했던 수와 그 2의 보수의 서로 다른 비트 수를 출력하기 문제 : 링크 필요 알고리즘 비트의 합 연산 두 비트 a, b가 있을 때 비트의 합 연산은 다음과 같다. carry_out은 자리 올림이고, sum은 해당 자리에 남는 수이다. carry_out : a and b sum : a xor b 풀이 bits_a = [True if bit == '1' else False for bit in bin(int(input()))[2:].rjust(32, '0')] bits_b = [not bit for bit i..