본문 바로가기

알고리즘124

합분해[백준 2225] - python 기본적인 다이나믹 프로그래밍이다. 배열을 그리고 초반 몇개를 직접 시도해보면 규칙이 보일거다 정답 코드 먼저 보자 n, k = map(int, input().split()) dp = [[0] * (k+1) for _ in range(n+1)] dp[0][0] = 1 for i in range(0, n+1) : for j in range(1, k+1) : dp[i][j] = dp[i-1][j] + dp[i][j-1] print(dp[n][k] % 1000000000) k = 1 인경우 모든 숫자는 1이다. k = 2 인경우 모든 숫자는 (n+1)을 가진다. n=2: (0,2)(1,1)(2,0) n=3: (0,3)(1,2)(2,1)(3,0) n=4: (0,4)(1,3)(2,2)(3,1)(4,0) k= 3 인.. 2021. 11. 30.
2로 몇 번 나누어질까[백준 1407] - python 이 문제는 크로아티에서 고등학생 대상으로 나온 문제다. 상당히 애를 먹었던 문제다.(아직 멀었나 보다) 코드 먼저 살펴보자 a,b = map(int, input().split()) def calc(number) : if number == 0 : return 0 elif number == 1 : return 1 elif number % 2 == 0 : return number // 2 + 2 * calc(number // 2) elif number % 2 == 1 : return number // 2 + 2 * calc(number // 2) + 1 print(calc(b) - calc(a-1)) 애를 먹었던 거에 비해서는 굉장히 간단하다. 규칙만 잘 찾으면 절대 어렵지 않은 문제다. 그 규칙에 대해서 아.. 2021. 11. 30.
플로이드 워셜 알고리즘 플로이드 워셜 알고리즘은 '모든 정점간에 최단거리를 구하는 알고리즘' 입니다. 시간 복잡도는 O(n^3)이다. 두개의 정점과 정점을 거치는 중간점 총 3개를 모두 탐색해야 합니다. 핵심은 거쳐가는 정점을 기준으로 최단거리를 알아내는 것입니다 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단거리를 구하는 문제 입니다. 다익스트라 알고리즘 플로이드 워셜 알고리즘 한 정점에서 다른 모든 정점으로의 최단 거리 구하는 알고리즘 모든 정점에서 모든 정점으로의 최단거리 구하는 문제 코드 먼저 살펴보겠습니다 v, e = map(int, input().split()) INF = 10000000 dist = [INF * (v+1) for _ in range(v+1)] # 입력받은 간선들에 대한 정보로 거리정보 .. 2021. 11. 28.
전구와 스위치[백준 2138] - python https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 1년 전에 풀때 못풀었던 문제다. 이번에 풀게되었는데 이번에도 실패다. (고마워요 다른 블로거 포스팅들) 다음엔 꼭 성공하리... 다음에 실패하지 않기 위해 이번에는 생각을 정리해서 글을 남겨둘 거다. 다음에 풀 나에게 힌트가 되기를 바라며... 정답 코드 먼저!!! n = input() first = list(input()) target = list(input()) .. 2021. 11. 21.
가장 긴 증가하는 부분 수열[백준 11053] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 스터디중 25분내에 풀지 못하고 곤혹에 빠졌던 문제이다. dp를 이용하여야 하는 문제이다. 정답 코드 먼저!!!! n = int(input()) l = list(map(int, input().split())) dp = [1] * (n + 1) for i in range(1, n) : for j in range(i) : .. 2021. 11. 20.
랜선 자르기[백준 1654] https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 우선 문제를 보고 바로 이분 탐색의 접근 방법이 떠올랐다는 것은 스스로에게 칭찬해주고 싶다. 최근에 이분 탐색 풀이에 크게 감명받고 한번쯤 이분 탐색을 꼭 곁들여 보는것 같다(혹시 이 접근은 아닐까 하는식??) 각설하고 애를 먹었던 부분은 길이가 최대로 긴 부분까지 접근해야 하는데 이부분을 어떻게 할것이냐?? 정답 코드 먼저!! k, n = map(int, input(.. 2021. 11. 20.

티스토리툴바