개발자로 살아남기

이 문제는 다이나믹 프로그래밍을 이용하여 해결 할 수 있다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1878&sca=3050

도착시간 기준으로 방문했을때의 최소값을 기록하여 확인 가능하다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=763&sca=3050

DP를 이용하여 해결한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=298&sca=3050

N개의 동전의 가치를 합하여, K원을 만드는 경우를 구한다. 1, 2, 5 원의 동전을 이용하여 10원을 만드는 경우는 다음과 같다. 사용동전1 2 5 개수 1 1 1 2 1+1 2 2 3 1+1+1 1+2 2 4 1+1+1+1 1+1+2, 2+2 3 5 1+1+1+1+1 1+1+1+2, 1+2+2 5 4 5원을 만드는 경우는 위와 같다. 1원동전 사용: 1원을 5개 사용2원동전 사용: 3원을 만드는 경우에 2원을 더하여 생성5원동전 사용: 0원을 만드는 경우에 5원을 더하여 생성 https://www.acmicpc.net/problem/2293

BFS를 이용하여 익지 않은 토마토가 존재하는 곳으로 한번씩 이동하여 더이상 처리할 곳이 없을 때 까지 이동하면 된다. BFS 이용시 재귀를 이용하게 되면 스택오버플로우가 발생한다.

두줄로 타일깔기는 라인 길이에 따라 타일을 배열하는 방법을 생각해서 처리하면된다. 구현할 때 재귀를 이용하여 처리하면 stack overflow 가 발생한다. f(n) 을 구하는 방법은 f(n-1) 의 타일 개수에 1 x 2 타일을 하나 추가하는 방법과f(n-2)의 타일 개수에 2 x 2 타일을 추가하는 방법 두개를 더하면 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=687&sca=3050http://huiyu.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%ED%83%80%EC%9D%BC-%EC%B1%84%EC%9A%B0%EA%B8%B0-%EB%AC%B8%EC%A0%9C

전깃줄 문제는 다이나믹 알고리즘의 LIS를 응용하는 문제이다. 입력받은 전봇대의 쌍 중에서 하나를 기준으로 정렬하여, 정렬되지 않은 전봇대중 가장 많이 정렬되어 있는 전봇대의 값에서 전체를 빼면 제거해야할 최소의 전봇대 개수가 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=684&sca=3050

색종이 만들기는 사각형을 4등분하여 나누어 가면서 색종이가 모두 하나의 색인지를 확인하여 나가면 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=614&sca=3060

정올 같은 사이트의 문제해답을 올리시는 분이 있어서 스크랩 해석을 상세하게 해주시기 때문에 많은 도움이 된다. http://comganet.github.io/dp/2016/06/03/dp-1007

계단오르기는 다이나믹으로 해결할 수 있다. 연속해서 오른 계단이 하나인 것과 두개인 것을 계산하여 처리할 수 있다. 1번은 연속해서 오른 계단이 하나인것, 즉 두번 뛰어서 오른 계단에 대한 정보를 확인하는 것이다. i-2 번째 계단의 1번 연속, 2번 연속해서 오른 계단의 최대값가 현재 계단의 값의 합이다. 2번은 연속해서 오른계단이 두개인것, 즉 이전계단에서 한번오른 것이다. 이전계단에서 한번오른 값과 현재의 값을 더하여 결정한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=792&sca=3050

숫자카드 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있다. 27123을 2글자씩 읽어서 숫자로 확인하고 34이상이면 분할한다. 27, 123 으로 분할하고 카드로 표현할 수 있는 형태가 몇개인지 확인한다. 카드로 표현 가능한 개수는 마지막 수를 표현하는 카드가 한자리 수인지, 두자리 수인지로 구분하여 점화식을 구성한다. D[i] = (D[i-1][0] * 2 )/2 + D[i-1][1] + (D[i-1][0] * 2 )/2 끝자리가 한자리수이면 마지막에 하나더 숫자가 붙어서 두자리 또는 한자리가 될수 있기 때문이다. 끝자리가 두자리수 이면 한자리수로 붙어서 표현이 가능하다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=683&sca=3050

각 노드에서 자신을 제외한 노드로 이동하는 최단거리를 구하여 모두 더하는 문제이다. BFS를 이용하여 문제를 해결할 수 있다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=388&sca=50&sfl=wr_hit&stx=1108&sop=and

극장좌석문제는 다이나믹 프로그래밍으로 풀이가 가능하다. 전제조건은 좌우 한칸으로는 이동이 가능하다. 좌석이 2개일 경우 아래의 두개의 경우가 가능1, 22, 1좌석이 3개일때는 좌석이 2개인 경우에서 끝자리가 2인 경우는 3과 교환이 가능하기 때문에 2가지 경우가 나오고, 1인경우는 3과 교환이 불가능 하여 끝에 3이 붙는 하나의 경우만 나온다. 끝이 2 인 경우: (1*2)/2 + 1 = 2끝이 2 이 아닌 경우: (1*2)/2 = 1좌석이 3개인 경우 3가지 종류가 가능1, 2 -> 1, 2, 3 1, 3, 22, 1 -> 2, 1, 3좌석이 4개일때는 좌석이 3개인 경우에서 끝자리가 3인 경우는 4와 교환이 가능하기 때문에 4가지 경우가 나오고, 2인 경우는 4와 교환이 불가능하이 끝에 4가 붙는 ..

