python

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

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

[DP] 가장 긴 증가하는 부분 수열 (LIS)

가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)은 대표적인 다이나믹 프로그래밍 문제이다. {10, 20, 10, 30, 20, 50} 과 같은 수열이 주어졌을 때, 수가 점점 증가하는 수열의 가장 긴 길이를 구한다. 1) Dynamic Programming 풀이법 - O(N^2) 파라미터 설명: n = 수열의 길이 arr = 수열을 이루는 숫자가 담긴 배열 d = arr[i]를 마지막 원소로 가질 때 LIS의 길이 d[i] 값을 1로 초기화한다. 현재 위치(i)보다 이전에 위치한 원소(j)가 작은지 확인한다. (i는 기준이 되는 인덱스, j는 i보다 작은 인덱스) arr[i] > arr[j] 이면, 현재 위치 숫자 중 d의 최댓값..

[백준] 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의 배수인 경우, 배수가 아닌 경우 순서대로 조건..

[프로그래머스] 단어 변환 (Python)

문제 begin으로 주어진 단어에서 시작해 target 단어를 만드려고 한다. words에 주어진 단어 리스트를 사용해 target 단어로 변환할 수 있는데, 한 번에 알파벳이 1개만 다른 단어로 변환할 수 있다. 가장 짧은 변환 과정은? (문제 링크) 내 풀이 BFS로 풀이했으며 deque 라이브러리로 큐를 사용했다. words에 존재하지 않아 변환할 수 없는 단어는 0을 반환한다. (시작 단어, 0)을 queue에 넣는다. queue 요소를 하나 꺼내고, 꺼낸 단어와 1글자만 다른 단어를 큐에 삽입한다. 정답 단어를 찾으면 반환하고, 찾지 못하면 계속 반복한다. from collections import deque # 한 글자만 다른 단어인지 확인 def is_valid(word, target): s..

[LeetCode] #200. Number of Islands (Python)

문제 1인 부분은 땅으로 지나갈 수 있고, 0은 바다로 지나갈 수 없다. 땅/바다 정보가 들어있는 2차원 배열이 주어졌을 때, 총 섬의 개수를 구하여라. (문제 링크) 풀이 1 땅/바다 정보가 들어있는 지도 grid 를 탐색하면서 땅인 위치를 찾으면 해당 위치에서 4방향으로 땅이 있는지 dfs를 수행한다. dfs를 완료하면 연결된 땅을 다 방문했기 때문에 섬의 개수를 1 증가시킨다. dfs()를 살펴보면: 탐색하는 좌표 (x, y)의 위치가 지도의 크기를 벗어나거나 이미 방문할 수 없는 곳(바다 또는 이미 방문한 곳)이면 종료한다. 아래와 같이 탐색할 수 있는 조건으로 코드를 짤 수도 있다. 하지만 3개의 AND 조건을 확인하는 것 보다 OR 조건을 확인하는 시간이 짧아 탐색할 수 없는 조건을 사용했다...

[이코테] 고정점 찾기 (Python, 이진탐색)

문제 고정점(Fixed Point)이란 수열의 원소 중에서 값이 인덱스와 동일한 원소를 의미한다. 예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때 a[2] = 2 이므로 고정점은 2가 된다. 하나의 수열이 N개의 서로 다른 원소로 이루어지며, 모든 원소는 오름차순으로 정렬되어있다. 수열에서 고정점이 있다면 고정점을 출력하는 프로그램을 작성해라. 시간 복잡도 O(logN)인 알고리즘을 작성해야 한다. # 예시1 n = 5 arr = [-15, -6, 1, 3, 7] # res = 3 # 예시2 n = 7 arr = [-15, -4, 2, 8, 9, 13, 15] # res = 2 # 예시3 n = 7 arr = [-15, -4, 3, 8, 9, 13, 15] # res = -1 풀이 ..

[프로그래머스] 괄호 변환 (Python) / 카카오 2020

문제 위의 규칙에 따라 입력 문자열을 "올바른 괄호 문자열"로 변환하려고 한다. 문제 링크 재귀는 특정 과정(규칙)을 특정 조건까지 수행한 결과를 반환하는 문제가 대부분이다. 몇 단계만 그림을 그려보면 재귀를 이해하는데 큰 도움이 된다. p = "()))(())" 일 때 올바른 괄호 문자열로 변화하는 과정을 그리면 위의 그림과 같다. 풀이 is_balanced() : 균형잡힌 문자열인지 확인하는 함수: ( 괄호와 ) 괄호의 개수가 같은지 확인 is_correct() : 올바른 문자열인지 확인하는 함수 → 스택(deque 또는 list)을 사용해 이전 요소와 짝이 맞으면(반대되는 괄호이면) 이전 요소를 삭제하고, 짝이 맞지 않으면(동일한 괄호이면) 삽입한다. do_split() : u, v를 쪼개는 함수 ..

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

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