알고리즘/백준 알고리즘 강의 (40) 썸네일형 리스트형 백준 알고리즘 기초 - 다이나믹 프로그래밍 (예제1) DP는 정말 문제 푸는 감각이 중요한듯. 알면 너무 쉽고, 모르면 진짜 어렵다. 많이 풀어보자. 예제 푼 것들 정리! - * 카드 구매하기 (mid): 주어진 카드를 최댓값으로 구매하는 경우를 구하는 문제다. 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include using namespace std; int p[10001]; int d[1001]; int main().. 백준 알고리즘 기초 - 다이나믹 프로그래밍 1 + 기초 예제 풀 수 있을 것 같지만, 못 풀 것 같기도 한 알고리즘.. dp.. 그만큼 제대로 된 이해를 못 하고 있다는 거겠지..? 이번 기회에 확실하게 짚고 넘어가자. 다이나믹 프로그래밍 정리 시작! - * 다이나믹 프로그래밍 (DP): 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 (큰 문제를 작은 문제로 나눠서 푸는 알고리즘은 2가지가 있는데 하나가 DP, 하나는 분할 정복 알고리즘(D&C)이다. DP는 나눈 문제들이 중복이 가능하지만, D&C는 중복이 될 수 없다는 차이가 있다.) - 두 가지 속성을 만족해야 DP를 사용할 수 있다. 1. Overlapping Subproblem : 큰 문제와 작은 문제를 같은 방법으로 풀 수 있어야 하고, 문제를 작은 문제로 쪼갤 수 있어야 한다. 2. Optimal Sub.. 백준 알고리즘 기초 - 수학1 (연습) 수학 1 연습 해보자 - - GCD 합 (low): 이중 for 문으로 묶어서 더하면 되는 간단한 문제였다. 9613번: GCD 합 문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 �� www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include using namespace std; int gcd(int x, int y) { while (y != 0) { int r = x%y; .. 백준 알고리즘 기초 - 수학1 굉장히 유용한 챕터였다. 예전부터 관련된 문제를 해결하는 것은 어렵지 않았는데, 세련되지 않게 푸는 느낌이 들 때가 많았다. 다른 방법이 있을 것만 같은 느낌이 강하게 들었는데, 이번 챕터로 그 찝찝함을 해결한 느낌이 들어서 기분이 좋다. 아리까리 할 때 자주 찾을 것만 같은, 수학1 정리 시작! - * 나머지 연산: 답이 엄청 커질 때, 어떤 수로 나눈 나머지를 답으로 요구하는 경우가 있다. 결과값의 나머지를 바로 구할 수도 있지만 그게 너무 커져버리면 오버플로우가 나서 계산을 못 하는 경우도 생긴다. 그런 일이 안 생기게 계산 과정에서 나머지 연산을 해주는 방법이 있다. - (a+b) mod M = ( (a mod M) + (b mod M) ) mod M - (a*b) mod M = ( (a mod .. 백준 알고리즘 기초 - 자료구조1 (연습) 문제 풀이 강의라서 강의를 듣기 전에 먼저 문제를 풀었다. 어떻게 풀었냐에 따라 3가지 기준으로 표시를 남겨서, 나중에 복습할 때 활용하고자 한다. low: 솔루션이 떠올라서 답을 풀었다. mid: 솔루션이 떠오르지 않아 강의를 참고해 답을 풀었다. high: 솔루션이 떠오르지 않아 강의를 봤는데도 아리까리 해서 정답 코드를 참조했다. + 그리고 스스로에게 다시 한번 당부. 방법론은 이해 했으나 사소한 실수로 인한 런타임 에러 등으로 시간 낭비를 할 필요는 굳이 없는 것 같다. 차근차근 체크를 해도 도저히 영문을 모르겠다 싶으면 그냥 정답 코드를 참고하고, 다시 풀어보도록 하자. 연습문제 정리 시작! - * 단어 뒤집기2 (low): 단어 뒤집기 업그레이드 버전. 괄호 안의 단어는 안 뒤집는 조건이 추가.. 백준 알고리즘 기초 - 자료구조1 (큐, 덱) 금방 끝낼 수 있을 거라고 생각했는데, 생각보다 소요되는 시간이 꽤 된다.. 자꾸 문제를 풀다가 어떤 덫에 걸리면 그걸 내 힘으로 풀어보겠다고 미련하게 시간을 날린다. 어느 정도의 시간을 보내면 덫에서 빠져나와 정신을 차리는 지혜도 좀 발휘하자 미련한 놈아 큐, 덱 정리다. - * 큐: 한쪽 끝에서만 넣고, 다른 한쪽 끝에서만 뺄 수 있는 자료 구조다. FIFO. 먼저 온 놈이 먼저 나간다. 주로 BFS에서 많이 사용된다. 스택처럼 일차원 배열 하나로 구현이 가능하고, STL이 있지만 일단 한번 구현해본다. 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보.. 백준 알고리즘 기초 - 자료구조1 (스택) 바로 이전 글에서.. 미련함에서 벗어나자고 했건만.. 아직 한참 멀었다.. 오답 수집가냐 진짜 떠오르는대로 꾸역꾸역 코딩을 하다보니 이런 일이 벌어졌다. 구조를 구상하고, 정리가 됐을 때 코딩을 시작해라 좀. 저렇게 시간 낭비하는 건 너무 아깝다.. 됐고 스택 공부한 거나 정리 해보자. - * 스택: 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조. 제일 위(top)에 뭐가 있는지가 관심사다. - top에 추가하는 것을 push, top에서 빼는 것을 pop이라고 한다. - LIFO (Last In First Out) 구조다. 제일 마지막에 들어온 사람이 제일 먼저 나가야 된다. (짬 대우) * 스택 구현: 일단 STL 없이 한번 구현 해봤다. 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 .. 백준 알고리즘 기초 - 알고리즘 시작 돈을 주고 산 강의라.. 그대로 옮겨 올 수는 없을 것 같고.. 딱 나한테 필요한 부분만 정리를 해보려고 한다. 누군가 읽을 일이 있을지 모르겠지만 애초에 소개 목적이 아님을 알려둔다.. - * 알고리즘: 어떤 문제를 해결하기 위해 정해진 일련의 절차나 방식을 공식화한 형태로 표현한 것. * 알고리즘 문제 풀이, 고민의 시간: 한 문제를 붙들고 며칠을 고민하기도 했는데, (이제 그런 미련한 짓은 그만) 2~3시간정도만 고민하고 안 되면 바로 정답을 보면서 원리를 이해한 뒤에 다른 문제를 더 푸는 것이 효율적일듯. * 시간 복잡도: 코드를 작성했을 때 시간이 얼마나 걸릴지 예측해보는 것. 최악의 경우에 얼마나 걸릴지를 구한다고 생각하면 된다. 소스 코드를 보고 계산할 수도 있고, 작성하기 전에 먼저 계산 .. 이전 1 2 3 4 5 다음