숫자를 1, 2, 3 으로 문자열에 하나씩 붙여 가면서문자열의 길이를 반으로 나눠서 확인할 수 있는 가장 긴 길이부터 1개까지 확인하여 좋은 수열인지 확인한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=306&sca=3030

그리디 알고리즘을 이용하여 저울 문제를 해결할 수 있다.

동전교환은 다이나믹 프로그래밍으로 해결한다. 잔돈이 n 이고, c가 코인일때 f(n) = f(n - c) + 1가 된다. 현재 잔돈에서 코인을 뺀돈의 코인개수가 있다면 거기에 +1을 하게 되면 현재의 코인개수가 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1273&sca=3050

몇명이 하얀 모자를 쓰고 있는지 찾아내는 문제이다. 말하는 사람이 하얀 모자를 쓰고 있는 경우와 쓰고 있지 않은 경우의 하얀 모자 개수를 모두 확인해서 가장 많이 나온 하얀 모자의 개수가 실제 쓰고 있는 하얀 모자의 개수이다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1215&sca=50&sfl=wr_subject&stx=%ED%95%98%EC%96%80&sop=and

LIS 문제중 가장 간단한 형태인것 같다. 숫자들중 순서대로 나보다 큰 숫자들 중 정렬이 가장 많이 되어 있는 숫자를 찾아서 +1을 하여 기록한다. http://saecom-dalcom.tistory.com/9http://comganet.github.io/dp/2016/06/03/dp-1007http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1144&sca=3050

가장높은 탑 쌓기 문제는 다이나믹 프로그래밍을 이용하여 처리한다. 우선 밑면의 넓이 기준으로 정렬을 하면 현재 인덱스보다 작은 인덱스의 무게만 비교하면 넓이는 신경쓰지 않고 확인할 수 있다. 대신 정렬을 이용하기 때문에 기존의 인덱스가 변하게 되므로 인덱스만 따로 저장해 둔다. 그다음은 현재 벽돌보다 작은 무게의 벽돌을 찾아서 현재벽돌의 높이 + 작은무게벽돌의 높이(자신의 위에 있는 벽돌의 높이도 추가되어 있음)만 저장한다. 더 큰 높이의 벽돌이 있으면 갱신한다. 올릴 수 있는 벽돌이 없다면 자신의 높이만 저장한다. 이렇게 result 배열에 결과를 저장하고가장 높은 높이의 벽돌을 찾아서 해당 벽돌의 인덱스를 역순으로 찾아서 출력하면 된다. http://www.jungol.co.kr/bbs/board.p..

배낭채우기문제는 다이나믹으로 처리한다. 배낭의 무게를 10부터 이동해가면서, 현재 시점에 최고의 무게를 확인하면서, 현재의 무게를 뺀 이전 무게의 최고값과 현재의 최고값을 더하면서 배낭을 채우면 된다. 보석 배낭무게 무게 가치 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 40 - 40 40 80 90 120 150 140 190 200 230 260 270 300 3 50 - - 50 50 90 100 130 160 170 200 210 240 270 280 5 110 - - - - 110 110 150 160 190 220 230 260 270 300 10 200 - - - - - - - - - 200 200 240 250 280 맥스값 - 40 50 80 110 120 150 160..

매시간 공기가 되는 부분을 먼저 계산하고,이전에 없어진 부분을 제거하면서 백트래킹으로 처리해 가면 처리할 수 있음 http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1113&sca=3030

사각형으로 표시되지 않는 영역, 빈곳을 100부터 기록해서 나중에 100 이상인 값이 몇개인지 세어서 영역을 구한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=729&sca=3030

백트래킹을 이용한 스도쿠 처리 0으로 입력되어 입력가능한 값을 확인해야 하는 목록을 확인후에 해당 리스트를 순서대로 순회하면서 입력 가능한 값을 확인하면서 모든 값을 입력하면 종료한다.

택배 문제는 도착지점을 기준으로 정렬하여싣고 갈 수 있는 택배를 용량으로 확인하여 최대 값을 확인할 수 있다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1903&sca=3020

화학 물질을 온도가 낮은 순으로 정렬하고 온도가 겹치면 같은 냉장고에 입력하고, 온도가 겹치지 않으면 다른 온도의 냉장고를 선택하면 냉장고를 설정할수 있다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=3020

정올의 그리디 알고리즘 1060문제최소비용 신장트리 * 프림알고리즘을 이용하여 풀이함 최소비용의 노드를 연결하고, 현재 연결된 노드중 최소비용의 노드를 추가하면서 더 이상 방문할 노드가 없으면 종료한다. https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

아무리 생각해도 해결책이 생각이 나지 않았는데 다른분이 푸신 방법을보고 해결함 사용가능한 최소의 동전개수를 구하기 위해서는동전의 총합으로 사용가능한 최대값에서 구하려는 동전의 값을 뺀 나머지를 구할 수 있는최대의 동전개수를 구해서 남은 나머지가 최소의 값이 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=466&sca=3020http://m.blog.naver.com/skyblue_2002/220631970001

경로찾기 해밍코드 찾는 방법은 문자열을 char 배열로 변환하고, 다른 부분을 체크하여 반환한다.

정올 1495번 문제대각선 지그재그 배열의 크기 n을 입력 받아서 아래와 같이 출력1 3 4 2 5 8 6 7 9 http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=767&sca=20

그리디 알고리즘의 요플레 공장 1주일 보관하는데 드는 비용을 추가해서 최소값을 계산하면 최소 비용이 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1454&sca=3020