기타/알고리즘
-
[파이썬] 다이나믹 프로그래밍 기초기타/알고리즘 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. ..
-
[파이썬] 그래프, 그래프 탐색(BFS,DFS) 알고리즘의 기초기타/알고리즘 2020. 12. 18. 22:04
정점(node)과 간선(edge)으로 각 정점들의 관계를 나타낸 것을 그래프라고 한다. 만약 위와 같이 그래프가 주어진다면, 1은 2, 3, 4 와 연결되어 있고, 2는 5와 연결되어 있고, 3도 5와, 5는 6, 7과, 7은 3과 연결되어 있음을 확인할 수 있다. 파이썬에서는 그래프를 딕셔너리를 이용하여 나타낸다. 그래프의 키는 정점을, 값은 키와 연결된 정점을 나타낸다. 따라서 아래와 같이 나타낼 수 있다. graph = {1 : [2,3,4], 2 : [5], 3 : [5], 4 : [], 5 : [6, 7], 6 : [], 7 : [3]} 알고리즘 문제를 풀 때는 주로 두 정점의 연결관계를 여러줄에 걸쳐 입력받는다. 위 문제라면 1 2 1 3 1 4 ... 와 같은 식으로 입력을 받는다. 입력받은..
-
백준 파이썬 11501 : 주식 풀이 (시간초과 해결)기타/알고리즘 2020. 12. 16. 23:08
https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 미래의 가격을 알고 있고, 매일 한 주를 사거나 팔 수 있고, 아무것도 하지 않을 수 있다. 이때의 최대 이익을 구해야 한다. 주식은 싸게 사서 그보다 비싸게 팔면 되는 '매우 간단한' 게임이므로 1. 현재 가격이 미래 가격보다 싸면 사고 2. 미래 가격보다 비싸면 아무것도 하지 않고 3. 지금 가격이 최대 가격이면 팔면 된다 따라서 1. 현재 이후의 가격의 최대값을 구하고 2. 현재..
-
[파이썬] 리트코드 739. Daily Temperatures 풀이기타/알고리즘 2020. 12. 16. 19:09
https://leetcode.com/problems/daily-temperatures/ Daily Temperatures - 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 매일의 온도를 리스트 T로 입력받은 뒤 현재보다 더 따뜻한 날이 올 때까지 며칠이 걸리는지를 구하는 문제다 1. enumerate를 이용해서 특정 날짜의 인덱스와 온도값을 기억한다 2. T의 인덱스를 계속해서 스택에 쌓아두면서 1. 현재 온도가 스택에 쌓아둔 마지막 날의 온도보다 높다면 2...