전체 글110 2016 ACM-ICPC Asia Taiwan Online Programming Contest 창수랑 둘이서만 했는데, E번을 못 푼 걸 제외하면 썩 나쁘진 않은 듯.시간이 부족해서 G번과 I번은 문제도 못 읽었다.C번과 D번은 문제를 제대로 읽지 않아서 약간 시간이 소비되었다.한국 인터넷 예선과 비슷한 난이도이지만, 문제 수는 더 적은 세트라는 느낌이 들었다. 2017. 9. 16. AtCoder Regular Contest 074 C - Chocolate Bar간단한 수식으로 나올 것 같았는데, 예외적인 경우를 생각하기 귀찮아서 삼분검색 돌렸다.원래의 경우에서 상하좌우 바꾸고, 90도 돌리는 것만 고려해주면 되어서 실제 작성한 코드는 짧다.소스코드 D - 3N Numbers왼쪽에서부터 어느 곳까지 N개를 고르고, 그 이후 구간에는 N개를 고르는 것으로 볼 수 있다.따라서 전처리로 왼쪽에서 어디까지 N개를 골랐을 때의 최댓값, 오른쪽에서 어디까지 N개를 골랐을 때의 최솟값을 구해놓으면 답을 쉽게 계산할 수 있다.소스코드 E - RGB Sequence문제를 안 읽어봤다. F - Lotus Leaves플로우 네트워크를 만들고, 정점을 이분화 한다.시작점과 도착의 경우, 이분화한 정점 사이의 용량을 무한대로 준다.이 외의 정점들은 이분화.. 2017. 5. 21. 힙(Heap)을 이용한 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 방향이 있는 가중치 그래프에서의 단일 시작점 최단 경로 알고리즘이다. 단, 조건으로 모든 간선의 가중치가 음이 아닌 수여야 한다. 다익스트라 알고리즘은 해 집합(S)에서 해가 아닌 집합(T)로 향하는 경로 중, 가장 짧은 경로를 매번 선택한다. 아래 그림을 보자. 단일 시작점을 a라 하고, 위에서 말한 정의에 따라 표현했다.특정 시점에서의 가장 짧은 경로를 a→u-v라 하자. 즉, a에서 u까지 가는 경로에 간선 u-v를 추가하는 경로이다. 이 때, v가 S에 포함되는 경우가 2가지 경우가 있다. 1) a에서 S의 원소 u까지 가는 최단 경로에다가 u-v를 잇는 간선을 추가해서 v가 S의 원소가 되는 경우 2) a에서 T의 원소 u'까지 가는 최단 경로에다가 u-v를 잇는 간선을 추.. 2017. 2. 23. Shortest Path Faster Algorithm(SPFA) 방향성 가중치 그래프 G = (V, E)에서 단일 시작점 s가 있을 때, Shortest Path Faster Algorithm(SPFA)는 s에서 출발하여 다른 정점 v에 이르는 최단경로를 찾아낸다. Pseudo Code를 보면 다음과 같다. 초기에 다른 정점에 이르는 최단거리는 다 무한대로 설정하고 시작점에 이르는 최단거리는 0으로 정한다. Queue에 시작점을 넣고 Queue가 비어있지 않을 동안 반복한다. Queue의 맨 앞에서 원소 하나를 꺼내서 그 정점을 u라고 하자. u에서 뻗어나가는 간선들을 훑어보며, 간선이 가리키는 점 v의 최단거리를 갱신할 수 있으면 갱신해준다. 갱신하고 나서, Queue에 v가 없다면 Queue에 삽입한다. Queue에 어떤 정점 x가 있는지, 없는지의 여부는 정점 .. 2017. 2. 16. Parametric Search (파라메트릭 서치) 가능한 해 구간에 대해서 이분탐색을 하는 방법을 'Parametric Search'라고 한다. 흔히 가능한 해의 최솟값이나 최댓값을 구하라는 문제에서 사용할 수 있는 기법이다. Optimization Problem을 Binary Search + YES/NO Problem으로 바꾸어 푸는 방법이다. Parametric Search를 사용하기 위해서는 몇 가지 조건이 있다. 1. 가능한 해의 영역이 연속적이어야 한다. 예시로 가능한 해의 최솟값을 찾는 문제에서 설명하면 가능한 해 구간 [ L , R ]에서 우리가 정한 답 X를 기준으로 2가지 경우가 있다. 1) X가 해를 만족할 때, [ X , R ]에 대해서도 모두 해를 만족해야 한다. 따라서 X의 탐색 범위를 해 구간 [ L , R ]에서 [ L , X.. 2017. 2. 14. 이전 1 2 3 4 5 6 7 ··· 22 다음
