-같은 점- 작은 부분으로 문제를 나눈다. -다른 점- 다이나믹 알고리즘 : 각각의 작은 문제가 겹친다. memoization을 통해 이를 해결한다. 분할정복 알고리즘 : 문제가 겹치지 않는다. 따라서 다이나믹 알고리즘 문제의 경우 재귀함수를 쓰면 시간초과가 많이 나오지만, 분할정복 알고리즘은 재귀함수 사용에 비교적 자유롭다. -대표 문제 - 분할 정복 알고리즘 1780번 종이의 갯수 11729번 하노이탑

그리디 알고리즘 -결정해야 할때 그 순간 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘. -거스름돈 문제가 대표적인 문제지만, 모든 문제가 그런것은 아니다. -그리디 알고리즘은 증명이 어렵다 관련문제 : 11047번(동전 0) a[i]가 a[i-1]의 배수이므로 그리디 알고리즘을 사용하여도 문제가 없다. 다만 배수라는 조건이 없다면 다이나믹 프로그래밍을 통해서 해결하는 것이 옳다. cost[i]= cost[i-coint[k]]+1 1931번 (회의실 배정) 정렬하는 문제. 가장 빨리 끝나고 가장 빨리 시작하는 순서대로 정렬하면 편하다 11399번 (atm) 증명으로 가능 pf ) i번째 사람이 일을 보는데 시간을 p(i)라고 하면 i번째 사람이 기다려야 하는 시간은 시그마(1 각 자리수를 ..

알고리즘 강의를 듣다 보면 아무래도 기초 강의다 보니 학부 수업시간에 배운 내용이기도 하고, 혼자 알고리즘 문제를 풀면서 배운 것들이 많다. 그래도 처음 공부한다는 마음으로 공부하고 있는데 나름 정리가 되는 것 같아서 뿌듯하다. 오늘은 알고리즘 대회에서 꾸준히 출제되고 있는 다이나믹 프로그래밍이다. 다이내믹 프로그래밍이란? 큰 문제를 작은 문제로 푸는 알고리즘으로 다이내믹이라는 명칭은 알고리즘과 아무런 관련이 없다.(개발자가 그냥 멋있어 보여서.. 사용한 것이라고) 문제 해결 조건 큰 문제를 작은 문제로 쪼개서 풀 수 있고, 큰 문제를 작은문제와 같은 방법으로 풀 수 있으며, 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 사용 가능 한 방법이다. ex) 피보나치수, 조합 등등 문제 해결 방법 - ..

코드 플러스 백준알고리즘 강의 정리. 일+운동 다녀와서 엄청나게 피곤하지만.. 그래도 할 건 해야지...ㅠㅠ 오늘은 3강 큐와 queue란? 한 쪽 끝에서 자료를 넣고 다른 한쪽 끝에서 뺄 수 있는 구조. 터널이나 무빙워크 정도로 생각하면 편하겠다. 먼저 넣는 것이 가장 먼저 나오는 구조. queue는 c++에 STL에 있기 때문에 구현해서 쓰기보다는 가져다 쓰는 것이 편하다. c++의 경우 : queue java의 경우 : java.util.Queue queue의 STL APT push : 큐에 자료를 넣는 연산 . return 값이 없다 pop : 큐에서 자료를 빼는 연산. return 값이 없다 front : 큐의 가장 앞에 있는 자료를 보는 연산. 가장 앞에 있는 자료를 return한다. back..

코드 플러스 백준알고리즘 강의 정리. 1강부터 작성하려고 했지만 1강은 솔직히 그냥 몸풀기 같은 느낌이라 2강부터 정리해보려고 합니다. 스택에 대해 알아봅시다. stack이란? 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조. 마지막에 넣은 것이 가장 먼저 나오는 구조(한쪽이 막혀있는 원통 생각하면 편할 듯 프링글스 통) stack은 c++에 STL에 있기 때문에 구현해서 쓰기보다는 가져다 쓰는 것이 편하다. c++의 경우 : stack java의 경우 : java.util.Stack STL apt 정리 push : stack에 자료를 넣는 연산. return 값이 없다 pop : stack에서 자료를 빼는 연산(자료가 스택에서 삭제된다). return 값이 없다 top : stack의 가장 위에 잇는 ..

안녕하세요. 2년뒤 acm 학교 대표와 입상을 노리는 goodwoong입니다. 어느덧 백준온라인 저지는 250문제 넘게 풀었는데, 아는 건 없는 것 같고, 불안에 떨고 있는(..) 상황이었습니다. 종만북을 열심히 읽어봤지만 너무 어렵기도 하고 하루에 한 문제 푸는 것도 벅차더라구요. https://plzrun.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4PS-%EC%8B%9C%EC%9E%91%ED%95%98%EA%B8%B0 알고리즘 문제풀이(PS) 시작하기 이런건 고수들이나 써야 하지 않나 싶지만, 그래도 1년정도 공부하면서 이 분야를 어떻게 시작해야 할지 써보려 한다. 라고 운을 뗀다음..