전체 글
-
[파이썬] 리트코드 39. Combination Sum 풀이기타/알고리즘 2020. 12. 24. 22:53
Combination Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com candidates = [2,3,6,7] 와 같은 식으로 주어졌을 때, candidates안의 요소들을 더하여 target = 7을 만들 수 있는 배열을 출력하는 문제다. 그래프를 탐색하며 각각의 값들을 더해가다가 합한 값이 target이 되었을 때, 여태까지의 경로를 출력하면 되는 것이다. 1. dfs의 변수로 csum(target까지 남은 수), index, path를 이용한다 2..
-
[파이썬] 리트코드 53. Maximum Subarray 풀이기타/알고리즘 2020. 12. 24. 22:46
Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com nums이 주어졌을 때, 연속된 배열의 합이 가장 큰 경우의 합을 출력하는 문제다. 각각의 배열에 대해 모든 합을 계산하는 브루트 포스 방식으로는 풀 수 없다. 조금 더 효율적인 다이나믹 프로그래밍을 이용해야 한다. nums = [-2,1,-3,4,-1,2,1,-5,4]으로 주어진다면 포인터를 이동시키면서 배열의 합이나 포인터가 가르키는 숫자 중 큰 것을 cur_mx에 저장해주고 c..
-
[파이썬] 리트코드 78. Subsets 풀이기타/알고리즘 2020. 12. 24. 22:09
Subsets - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com nums = [1,2,3]일 때 부분집합의 개수를 구하는 문제다. 탐색 알고리즘을 실행했을 때, 모든 탐색의 결과가 정답이 된다. 따라서 dfs로 간단하게 풀 수 있다. 1. 인덱스와 경로를 변수로 가지는 dfs를 정의하고 2. 지나온 경로를 결과값에 저장하면서 3. 모든 경로에 대해 탐색을 실행한다 class Solution: def subsets(self, nums: List[int]) -> L..
-
[파이썬] 다이나믹 프로그래밍 기초기타/알고리즘 2020. 12. 23. 23:08
1. 다이나믹 프로그래밍이란 다이나믹 프로그래밍은 1. 작은 문제의 답을 이용해서 큰 문제의 답을 계산하고 2. 각각의 계산결과를 기억하는 방법이다. 2. 조건 다이나믹 프로그래밍을 이용하기 위해서는 두 조건을 만족해야 한다. 1. 최적부분구조 큰 문제의 정답을 작은 문제에서 찾을 수 있어야 한다. A라는 문제를 B와 C로 나누었다면 B의 결과와 C의 결과를 더한 값은 A와 같아야 한다. 그렇지 않으면 작은 문제로 나누어서 푸는 것이 틀린 접근이 된다. 2. 중복된 하위 문제 작은 문제들이 반복되서 이용되어야 한다. 작은 문제의 결과를 저장해서 재활용하기 때문에, 그 결과가 여러번 이용되어야 다이나믹 프로그래밍을 하는 의미가 있는 것이다. 3. 방법, 재귀와의 비교 피보나치의 수를 처음 배울 때는 무조건..
-
[파이썬] 리트코드 509. Fibonacci Number 풀이기타/알고리즘 2020. 12. 22. 11:27
https://leetcode.com/problems/fibonacci-number/ Fibonacci Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 다이나믹 프로그래밍에는 상향식 방법과 하향식 방법이 존재한다. 상향식 방법은 타뷸레이션이라는 것인데, 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나가는 방식이다. 작은 문제들의 계산을 다 해두고 결과값을 저장해뒀다가 필요한 결과값을 반환하는 식이다. range(2,n+1)의 모든 숫자에 대해 ..
-
백준 파이썬 18352 : 특정 거리의 도시 찾기 풀이기타/알고리즘 2020. 12. 22. 10:40
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net x에서 출발하여 최단 거리가 k인 도시를 모두 출력해야 한다 1. 그래프를 입력받는다. 일반적으로 탐색 문제에서는 '1 2'라는 입력이 들어오면 graph[1]에 2를 넣고, graph[2]에는 1을 넣어서 양방향으로 연결된 관계를 표현해준다 그러나 이 문제에서는 최단 거리를 구하기 때문에 양방향 관계가 필요가 없다. 왔던 ..
-
백준 파이썬 2667번 : 단지번호 붙이기 풀이기타/알고리즘 2020. 12. 19. 15:32
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 그래프 탐색 문제로, 동서남북으로 인접한 곳에 집이 있으면(= 1이라면) 집이 연결되어 있다고 하고, 연결된 집의 모임을 단지라고 한다. 여기서 단지의 개수, 각 단지내 집의 수를 출력해야 한다. 1. 어느 한 점에 대해서 인접한 곳에 1이 있는지를 탐색하고 2. 1이 있다면 그 점에서 다시 인접한 곳을 탐색하길 반복하고 3. 탐색을 할 때마다 카운트를 세다가 4. 탐색이 끝나면 카운트를 정답에 저..
-
백준 파이썬 2583번 : 영역 구하기 풀이기타/알고리즘 2020. 12. 18. 23:39
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 영역이 주어지고, 갈 수 없는 영역이 주어졌을 때, 갈 수 있는 영역의 개수를 구하는 문제다. 0,0에서 시작해서 BFS(너비 우선 탐색)을 동서남북 네 방향으로 실행하고, 한 칸 이동할 때마다 카운트를 더해주다가, 더 이상 갈 수 있는 영역이 없어졌을 때 카운트를 답에 저장해주면 된다. 1. 사각형의 세로 길이는 m, 가로 길이는 n, 갈 수 없는 영역의 개수는 k개다 2. ..