남남이루의 고군분투 🌳

import sys sys.stdin = open('graph input.txt', 'rt') input = sys.stdin.readline size = int(input()) graph = [list(map(int, input().rstrip())) for _ in range(size)] print(graph) apt = [] dx = [1,-1,0,0] dy = [0,0,1,-1] def DFS(x,y): global cnt if 0 탐색 시간복잡도 단지수(V) : N**2 연결(E) : 4*N**2 O(V+E) : 5N**2 => N*2 => 25\*2 => 625 : 2억보다 작음 자료구조 리스트? visited => graph 문제 접근하는 루틴을 연습해봤다. 추가..

문제 양방향 그래프의 연결 요소를 구하는 문제로, DFS의 대표적인 유형의 문제 중 하나이다. 풀이 DFS는 소스코드 프레임에 아래와 같은 것들이 자주 쓰인다. visted = [False]*(n), count = 0, graph = [[] for _ in range(n)] 첫 번째 visited는 노드를 방문했는지 확인하기 위함이고, 두 번째는 문제에서 요구하는 것을 count, 마지막은 graph이다. 그래프의 특성에, 방향이 없다고 했기 때문에, 그래프 생성할 때 인덱스와 값을 switch해서 두번 씩 적어줘야 한다. for i in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u) DFS를 최초로 호출하..

문제 풀이 프로세스 (오답) 1. 문제의 주요 변수들 명시 2. DP의 빈배열이 있다고 가정하고, 문제의 조건에 맞는 답을 나열해보기 3. 나열한 것들 중에서 규칙찾기 # n 개의 물건, 최대 100개 # k 가용 무게 # w 무게와 v 가치 더보기 y = 무게 d[x][y] = 가치 총합? d[x][0] = 0 d[x][1] = 0 d[x][2] = 0 d[x][3] = 6 d[x][4] = 8 => max(d[x][3], d[x][4]) d[x][5] = 12 => max(d[x][4], d[x][5]) d[x][6] = 13 => max(d[x][5], d[x][6]) d[x][7] = 14 => max(d[x][6], d[x][3]+d[x][4]) # 이중 포문으로 탐색할 부분 d[무게] = 가치..

이항계수를 구하는 문제 n과 k 가 주어질 때, 두 수에 해당하는 이항계수를 구하는 것이 문제이다. 관건은 이항계수의 개념을 알고, 이를 코드로 구현하는 것이다. (단, 수의 범위가 1,000으로 그렇게 크지 않기 때문에 전체 숫자를 구한 다음에 접근하는 방법도 가능하다.) 이항계수 이해하기 조합론에서, 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다. 위의 이항계수 주요성질을 참고해, 코드를 구현할 수 있다. 정의식 (n)! / (n-k)!(k)! 을 이용하거나, 1 또는 2를 이용해 재귀함수나 dp를 사용한 코드를 볼 수 있다. (맨 밑 참고 블로그 확인) 아래의 코드는 botto..

주어진 동전들로 k원 금액을 만들어라! 틀린 이유 1. for 문 구현에서 index랑 범위 설정이 이해가 잘 안 갔었다.

와 미챠따.. 첨으로 답안보고 풀었다 관건은, d[x]가 최대금액을 보장하는 놈이 들어있고, 카드팩을 돌면서 비교하면 됨. 규칙을 찾기 위해 적어보자면, p[x] = y x 카드 갯수 y 금액 d[1] = p[1] d[2] = max(p[1], p[2]) d[3] = max(p[1]+p[2], ) d[4] = max(d[3]+p[1], d[2]+p[2]) d[5] = max(d[4]+p[1], d[3]+p[2]) max안에 들어갈 내용들만 봤을 때, d와 p의 인덱스들의 합이 d의 인덱스임을 알 수 있었음 import sys input = sys.stdin.readline n = int(input()) d = [0] * 1001 p = [0] +list(map(int, input().split())) f..

