성실한 삶 성실한 삶

접근방법DP 풀이법 중에서 비트마스크를 이용한 DP 의 대표적인 문제이다. 외판원 순회 문제는 쉽게 요약하면 한명의판매원이 모든 도시를 한번씩 방문한뒤 출발지로 돌아오는 최소 비용을 구하는 문제이다.그냥 일반 DP는 느낌이 누적합, 1,2 차원적 문제의 DP 느낌이라면 비트마스크를 이용한것은 상태가 많은 부분집합의 DP 느낌이다. 예를 들면 DP의 대표적인 문제인 배낭문제가 무게, 가치 dp[개수][무게]를 이용하여 지금까지 고려한 물건의 수와 무게를 상태로 사용하여 최대 가치를 찾는 것이라면 외판원 순회는 만약 도시가 4곳이라고 가정한다면 dp[1 0~ 15가 16개 이므로 MAX값은 (1 방문한 도시를 1 방문하지 않은 도시를 0 이라고 했을때 0000 부터 1111까지의 상태를 이용하여 DP를 진행..

https://www.acmicpc.net/problem/1644  접근방법소수의 연속합 문제는 저번 문제와 같은 연속된 소수들의 합이 n이 되는 경우의 수를 세는 문제이다.연속된 이라는 말이 있으니 투포인터를 사용하면 시간 효율성이 높아질것이고, 소수를 판별해야 하니 소수 판별법을 써서 소수를 걸러내야 될것이다. 그래서 나는 이렇게 구상했다. 1. 소수 목록 만들기2. 투포인터로 경우의 수 찾기(오른쪽 포인터가 n을 넘으면 탈출)3. 출력 일단 소수 목록은 사람들이 많이 쓰는 에라토스테네스의 체를 쓰기로 했다.에라토스테네스의 체는 특정범위의 소수를 빨리 찾는 알고리즘으로 대량으로 바르게 찾는 방법이다.방법은 다음과 같다.1. 소수가 아닌 1을 제거한다.2. 2부터 소수인 수의 배수를 제거한다.(지워진 ..

접근방법부분합 문제는 N개의 10000 이하 자연수가 주어지고 이 수열에서 연속된 수의 합 중에 s이상이 되는것, 그중에서 길이가 짧은 것을 찾는것이다.그렇게 되면 투포인터를 쓸수있다. 조건은 l 포인터 부터 r 포인터까지 더한게 s보다 크면 l을 늘려 줄이고 작으면 r을 늘려 크게 만들면된다. 탈출 조건은 r이 n을 넘으면 이다.즉 r이 n이 넘을 때까지 조건문을 반복하며 s보다 같거나 크면 연속된 수의 크기를 저장 하고 다시 비교하고 작은거 저장하고... 반복하다보면 문제 해결이다. 투포인터 문제인걸 캐치하고 조건문만 잘 설정하면 쉬운 문제이다.가장 주의할 점은 만약 못찾았을 경우이다. 이때는 초기 값을 아예 int 최대값 (INT_MAX)로 잡아 못찾아서 min_size(연속된 수의 길이)를 수정하..

접근방법두 용액 문제는 서로 다른 n개의 정수가 주어졌을때, 두 수의 합이 0에 가까운 수를 찾는 문제이다.보통 이럴때 가장 쉽게 푸는 방법은 전체의 경우의 수를 비교하는 것이지만(브루트포스), 안타깝게도 대부분의 문제는 그러면 시간초과가 나오게 설정이 되어있다. 그러므로 시간을 최대한 효율적이게 쓰는 알고리즘을 사용해야한다. 방법은 두개 생각했다. 한개는 이진탐색이고 한개는 투포인터이다. 이진 탐색을 사용했을때 따로 조건문을 많이 사용해야할것 같아서 투포인터로 풀었다. 투 포인터는 간단하게 설명하면 움직이는 포인터를 두 개로 만들것이다.만약 이 문제처럼 1차원 배열로 예를 들면  이렇게 생각할수있다. 조건에 따라 포인터 1을 움직일지 포인터 2을 움직일지 고르면된다.(이 방법은 배열을 한번 순회해서 배..

현대 오토에버 대비 다이나믹 프로그래밍 문제중 하나인 LCS(최장 공통 부분 수열)문제이다.말그대로 두 수열이 주어졌을때 두 부분 수열이 되는 수열중 가장 긴 것을 찾는 것이다.0부터 n까지 공통된 문자만 찾아서 비교하면된다. 문자열의 문자는 정해지지 않으므로찾으려는 결과 값은 dp[i][j] = 문자열 a의 i글자와 문자열 b의 j글자 간의 공통 수열 길이 이렇게 나타낼수있다. 그렇다면 초기값은 dp[0][j] = 0, dp[i][0] = 0이다.그리고 앞에 배낭문제처럼 이 문제도 만약 공통된 수를 찾으면 value를 증가 시키면 된다. 이때 value 값은 +1 이다.그렇다면 점화식을 구할수있다. dp[i][j] = dp[i-1][j-1] +1 이다.처음엔 dp[i][j] +1 를 적용 시킬까 생각을..

접근방법현대 오토에버 대비 다이나믹 프로그래밍 문제중 하나다.저번 배낭 문제에서 말했듯이 다이나믹 프로그래밍은 문제를 동일한 여러 하위 문제로 쪼개서 푸는 프로그래밍이다. 1,2,3 더하기는 주어진 정수 n 만큼 11보다 작은 양의 정수를 입력하고 이 정수가 되는 1 2 3의 합의 경우의 수를 구하는 문제다. 그렇다면 초기 조건은 dp[1]  = 1, dp[2] = 2, dp[3] = 4 이다.(1,2,3을 나타내는 경우의 수) 그렇다면i정수의 경우의 수는 dp[i] = dp[i-1]+dp[i-2]+dp[i-3] 이렇게 나타낼수있다 왜냐하면n = 4일때 경우의 수는 7이다dp[1]은 1이다 dp[2]은 2이다.dp[3]은 4이다이를 보면 dp[4] = 7 이므로 dp 1 2 3 을 더한 값과 같다다음을 ..

접근방법현대 오토에버 코딩 테스트 준비 대비 문제로 푼 문제이다.  원래는 c 스타일의 코드를 c++의 문법으로 풀었는데, 코딩 테스트는 c로 풀어야해서 c++로 푼걸 다시 c로 변환 해봤다. 다이나믹 프로그래밍의 대표적인 문제인 배낭 문제로 배낭 문제란 제한된 무게를 가진 가방에 물건을 담을때 가치의 합을 최대로 넣는 방법을 찾는 문제이다.다이나믹 프로그래밍의 특징은 문제를 작은 하위 문제로 만들수 있고, 이러한 동일한 하위 문제가 반복된다는 것이다.다르게 말하면 기억하며 풀기라고도 말할 수 있다. 이는 특정 문제에서 모든 조합을 계산하는 브루트포스 알고리즘보다 시간을 효율적이게 쓸수있다.만약 i번째 물건까지 고려했을 때 , 무게가 w일때의 최대 가치는 dp[i][w]라고 가정하면, 초기 조건 dp[0..

접근방법그리디 알고리즘 보강 추천 문제 중 하나이다. 문제 요약하면 1차원 고속도로 위에 센서가 원점을 기준으로 위치별로 N개가 있는데 이 센서를 기지국에 다 포함시켜야한다. 기지국의 개수는 K개이다. 즉, 센서를 K개의 그룹으로 나눈뒤 나눈 그룹중 최소 거리의 합을 출력하면된다.쉽게 쉽게 단계를 나눠 보았다.1. N개 센서 입력2. N개의 센서 정렬3. 정렬된 센서들 사이의 거리를 다른 컨테이너에 저장(N ,N+1)4. 컨테이너를 내림차순으로 정렬 그 후 센서들의 최대 거리의 합을 저장5. K-1(K가 1이면 돌 필요가 없음)번 센서들 끼리의 거리가 큰 순서로 최대 거리의 합에 빼기 연산6. 연산값을 출력 순으로 진행 하였다.   처음 딱 코드를 한후 테스트 케이스를 확인 한후 제출을 해봤는데 Out ..