땃쥐네

문제 플랫폼 : 백준 번호 : 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(..

문제 플랫폼 : 프로그래머스 번호 : 131128 제목 : 숫자 짝꿍 난이도 : Level 1 두 정수 X, Y가 주어졌을 때 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들(중복 허용)을 이용하여 만들 수 있는 가장 큰 정수 반환 문제 : 링크 필요 지식 파이썬의 경우 카운터를 잘 사용하면 정말 쉽게 풀 수 있는 문제다. 문자열 처리 Python : Counter 풀이 from collections import Counter def solution(x, y): c = Counter(str(x)) & Counter(str(y)) return '-1' if not c else '0' if len(c) == 1 and '0' in c else ''.join(sorted(c.elements(), reverse..

문제 상황 백준의 2775번 문제를 풀고 있었다. 이 문제의 상황은 a층 b호에 사는 사람은 a-1층 1호부터 b호까지 사는 사람의 합만큼 사람이 살아야하는 규칙에서 n층 k호에 사는 사람의 수를 순서대로 출력하는 문제였다. (단, 0층 b호에는 b명이 산다.) 문제를 해결하기 위해서는 나는 바텀업 방식의 DP 알고리즘을 사용하기로 했다. numbers = [[0] * 15] * 15 for r in range(15): for c in range(15): if r == 0 or c == 0: numbers[r][c] = c else: numbers[r][c] = numbers[r][c-1] + numbers[r-1][c] print(f'{r}층 {c}호에는 {numbers[r][c]}명이 살아요.\n')..

문제 플랫폼 : 프로그래머스 번호 : 042889 제목 : 실패율 (2019 KAKAO BLIND RECRUITMENT 출제) 난이도 : Level 1 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성 문제 : 링크 필요 지식 Counter 사용 정렬 풀이 from collections import Counter from typing import List def solution(n: int, stages: List[int]): results = [[i, 0, 0] for i in range(0, n + ..

문제 플랫폼 : 백준 번호 : 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..