우노

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=python3 문제 설명 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어, "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요. 제한사항 문자열 s의 길이 : 10..

문제 링크 https://www.acmicpc.net/problem/16719 풀이 정답을 출력할 배열을 만듭니다. 입력 문자열을 통해 아래 알고리즘을 진행합니다. 입력 문자열에서 가장 작은 알파벳을 선택합니다. 해당 알파벳을 정답 배열에 추가합니다. 정답 배열의 모든 알파벳들을 취합해 출력합니다. 해당 알파벳을 기준으로 뒷 문자열을 입력 문자열로 정해, 위 알고리즘을 반복합니다. 해당 알파벳을 기준으로 앞 문자열을 입력 문자열로 정해, 위 알고리즘을 반복합니다. 현재 알파벳을 기준으로 뒷 문자열부터 확인한 뒤, 앞 문자열을 확인하는 이유는, 현재 알파벳이 입력 문자열에서 가장 작은 알파벳이기 때문에, 현재 알파벳이 가장 앞에 와야 가장 작아지기 때문입니다. 세부 알고리즘은 아래 예제 코드와 같습니다. ..

문제 링크 https://www.acmicpc.net/problem/14719 풀이 투 포인터 알고리즘을 사용해 해결할 수 있으며, 세부 알고리즘은 아래 예제 코드를 읽으며 이해하시면 도움이 될 것 같습니다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) height = list(map(int, sys.stdin.readline().split())) # 가장 왼쪽 블록과 오른쪽 블록의 인덱스 저장 left, right = 0, len(height) - 1 # 가장 왼쪽 블록의 개수와 가장 오른쪽 블록의 개수로 초기화 left_max, right_max = height[left], height[right] # 고인 물의 개수 result = 0 ..

문제 링크 https://www.acmicpc.net/problem/2457 풀이 회의실 배정 문제의 변형판입니다. 먼저, 입력 날짜가 1월 1일이면 101, 12월 31일이면 1231처럼, 월에 100을 곱해줘서 일이랑 더해줍니다. 꽃이 피는 날짜, 꽃이 지는 날짜순으로 오름차순 정렬합니다. 정원의 마지막 꽃이 지는 날짜 end_date를 3월 1일로 초기화합니다. 모든 꽃들을 탐색합니다. 남아있는 꽃들 중, 꽃이 피는 날짜가 end_date 이전이며, 가장 느리게 지는 꽃을 찾습니다. 확인한 꽃들은 탐색 배열에서 제거합니다. 가장 꽃이 느리게 지는 날짜를 end_date로 수정합니다. 정원의 마지막 꽃이 지는 날짜가 12월 1일 이상이 됐거나, 현재 확인할 꽃의 시작 날짜가 정원의 마지막 꽃이 지는 ..

문제 링크 https://www.acmicpc.net/problem/1958 풀이 2차원 DP 테이블을 사용한 LCS 문제와 동일한 방식으로, 3차원 DP 테이블을 사용해서 해결할 수 있습니다. 기본적인 LCS 알고리즘은 해당 포스트에선 생략하겠습니다. 코드 작성은 쉬울 수 있으나, 시각적으로는 잘 그려지지 않는 것 같습니다. 코드 import sys # 각 문자열 입력 first = sys.stdin.readline().rstrip() second = sys.stdin.readline().rstrip() third = sys.stdin.readline().rstrip() # DP 테이블 초기화 dp = [[[0] * (len(third)+1) for _ in range(len(second)+1)] fo..

문제 링크 https://www.acmicpc.net/problem/2169 풀이 특정 좌표로 갈 수 있는 방법은 아래와 같습니다. 위에서 오는 것 왼쪽에서 오는 것 오른쪽에서 오는 것 5x5 샘플 데이터를 통해 좌표 값들을 업데이트해보겠습니다. 먼저, 첫 번째 행은, 왼쪽에서 오른쪽로 진행하는 경우 밖에 없으므로, 각 좌표까지의 최대 가치를 먼저 업데이트할 수 있습니다. 이제 나머지 행들을 순서대로 탐색하며 좌표값들을 업데이트해야합니다. 이때, 각 행들을 두 가지 임시 배열(왼쪽 → 오른쪽으로 진행 시 구해진 최댓값, 오른쪽 → 왼쪽으로 진행 시 구해진 최댓값)로 표현한 뒤, 두 임시 배열을 비교함으로써, DP 테이블의 각 좌표를 최대값으로 업데이트할 수 있습니다. 왼쪽 → 오른쪽으로 진행될 경우, 임..

