All154 [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.] 딥러닝이란 무엇인가? 학습 목표 :- 인공지능, 머신러닝, 딥러닝의 관계를 파악할 수 있다.- 딥러닝의 장단점, 활용 분야를 안다. 1.1 인공지능, 머신러닝, 딥러닝 인공지능, 머신러닝, 딥러닝 모두 근 3년간 (주관적인 생각이다.) 핫한 키워드다. 특히 딥마인드의 알파고가 이세돌 9단을 이겼다는 것을 기점으로 국내에도 인공지능 열풍이 불기 시작했다고 생각한다. 그런데 이 세 단어에 관심 있는 사람은 많지만 정확하게 아는 사람은 별로 못 본것 같다. 차이가 뭘까? 하나씩 살펴보자. 그림 1-1은 구글에 인공지능의 정의를 검색한 결과이다.인공지능은 아주 포괄적인 의미로, 머신러닝 딥러닝 할 것 없이 사람이 기계를 이용해 지능을 만들면 다 인공지능이다.(지능의 정의가 좀 애매하긴 하지만 여기선 논외로 한다.) 머신 러닝(Mac.. 2018. 9. 19. 이전 1 ··· 20 21 22 23 24 25 26 다음
