algorithm

Divide and conquer

어떤 문제가 divide and conquer로 표현 가능하다고 하자. 그렇다면 이 문제는 여러개의 원자적인 sub-problem들의 집합이다. 그리고 이 집합에 대해 아래의 조건이 성립한다고 가정하자.atomic한 sub-problems들 중 중복 되는 것들이 있다.

모든 경우의 수를 전부 고려한다. 탐색할 필요가 없는 상태(부분적인 조합)를 가지치기(pruning)한다.combinatorial search와 연관이 있다. DFS로 탐색탐색 도중 제대로 작동하지 않는 판단이 내려지면새로운 탐색이 가능한 choice point로 ba

위키피디아에서 이야기 하는 알고리즘의 정의는 아래와 같다. a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a com

복기x,y를 바꿔 썼다.outOfBound를 먼저 체크해야 오버플로우가 발생하지 않는다. 문제유형

문제링크 : https://www.acmicpc.net/problem/19942복기다른 방법으로 풀어 보려고 했는데 점점 이상해졌다. 비트마스킹 기준, 정수 5가 정수 11보다 사전 정렬 시 더 뒤에 와야 한다. 이걸 못 깨달았다. 문제유형 : 조합 찾기

문제링크 : https://www.acmicpc.net/problem/9935 복기 스택을 쓸 생각을 하지 못 했다. 마구잡이로 구현해서 메모리 초과 발생 문제유형 : 자료구조(스택) 자료 구조 : 스택 문자열 처음 접근한 방법은 아래와 같다. 단순

문제유형:복기

그리디 최초 풀이 당시 order by day, price로 정렬 후 각 day 마다 최대값을 뽑아냄. 하지만 day가 같더라도, 최대 price를 가지는 값들을 골라야 했음(반례 생각 x).fail priority queue를 사용해서 풀 수 있다. 각 day마다,