분류 전체보기 (19) 썸네일형 리스트형 [ 백준 1520번 내리막 길 ] Python 코드 (메모이제이션 a.k.a. DP) 1. 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 2. 리뷰 어떻게 DP문제는 풀 때마다 새롭다. 이것도 DP로 풀 수 있다고?라는 충격의 연속이다. 특히 이 문제는 Top-Down 방식의 메모이제이션만이 DP에 비해 차별화된 강점을 보여주었다. 지금까지 푼 문제들은 DP와 메모이제이션이 상호변환이 가능했는데, 이 문제는 DP로는 풀기 어려웠다. (솔직히 불가능하다고 생각하지만 혹시 모르니까....ㅎㅎㅎ) 문제를 보면 가장 먼저 DF.. [LeetCode 433. Minimum Genetic Mutation] Python 코드 (Bactracking, BFS) 1. 문제 https://leetcode.com/problems/minimum-genetic-mutation/ Minimum Genetic Mutation - 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 2. 리뷰 아주 재밌는 문제다. 처음에는 백트래킹으로 풀었고, 최적화를 통해 꽤 괜찮은 결과를 냈다. 그런데 문제가 요구하는 바를 잘 살펴보면, BFS가 더 적합하고 효율적임을 알 수 있었다. 백트래킹, BFS, DFS 등은 모두 완전탐색 기반의 알고리즘이다... [ 백준 17144번 미세먼지 안녕! ] Python 코드 (Simulation) 1. 문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 2. 풀이 문제가 어려운 것은 아니었지만 Python3로 돌리면 시간초과가 발생했다. PyPy3로는 통과되었지만 뭔가 만족스럽지 않아서 Python3로 통과될 때까지 코드를 최적화했다. 그래서 어떻게 겨우겨우 Python3로도 통과를 했다!! 상위코드를 몇 개를 살펴 보았는데, 내가 제출한 코드와 비슷한데도 2배 정도 시간차이가 났다. 어째서인지 잘 모르겠다. 내가 적용한 최적화 방법.. [ 백준 1726번 로봇 ] Python 코드 (BFS) 1. 문제 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 2. BFS 풀이 (3차원 visited 배열) 나는 처음에 다른 방식으로 풀었다. BFS에서 visited배열의 활용 방식을 살짝 변경해서 최단거리를 찾는 알고리즘으로 사용했는데 혼자 풀고 뿌듯함에 차있을 때, 다른 분들의 3차원 visited 배열을 보고 무릎을 탁 쳤다. 메모리 사용량과 처리시간도 더 적었을 뿐더러, 무엇보다 기본적인 BFS 알고리즘 동작방식을 그대로 따랐다. 3차원 visi.. [ 백준 11265번 끝나지 않는 파티 ] Python 코드 (다익스트라, 벨만포드) 1. 문제 https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net 2. 풀이 2.1. Bellman-Ford 입력이 2차원 배열인데다가, 출발지도 여러개여서 Bellman-Ford 알고리즘을 쓰고 싶은 충동에 휩싸인다. 실제로 Bellman-Ford를 써서 풀 수 있기는 하다! 그런데 파이썬의 비애로 자잘한 최적화를 해줘야 한다. 관련 내용은 이 블로그를 참조했다. 아주 자세하고 친절하게 써주셨다. 무조건 min으로.. [ 백준 1922번 네트워크 연결 ] Python 코드 (MST) 1. 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 2. 풀이 물구나무 서서 봐도 MST(최소 스패닝 트리) 문제이다. 특별하게 꼰 부분도 없어서 MST 알고리즘 연습하기 딱 좋다. 대표적인 MST 알고리즘으로는 Prim과 Kruskal이 있다. 주어진 그래프의 노드가 V개, 간선이 E개라고할 때 시간복잡도는 다음과 같다. 알고리즘의 반복문 부분을 보면 어렵지 않게 확인할 수 있다. Prim Prim with heap Kruskal 시간복잡도 O(V**2) O(E*logV) O(E*logV) 특징 자료구조 heap을 사용해야 .. Ch 06. 관계 데이터 연산 김연희, 『데이터베이스 개론』, 한빛아카데미(2022.07.20), Chpater 04 Ch6. 관계 데이터 연산 관계 데이터 연산을 일반 집합 연산자와 순수 관계 연산자로 나누어 학습한다. 6.1. 관계 데이터 연산의 개념 관계 데이터 연산 관계 데이터 모델에서 원하는 데이터를 추출하기 위해 릴레이션에 처리를 요구하는 것으로, 관계 대수와 관계 해석으로 나눌 수 있다. 관계 대수(relational algebra)는 데이터의 처리 과정을 순서대로 기술하는 절차 언어이고, 관계해석(relational calculus)는 원하는 데이터가 무엇인지만 기술하는 비절차적 언어이다. 이 둘은 개념적 언어로 실제 사용되지는 않는다. 하지만 데이터 언어의 유용성을 검증하는 도구로써 쓰인다. 6.2. 관계 대수 6.2.. [ 백준 21610번 마법사 상어와 비바라기 ] Python 코드 (Simulation) 1. 문제 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 2. 아이디어 코드 짜기가 어려운 문제는 아닌데, 시간초과가 나버렸다. 두손 모아 기도하며 PyPy로도 돌려보았지만 여전히 시간초과였다. 주저리주저리 설명할 것 없이, 내가 개선한 방법만 말하면 다음 3가지다. 리스트 복사는 하지 않는다. 시간복잡도 O(n) 리스트의 모든 요소를 복사해야하기 때문에 시간복잡도가 O(n)이다. 가능하면 리스트 대신 집합에서 in 구문을 쓰자. 시간.. [ 백준 2156번 포도주 시식 ] Python 코드 (DP) 1. 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2. 아이디어 다이나믹 프로그래밍의 핵심은 DP배열이 가지는 의미 & DP배열을 계산하는 방법이다. 2.1. DP배열이 가지는 의미 지금까지 풀어본 문제들을 보면, DP[n]은 대부분 다음 두 가지 중 하나의 의미를 가졌다. n번째를 선택했을 때의 최적값 n번째까지 고려했을 때의 최적값 (n번째를 선택하지 않는 경우까지 고려) 이 문제는 두번째 경우에 해당한다. 왜냐하면 최댓값을 만드는데.. [ 백준 9465번 스티커 ] Python 코드 (DP) 1. 문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 2. 아이디어 다이나믹 프로그래밍의 핵심은 DP배열이 가지는 의미 & DP배열을 계산하는 방법이다. 2.1. DP배열이 가지는 의미 지금까지 풀어본 문제들을 보면, DP[n]은 대부분 다음 두 가지 중 하나의 의미를 가졌다. n번째를 선택했을 때의 최적값 n번째까지 고려했을 때의 최적값 (n번째를 선택하지 않는 경우까지 고려) 이 문제는 첫번째 경우에 해당한다. 왜냐하면 총 .. 이전 1 2 다음
