All155 [KOI 초등부 / 메모리초과] BOJ 17609 회문 (2019 1차 대회) 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 유형 : DP라고 생각했는데 좀 더 생각해봐야겠다. DP로 풀려니까 N = 100,000인데다가 O(N^2)이라 안풀린다. 흠. 2019. 12. 25. [KOI 초등부] BOJ 17608 막대기 (2019 1차 대회) 불러오는 중입니다... 문제 유형 : 개인적으론 ad-hoc인듯 해설 : 먼저 막대기의 길이를 배열에 저장, 막대기의 개수가 N이라고 했을때 오른쪽에서 바라보므로 N-1, N-2, ... , 0 이렇게 마지막 원소부터 차례대로 순회를 하는데, "지금까지 순회한 막대기 중 가장 긴 것"보다 길이가 긴 경우에만 개수를 더해주면 된다. 지금까지 순회한 막대기 중 가장 큰 것 보다 작거나 같은 경우는 눈에 보이지 않기 때문 문제의 테스트 케이스를 직접 그려보면 이해가 잘 된다. 구현 : 2019. 12. 25. [NetworkFlow] 네트워크 유량과 포드 풀커슨 알고리즘 이번 글에서는 네트워크 유량 문제 (네트워크 플로우)와 포드 풀커슨 알고리즘에 대해 알아보자. 네트워크 유량 문제 (Network Flow Problem) 원래의 그래프는 간선을 거리, 비용으로 생각했다면, 유량 네트워크 (Flow Network)에서는 단방향 그래프에서 간선의 가중치를 최대로 흐를 수 있는 용량(capacity)과 실제로 흐르는 유량(flow)으로 생각한다. 이게 무슨 말이냐 하면 A에서 B로 가중치가 10이 존재한다면, A에서 B로 흐를 수 있는 최대 물의 양이 10이라고 해석할 수 있다. (실제로 물이 얼마나 흐르는지는 우리가 얼마나 흘려보내냐에 따라 다르다.) 이제 유량 네트워크가 뭔지 대충 느낌을 알았는데, 그래서 네트워크 유량이 뭐냐? 하면 네트워크 유량은 이 유량 네트워크에서.. 2019. 12. 24. 동적 프로그래밍(Dynamic Programming)의 개념 DP 문제를 풀다가 DP에 대한 이해가 부족한 것 같아서 글로 정리해본다. Dynamic Programming 동적 프로그래밍이란 큰 문제를 작은 문제로 분할하여 문제를 푸는 방법이다. 이 용어는 리처드 벨만이 처음 사용했는데, 이름에 큰 의미는 없다. 그냥 멋있어서 사용했다. 아무튼간에 이 방법을 사용하는 이유는, 큰 문제가 작은 문제를 포함하는 구조를 갖고 있을 때, 작은 문제를 알면 큰 문제의 정답을 빠르게 구할 수 있다는 점이다. 위의 코드를 한 번 읽어보자. 1 = 1 2 = 2 + 1 3 = 3 + 2 + 1 ... 100 = 100 + 99 + 98 + ... + 3 + 2 + 1 이런 식으로 구하는데, 잘 보면 3 = 3 + 2 + 1을 구할 때, 여기서 2 + 1은 sum(2)와 동일하므.. 2019. 10. 7. DP 문제가 잘 안 풀린다. 요즘 DP 문제가 고민인데, DP문제 카테고리의 문제를 봐도 왜 DP인지 잘 모르겠고 (왜 부분 문제가 겹치는지 잘 이해가 되지 않고), 계속 전에 풀었던 문제랑 비슷비슷한 문제만 풀린다. 생각해보니 알고리즘 강의 중에서 DP 강의가 길어서 중간에 하차를 했다. 내일부터는 강의 정주행으로 가자! 2019. 10. 7. [백준] 9251번 LCS (Longest Common Subsequence) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제를 풀기 전에 알아야 할 개념 : Dynamic Programming LCS란? LCS란 두 문자열 str1과 str2가 있다고 할 때, 공통된(Common) 부분 수열(Substring) 중, 가장 긴 것(Longest)을 의미한다. 여기서 Subsequence의 개념을 명확히 할 필요가 있는데, 원래 문자열의 글자를 몇 개 선택해서 원래 문자.. 2019. 10. 6. 이전 1 ··· 20 21 22 23 24 25 26 다음
