Algorithm/baekjoon

[백준] 18353번 - 병사 배치하기 (python)

문제 병사의 전투력이 내림차순이 되도록 하는 가장 긴 수열을 구한다. 문제 바로가기 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 LIS 알고리즘을 활용하면 쉽게 풀 수 있다. "증가하는" 부분 수열이 아닌, "감소하는" 부분 수열을 만들어야 하기 때문에 reverse()를 사용해 초기 전투력을 뒤집은 후에 계산했다. 이전 LIS 포스팅 [백준] 가장 긴 증가하는 부분 수열 (LIS) 가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subse..

[백준] 1932번 - 정수 삼각형 (python)

문제 위에서부터 시작해 아래로 내려오며 각 층의 수를 하나씩 선택해 더할 때, 총합이 최대가 되는 경로를 구하여라 문제 바로가기 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 파란색 글씨가 입력으로 들어온 삼각형 모양의 숫자이고, 빨간색 글씨가 각 경우에서 누적합이 최댓값이 되는 경우이다. 코드에서 파란색이 num, 빨간색이 d에 해당한다. 맨 위 꼭짓점은 더할 수 있는 값이 없으므로 자기 자신이다. 왼쪽 변과 오른쪽에 있는 숫자의 경우, 자기 자신에 바로 위에 있는 숫자만 더할 수 있다. 중앙에 있는 숫자의 경우, 자기 자신에 윗줄의 양옆 숫자 중 최댓값을 더한다. → 그..

[백준] 11403번 - 경로 찾기 (python)

문제 가중치 없는 방향 그래프 G가 주어진다. 모든 정점에 대해 i → j로 가는 경로가 있는지 확인해, 모든 노드에서 모든 노드로의 경로 존재 여부를 출력하라. 문제 바로가기 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 모든 노드 → 모든 노드로의 최단 경로를 찾는데 사용되는 알고리즘인 플로이드-와샬 알고리즘을 사용했다. (DFS, BFS를 사용해서도 풀 수 있을 것 같다.) 이 문제에서는 자기 자신으로 가는 경로도 존재하는지 확인하는 점이 기존 플로이드-와샬 알고리즘과 다르다. a → k → b 노드 순서로 노드 k를 경유한다고 볼 때, a..

[백준] 1463번 - 1로 만들기 (python)

문제 문제 링크 접근법 처음에 조건문을 떠올렸지만, 10의 경우 최소값이 3이라는 예시를 보고 조건문으로는 구현할 수 없어서 다른 풀이를 생각했다. DP를 사용해 풀었다. 숫자 1부터 시작해 각 숫자를 1로 만들기 위한 최소 연산 횟수를 리스트 d에 저장한다. 인덱싱을 편하게 하기 위해서 사용하지 않는 인덱스 0을 만들어 0으로 초기화했다. 위 그림처럼 2나 3으로 나눈 수가 이전에 있으면, 나눈 수의 최소값+1을 하고, 아닌 경우는 이전 값+1을 한다. 2: 1에서 +1 3: 1에서 +1 4: 2에서 +1 5: 4에서 +1 6: 3에서 +1 7: 6에서 +1 8: 4에서 +1 9: 3에서 +1 10: 9에서 +1 내 풀이 각 숫자가 3의 배수인 경우, 2의 배수인 경우, 배수가 아닌 경우 순서대로 조건..

[백준] 12865번 - 평범한 배낭 (python)

문제 N개의 물건은 각각 무게 W와 가치 V를 가진다. 최대 K 무게 만큼 가방에 담을 수 있을 때, 물건의 가치 합의 최대값은? 접근법 물건을 쪼갤 수 없는 배낭 문제 (0-1 kanpsack problem)에 속한다. DP 알고리즘으로 풀이한다. 물건을 쪼갤 수 있는 배낭 문제 (fractional knapsack problem)은 무게당 가치가 최대값이 되도록 설정하면 그리디로 최적해를 찾을 수 있다. 물건 4개를 사용해 최대 무게가 5인 가방의 가치가 최대가 되도록 만드는게 목표이다. 이를 NS(ABCD, 5) 라고 표현하겠다. 물건을 모두 사용하는 경우에서 물건을 1개씩 제외해 문제를 줄여나간다. 물건을 가방에 넣는 경우, 안 넣는 경우 2가지가 가능하다. 예를 들어 물건 D를 넣는 경우는 가방..