바텀업으로 배열을 채우고, 인덱스 n에 해당하는 값을 출력하는 식으로 품 d의 기본 배열을 각 인덱스로 채우는 게 다른 DP문제랑 다른 점이었고, ( 1**2로만 더한 횟수가 최대이므로, 3 = 1**2 + 1**2 + 1**2 , 3에 대해 최대 횟수가 3임 ) 이중 반복문, 제곱근까지는 생각했는데, 이걸 식으로 구현하는 게 어려웠다. 뺄셈으로 해결하신 분의 코드를 참고했다. 11을 예시로 원리를 설명해보자면, 11은 제곱의 항들로 표현되는 가짓수들의 일부는 이렇다. 11 = 1**2 + 1**2 + ... 11 = 2**2 + 2**2 + 1**1 + 1**1 + 1** 1 11 = 3**2 + 1**2 + 1**2 (최소 횟수) 어떤 자연수 N에 대해, N=1부터 시작하면서 N보다 작은 제곱수를 가..

풀이 과정 1. 점화식으로 표현해보기 2. 작은 수부터 일일이 계산해 규칙 찾아내기 3. 바텀업으로 풀어보기 >>> 런타임 에러 4. 생략된 규칙 추가하기 (%15746) >>> 메모리 초과 5. %15746의 위치를 출력 구문이 아닌, 입력 부분으로 옮김 >>> 런타임 에러 ------ 계속해서 index 에러가 나고 있었다. 다른 분들의 코드를 참고한 결과, 가장 큰 차이점은 빈 배열을 만드는 부분이었따. 나는 d = [0] * (n+1)로 했는데, 다른 사람들은 아예 배열의 길이를 N의 최대값인 1000000+1로 고정해뒀더라. 그걸 수정하니, 정답처리 되었다. 아직 왜 그런지는 모르겠다. import sys input = sys.stdin.readline n = int(input()) d = [0..

문제 요구사항 정수 X를 1로 만들기 위한 연산이 3가지가 있다. 이를 적절히 사용하여 1로 만들고자 할 때, 최소한의 연산 횟수를 구하라 주의사항과 DP의 특징 어떤 N에 대해 나올 수 있는 모든 연산의 횟수를 구하면, 이 문제는 시간초과가 뜬다. N보다 작거나 N을 2나 3으로 나눴을 때의 small N들이 최소한의 연산횟수로 도출된 것을 이용해 N의 최소연산횟수를 구하게 되면, 훨씬 시간자원을 아낄 수 있다. small N들은 문제에서 제시한 연산 방법에 따라 2나 3을 나눈 수, -1을 한 수들이다. 예를 들어 6의 최소연산횟수를 구하고자 할 때, N = 6이고, small N들은 2,3,5가 된다. 2,3,5를 만들 때 사용했던 연산에 각각 *3, *2, +1을 하게 되면 6을 만들 수 있으므로..

DP란, 피보나치처럼 작은 문제로 분할하여 현재의 값을 구하는 문제에 대해 메모리 공간을 활용함으로써 속도를 비약적으로 줄이는 기법이다. 점화식으로 표현되는 문제들을 DP기법을 활용할 경우 효율적으로 답을 구할 수 있다. 점화식이란, 인접한 항들 사이의 관계식을 의미한다. 예를 들어 수열에서의 각 항을 An이라고 부를때, 우리는 점화식을 이용해 현재의 항을 이전항에 대한 식으로 표현할 수 있다. DP로 해결할 수 있는 가장 대표적인 유형인 피보나치의 점화식은 A(n+2) = A(n+1) + An 으로 표현할 수 있다. 프로그래밍과 점화식 n번째 피보나치수를 f(n)이라고 표현할 때, f(4)를 구하고자 할 때 f(2)와 f(1)은 항상 1이므로 이때는 호출을 정지하는 코드를 넣어 재귀함수로 풀 수 있다...