패스트터틀

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net LIS = Longest Increasing Subsequence, 최장증가수열이다. 주어진 값에서 증가하는 수의 집합들중 가장 큰 원소의 개수를 구하는 방법에 관한 문제이다. 어떠한 알고리즘이 해당문제를 푸는데 최적화된 알고리즘인것을 보장할수있는것은 어떻게 알수가 있을까? 문제를 풀다보니 회의감이 ..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net https://sudeky.tistory.com/126 (Baekjoon) brute-force - (1) 부분수열의 합( + 부분집합 출력) https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 우선 부분수열의 합을 구하기전에 부분집합을 출력하는방법을 할줄 알아야한다. 부분집합을 출력하는방법은 visited로 표현할수있는데 예를들어서 1,2,3,4 를 가지고 부분집합을 구성할때 visited가 1000 이라면 1 visited가 1110 이라면 123 visited가 0011 이라면 34 ... 의 식으로 표현하면 모든 부분집합을 표현할수 있다. pac..

본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다. 목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. - dp - bitmask - lis - dp dp = dynamic programming 의 약자로 단어자체와 개념은 전혀 연관이없으며 쉽게말해서 기억하며 프로그래밍하는것이다. 예를들어서 fibonacci 수열을 구할때 다음과 같이 코딩을 할수있다. 예를들어서 int dp(int x){ if(x==1) return 1; if(x==2) return 2; return dp(x-2) + dp(x-1); } int main(){ cout

ㅇ 기본적인 틀 ㅇ A에서 A2 -> A3 -> ... -> An 까지 호출후 An -> An-1 -> ... -> A2 -> A1 순서대로 반환 Stack을 쌓고 회수하는 과정이다. 재귀함수가 어려운이유 1. 인간의 직관으로 이해해야 하는영역이기 때문에 직관적이라는 장점과 직관적이라는 단점이 존재 2. 기존에 접해보지 않은 반복문이라 익숙하지 않음 예를들어서 기본 반복문과의 차이점을 살펴볼때 1부터 10까지 출력하는 프로그램 작성하였을때 for(int i = 0 ; i < 10 ; i++){ System.out.println("%d", i); } 위와 같이 단순 반복문을 사용할경우에는 매우 쉽지만 public class _Ere{ // 1부터 10까지 출력한다. static void sum(int a)..

우선 이 책의 저자 질 볼트 테일러는 뇌과학자이며 뇌졸중을 37세에 걸렸고 그 경험을 통해서 우리가 가진 행복에 대하여 깨달은 바를 전달하는 책이다. 책으로 나오기도 했지만 이 주제로 TED에서 강연을 하기도 했었다. 책을 읽지 않더라도 한 번쯤 보기를 추천한다. 영적은 무엇일까? 내가 최근에 읽은 책 '신의 유전자'라는 책을 읽을 때에는 인간이 가진 본능이며 생물학적으로 우뇌스러울 때(우뇌 경향) 즉, 어떤 감정과 공감각에 대한 인식이 높은 사람들이 대게 영적 체험을 많이 한다고 소개했었다. 이와 관련해 좌뇌가 마비되었을 때 즉, 우뇌만 작동할 때는 어떻게 될까? 정말로 영적 체험에 가깝게 느낄까? 질 볼트 테일러는 뇌과학자이며 이와 관련한 경험을 뇌졸중을 통해 겪었다고 얘기한다. 뇌졸중의 순간일 때 ..

전투에 참가한 한 전사가 자신의 방패는 나약함이라고 여겼다. 그리고 전투에서 항상 두 개의 검으로 날아오는 검과 화살을 막았다. 하지만 그것은 몇 번일 뿐 결국 자신의 몸과 손에는 수많은 흉터와 상처가 생겼다. 몸에 상처가 많은 날에는 자신의 검이 더 좋지 못했다고 생각했으며 검을 더 날카롭고 가볍고 강하게 그리고 검을 더 잘 다루기 위해 매일매일 수련을 했다. 가끔은 숙련된 검술로 화려해 보였지만 그것은 겉만 화려한 실용적이지 않는 방법이었다. 방패가 없는 전사는 용감한 것이 아니고 멍청한 것이다. 나는 지금까지 그러한 멍청한 용사였다. 방패를 들지 않았었다. 물리적인 방패를 말하는 것이 아니다. 마음의 방패다. 우리가 흔히 알고 있는 '방어기제'에 대한 이야기이다. 나는 방어기제란 나약함의 상징이며 ..

https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net dp(n) = 2*dp(n-1) + 3*dp(n-2) + 2*(dp(n-3) + dp(n-4) + dp(n-5) + ....+ dp(0)) 위의 그림과 같은 과정을 통해 위의 점화식을 도출할수 있다. 그리고 코드를 짜서 제출할경우 시간초과를 겪는데 그러한 이유를 살펴보면은 2*(dp(n-3) + dp(n-4) + dp(n-5) + ....+ dp(0)) 부분에서 계속 구한값을 다시 계산하고 다시계산하는것을 알수있다. 이부분 또한 동적프로그래밍 기법을 적용하여서 한번구한값은 다시 구하지 말자라는 방식을 써야..