문제 링크 https://www.acmicpc.net/problem/5582 풀이 대표적인 DP 문제이며, 2차원 DP 테이블을 사용해서 풀 수 있습니다. 2차원 DP 테이블의 행과 열을 각각의 문자열로 구성한 뒤, 이중 for문을 통해 각각의 문자들을 비교하며, 각각의 문자가 같다면, 이전 공통 부분 문자열 길이에 1을 더해 저장해나가면 됩니다. 코드 # PyPy3로 제출 import sys # 각각의 문자열 first = sys.stdin.readline().rstrip() second = sys.stdin.readline().rstrip() # DP 테이블 dp = [[0] * (len(second)) for _ in range(len(first))] # 두 문자열에 모두 포함 된 부분 문자열 중 ..

문제 링크 https://www.acmicpc.net/problem/7579 풀이 0-1 냅색(배낭) 문제이며, 0-1 냅색 알고리즘의 개념을 알고 있다면 문제에 대해 더 쉽게 이해할 수 있습니다. https://www.youtube.com/watch?v=rhda6lR5kyQ 문제의 목표 특정 메모리를 넘는 최소 비용을 찾는 것 DP 테이블이 의미하는 것 0~i 까지의 앱을 종료하거나 종료하지 않았을 때, j 만큼의 cost를 사용함으로써 확보 가능한 최대 메모리값 아래 알고리즘을 진행합니다. 행은 앱의 개수만큼, 열은 cost의 총 비용만큼 만들어줍니다. 행을 차례대로 돌며 아래 알고리즘을 차례대로 수행합니다. j cost보다 현재 앱의 cost가 크다면, 아직 앱이 종료되지 않았으므로, 최대 메모리가..

문제 링크 https://www.acmicpc.net/problem/10942 풀이 2차원 DP 테이블을 채우는게 핵심입니다. DP[i][j]는, i 부터 j 까지의 숫자가 팰린드롬인지 아닌지를 나타냅니다. DP 테이블은 아래 조건을 통해 채워나갑니다. 연속된 숫자가 1개일 경우엔, 무조건 팰린드롬입니다. 연속된 숫자가 2개일 경우엔, 양끝 숫자가 같다면 팰린드롬입니다. 연속된 숫자가 3개 이상일 경우엔, 양끝 숫자가 같고, 그 사이의 숫자들이 팰린드롬이라면, 팰린드롬입니다. 따라서, 1번과 2번 조건을 실행한다면 DP 테이블은 아래와 같이 채워집니다. 이후, 3번 조건을 실행한다면, DP 테이블의 하향 대각선이 차례대로 채워집니다. 연속된 숫자가 3개일 때는, 세번째 하향 대각선 연속된 숫자가 4개일 ..

문제 링크 https://www.acmicpc.net/problem/10164 풀이 학창 시절에 배웠던 경로 찾기 방법을 사용하면 됩니다. 만약, (0, 0) 칸부터 (N-1, M-1) 칸까지의 경로를 찾는다면, 첫 행과 첫 열을 1로 채운 뒤, 빈 칸을 왼쪽 칸과 위쪽 칸의 덧셈 결과로 채워주면 됩니다. 따라서, 해당 방법을 사용해, 시작 지점에서 중간 지점까지의 경로를 구하고 중간 지점에서 마지막 지점까지의 경로를 구한 뒤, 두 값을 곱해주면 됩니다. 코드 import sys # 격자의 행의 수 n과 열의 수 m, ○로 표시된 칸의 번호 n, m, k = map(int, sys.stdin.readline().split()) # 경로 저장용 DP 테이블 graph = [[0]*m for _ in ran..