Joon's Space

문제풀이 그래프 문제는 먼저, 노드와, 간선의 정보를 모두 저장해준다. 이 문제 해결법은 그래프의 1 컴퓨터 노드에서 탐색을 시작했을 때, 1을 제외한 방문했던 노드수를 count 해준다. 노드 간의 탐색은 dfs, bfs 둘 중 dfs를 사용하였다. 소스코드 import sys input = sys.stdin.readline T = int(input()) L = int(input()) road = [[0] * (T+1) for i in range(T)] visited = [0 for i in range(T)] for i in range(L): a,b = map(int, input().split()) #연결할 노드 2개를 입력 road[a-1][b-1]=1 #양방향 으로 모두 갈수 있기 때문에 양방향 둘..

문제풀이 이번 문제도 dp를 이용하면 쉽게 풀린다. dp문제는 규칙을 찾고, 점화식을 먼저 구해준다. n 0 1 2 3 4 5 dp[n] 0 0 1 1 dp[2]+1 dp[4]+1 n>=2 부터 2,3으로 나누었을 때, 나누어지는지에 대한 여부를 살펴보고, 조건문을 이용해서 dp값을 추가해준다. dp[n] 의 값은 i) 2,3으로 모두 나누어질때는, dp[n//2], dp[n//3], dp[n-1] 에서 가장 작은 값 + 1 ii) 2로 나누어 떨어지고 3으로 나누어 떨어지지 않을 때, dp[n//2], dp[n-1] 에서 더 작은 값 +1 iii) 2로 나누어 떨어지지 않고, 3으로 나누어 떨어질 때, dp[n//3], dp[n-1] 에서 더 작은 값 +1 iv) 2,3 모두 나누어 떨어지지 않을 때,..

문제풀이 이 문제는 dp를 이용하면 쉽게 풀린다. 먼저 규칙을 찾아보자. DP 0 1 2 3 4 5 0 1 0 1 1 2 3 1 0 1 1 2 3 5 DP 점화식을 세우면, dp[n] = [dp[n-1][0]+dp[n-2][0], dp[n-1][1]+dp[n-2][1]] 이다. import sys input = sys.stdin.readline T = int(input()) dp = [[1,0],[0,1]] for i in range(2,41): dp.append([dp[i-1][0]+dp[i-2][0],dp[i-1][1]+dp[i-2][1]]) for i in range(T): n = int(input()) print(dp[n][0],dp[n][1]) www.acmicpc.net/problem/1003..

문제풀이 랜선의 길이를 K개에서 N개 이상으로 만들 수 있는 가장 큰 랜선의 길이를 구해야 한다. 길이를 1씩 늘리거나 줄이는 완전 탐색 방법은 시간적으로 비효율적일 수 있다. 이를 보완한 알고리즘이 '이분 탐색(Binary Search)' 알고리즘이다. 정렬된 값이 나열되었을 때, 특정 값을 O(logN)의 시간 복잡도를 갖고 찾을 수 있다는 장점이 있다. 먼저 코드를 작성하기 전 이분탐색을 이용하여 어떻게 구현할지 생각해보자. 기준이 되는 이분탐색 코드는 다음과 같다. def bi_search(target, A): start = 0 end = len(A)-1 while start

문제풀이 이 문제는 N개만큼 입력받은 수의 산술평균, 중앙값, 최빈값, 범위를 출력하는 구현 문제이다. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 다음과 같이 구현하면 되겠다. 중앙값, 범위를 구할 때 쉽게 접근하기 위해서 먼저 입력받은 값들의 리스트를 생성한 뒤, sorted 함수로 정렬해준다. 산술평균 -> sum 함수를 이용해서 리스트 길이만큼 나누어주고 round 함수로 반올림해준다. 중앙값 -> N의 갯수는 홀수이기 때문에 길이의 2로 나눈 값이 중앙값이 되겠다.최빈값 -> '수정렬하기3' 문제에서 배웠던 계수 정렬..

문제풀이 DP(Dynamic Programming) 문제이다. DP는 큰 문제를 해결하기 어려울 때 앞의 작은 경우를 나누어서 해결하는 기법이다. 문제를 해결하다보면 작은 문제와 겹치는 부분을 다시 계산하지 않고 저장했다가 재사용하면 큰 문제를 해결할 때 훨씬 더 효율적으로 계산할 수 있다. 설탕 배달과 같은 문제는 먼저 작은 문제들의 경우를 DP 리스트로 저장하여 준다. 3kg, 5kg 일경우 각각 1이며 0~2,4의 경우는 0가지이다. DP 리스트로 저장하였을 때, 다음과 같이 저장한다. DP = [0,0,0,1,0,1] 이제 더 큰 경우를 구하려면 DP 점화식을 세워야 한다. 1 2 3 4 5 6 7 8 9 10 3 0 0 1 0 0 2 0 1 3 0 5 0 0 0 0 1 0 0 1 0 2 총 0 ..

문제풀이 ① 좌표를 y좌표가 증가하는 순으로, ② y좌표가 같으면 x좌표가 증가하는 순서로 정렬 정렬하는 기준이 2가지인 정렬이다. 이와 같은 경우에는 key= 파라미터를 이용한다. key 파라미터는 함수를 받는 파라미터이기에 람다식을 이용할 수 있다. 이 문제에서는 y좌표가 큰 값부터 정렬하고 같다면 x좌표가 큰 순으로 정렬해야 한다. 이와 같이 2가지 정렬 조건이라면 우선순위순으로 기준을 왼쪽부터 나열해준다. key 함수의 리턴 값이 (첫번째 기준, 두 번째 기준) 형식의 튜플이 오면 된다. ex) sorted(list, key=lambda x:(x[1], x[0]) # x[0]=x 좌표, x[1]=y좌표이기 때문 소스코드 import sys input = sys.stdin.readline N = i..

문제풀이 이전에 풀었던 수 정렬하기 1,2번 문제와 동일하게 단순히 수를 입력받아 오름차순으로 정렬하는 문제이다. 하지만, 이 문제는 1,2번 문제와 달리 메모리 제한이 훨씬 적다. -> 단순히 리스트에 추가시켜 sorted 함수를 이용해서 정렬할 경우, 시간 초과가 아닌 메모리 초과라는 결과가 나온다... 숫자의 개수가 1부터 10,000,000까지인 걸 보면 왜 그런지 알 수 있었다. 그렇게 구글링을 하던 중, 리스트의 길이를 고정시키면 메모리 초과 오류가 나오지 않는다는 방법을 찾았다. 이 방법은 직접 리스트에 숫자를 정렬시키는 것이 아니라. 숫자를 입력받을 때마다, 그 숫자에 해당하는 인덱스 위치에 값을 1씩 더해준다. 아래 블로그 글을 참조하였다. Counting Sort : 계수 정렬 Coun..