문제 개요문자열 리스트로 표현된 Unix 경로가 주어졌을 때, 이를 정규화된 최종 경로로 변환하는 프로그램을 만들어 보겠습니다. Unix 시스템에서 ..는 한 단계 위(상위) 디렉터리로 이동한다는 의미이고, .는 현재 디렉터리에 머무른다는 의미입니다. 따라서 경로 정규화란 이 두 기호를 모두 처리하여 실제로 도달하게 되는 최종 디렉터리를 계산하는 과정을 말합니다.예를 들어 입력이 다음과 같다고 가정해 보겠습니다.[usr, .., usr, ., local, etc, foo]이 경로를 문자열로 연결하면 /usr/../usr/./loca

문제 이해하기문자열 s와 숫자 n이 주어졌을 때, 문자열을 n개의 행으로 재배열하는 문제입니다. 재배열된 결과를 위에서 아래로, 왼쪽에서 오른쪽으로 읽으면 원래 문자열이 복원되며, 이렇게 세로 방향으로 문자를 분산시키는 방식을 수직 암호(Vertical Cipher)라고 합니다. 간단하지만 원래 문장의 형태를 숨기는 기본적인 암호화 기법 중 하나입니다.예를 들어 입력이 s = ilovepythonprogramming, n = 5라면, 출력은 다음과 같습니다.[ipnrn, lypag, otrm, vhom, eogi]동작 원리 시각화문

비제네르(Vigenère) 암호란?비제네르 암호는 16세기부터 알려진 고전적인 다중 알파벳 치환 암호입니다. 모든 문자를 동일한 값만큼 밀어내는 카이사르 암호와 달리, 키(key) 문자열의 각 문자가 알파벳에서 차지하는 위치(A=0, B=1, ..., Z=25)를 개별 시프트 값으로 사용합니다. 이 글에서는 파이썬으로 비제네르 방식의 문자열 암호화 프로그램을 직접 구현해 보겠습니다.문제 정의소문자 알파벳으로 이루어진 문자열 text와 키 문자열 key가 주어져 있다고 가정합시다. 우리가 구해야 할 것은 text의 각 문자를 key의

문제 개요소문자로만 이루어진 문자열 s가 주어졌을 때, 문자열에 포함된 모든 모음(vowel)을 사전순으로 정렬한 뒤, 그 뒤에 자음(consonant)을 사전순으로 정렬하여 이어 붙인 새로운 문자열을 만드는 것이 목표입니다.예를 들어 입력이 helloworld라면 출력은 eoodhlllrw가 됩니다. 이 문자열에서 모음은 e, o, o 세 개이며, 자음을 정렬하면 d, h, l, l, l, r, w 순서가 되기 때문입니다.풀이 접근 방법이 문제는 다음과 같은 단계로 해결할 수 있습니다.모음을 담을 문자열 k와 자음을 담을 문자열

문제 설명숫자 n, p, q가 주어진다고 가정해 봅시다. 우리는 n명의 사람들이 줄 서 있는 곳에 서 있습니다. 정확히 몇 번째 위치에 서 있는지는 알 수 없지만, 앞쪽에는 최소 p명이 있고 뒤쪽에는 최대 q명이 있다는 사실은 알고 있습니다. 이때 우리가 설 수 있는 가능한 위치의 개수를 구하는 것이 목표입니다.예를 들어 입력이 n = 10, p = 3, q = 4라고 해보겠습니다. 총 10명이 있고, 앞에 최소 3명, 뒤에 최대 4명이 있어야 하므로, 우리가 설 수 있는 인덱스는 [0, 1, 2, 3, 4]로 총 5개입니다. 예를

문제 개요시간 순서대로 나열된 어떤 회사의 주가 리스트가 있다고 가정해 봅시다. 이때 딱 한 번 주식을 사고팔아 얻을 수 있는 최대 이익을 구해야 합니다. 단, 반드시 먼저 매수한 후에 매도해야 한다는 조건이 있습니다.예를 들어 입력이 다음과 같다면,prices = [10, 12, 9, 6, 8, 12]출력은 6이 됩니다. 6원일 때 매수하고 12원일 때 매도하면 이익은 12 − 6 = 6이 되기 때문입니다.해결 접근 방법이 문제는 배열을 한 번만 순회하면서 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.지금까지 확인한 주가

무방향 그래프(undirected graph)가 주어졌을 때, 해당 그래프가 이분 그래프(bipartite graph)인지 확인하는 문제를 살펴보겠습니다.이분 그래프란 그래프의 모든 정점을 두 집합 A와 B로 나눌 수 있어서, 그래프의 모든 간선 {u, v}에 대해 한쪽 끝점 u는 집합 A에, 다른 끝점 v는 집합 B에 속하도록 분할할 수 있는 그래프를 의미합니다. 즉, 어떤 간선도 같은 집합 내부(A→A 또는 B→B)를 연결하지 않아야 합니다.예시예를 들어 다음과 같은 그래프가 입력으로 주어진다고 가정해 봅시다.이 경우 출력은 T

시간순으로 정렬된 어떤 회사의 주가 리스트가 있다고 가정해 봅시다. 이때 해당 주식을 원하는 만큼 여러 번 사고팔았을 때 얻을 수 있는 최대 수익을 구하는 것이 목표입니다. 단, 매도하기 전에 반드시 먼저 매수해야 한다는 조건을 기억해야 합니다. 예를 들어 입력이 prices = [10, 50, 30, 40, 60]이라면 출력은 70이 됩니다. 10에 매수해서 50에 팔고, 다시 30에 매수해서 60에 팔면 되기 때문입니다. 문제 해결 접근 방법 이 문제는 탐욕 알고리즘(Greedy Algorithm)으로 간단하게 해결할 수 있습니

숫자로 이루어진 리스트 nums와 숫자 k가 주어졌다고 가정해 보겠습니다. 우리는 인덱스 k에서 시작하며, 현재 위치한 인덱스 i에서는 정확히 nums[i]칸만큼 왼쪽 또는 오른쪽으로 점프할 수 있습니다. 목표는 리스트의 마지막 인덱스까지 도달할 수 있는지 확인하는 것입니다.문제 예시예를 들어 입력이 다음과 같다고 해봅시다.nums = [0, 0, 2, 1, 3, 3, 1, 1] k = 2이 경우 출력은 True가 됩니다. 인덱스 2에서 시작하면 값이 2이므로 인덱스 4로 점프할 수 있고, 인덱스 4의 값이 3이므로 마지막 인덱스

문제 개요문자열 리스트 words와 문자열 letters가 주어졌을 때, letters에 포함된 문자들을 사용하여 만들 수 있는 words 중 가장 긴 문자열의 길이를 구하는 프로그램을 작성해야 합니다.단, 다음 두 가지 조건이 있습니다.각 문자는 한 번만 사용할 수 있으며 재사용이 불가능합니다.만들 수 있는 단어가 하나도 없다면 0을 반환합니다.예시입력이 다음과 같다고 가정해 보겠습니다.words = [dog, cat, rat, bunny, lion, bat] letters = gabctnyu이 경우 출력은 3이 됩니다. 사용 가

문제 개요n × n 크기의 정방형 행렬 M이 주어졌을 때, 행렬 안에서 알파벳 Z 모양을 이루는 모든 요소의 합을 구하는 프로그램을 작성해 보겠습니다.Z 모양은 첫 번째 행 전체, 마지막 행 전체, 그리고 반대각선(부 대각선) 요소들로 구성됩니다.예를 들어 다음과 같은 행렬이 입력으로 주어진다고 가정해 봅시다.432918256이 경우 Z 모양을 이루는 요소는 4, 3, 2, 1, 2, 5, 6이며, 이들의 합은 23입니다. 즉, 출력 결과는 4+3+2+1+2+5+6 = 23이 됩니다.풀이 접근 방법이 문제는 다음 단계를 따라 해결할

문제 이해하기 이번 글에서는 대표적인 동적 계획법(DP) 문제인 0/1 배낭 문제(Knapsack Problem)를 파이썬으로 해결하는 방법을 살펴보겠습니다. 길이가 같은 두 개의 리스트 weights와 values, 그리고 하나의 숫자 capacity(용량)가 주어진다고 가정해 봅시다. 여기서 weights[i]와 values[i]는 각각 i번째 아이템의 무게와 가치를 나타냅니다. 목표는 다음과 같습니다: 담은 아이템들의 총 무게가 capacity를 초과하지 않아야 합니다. 각 아이템은 최대 한 번만 선택할 수 있습니다. 위 조

두 개의 이진 문자열 a와 b가 주어졌을 때, 이 두 이진수를 더한 합계를 구하고 그 결과 역시 문자열 형태로 반환해야 합니다.예를 들어 입력이 a = 10110, b = 10010이라면, 출력은 101000이 됩니다.문제 해결 접근 방법이 문제는 우리가 손으로 이진수 덧셈을 하는 방식과 동일하게 풀 수 있습니다. 뒷자리부터 한 자리씩 더하면서 올림수(carry)를 관리하면 됩니다. 구체적인 단계는 다음과 같습니다.결과를 저장할 빈 문자열 ret을 준비합니다.na := a의 길이, nb := b의 길이로 설정합니다.i := na -

nums라는 숫자 리스트가 주어져 있고, 이 리스트는 한 노선에 있는 버스 정류장들을 나타낸다고 가정해 봅시다. 여기서 nums[i]는 버스가 i번째 정류장에 반드시 도착해야 하는 시간을 의미합니다. 버스는 뒤로 돌아갈 수 없이 앞으로만 이동할 수 있으므로, 우리는 모든 정류장을 지나가기 위해 필요한 최소 버스 대수를 구해야 합니다.예를 들어 입력이 nums = [1, 2, 7, 9, 3, 4]라고 한다면, 출력은 2가 됩니다. 한 대의 버스가 시간순으로 [1, 2, 3, 4] 정류장을 순서대로 지나갈 수 있고, 또 다른 한 대가

계단이 n개 있고, 한 번에 1칸 또는 2칸씩만 오를 수 있다고 가정해 봅시다. 이때 이 계단을 끝까지 오를 수 있는 서로 다른 방법의 개수를 반환하는 함수를 정해야 합니다.계단을 오르는 순서가 다르면 별개의 방법으로 간주합니다. 즉, 같은 칸수 조합이라도 순서가 다르면 새로운 방법으로 셉니다. 만약 답이 매우 커질 경우에는 결과를 10^9 + 7로 나눈 나머지를 반환하도록 합니다.문제 예시예를 들어 입력이 n = 5라면, 출력은 8이 됩니다. 계단을 오르는 방법은 다음과 같이 총 8가지입니다.1, 1, 1, 1, 12, 1, 1,

문제 설명n개의 계단과 숫자 k가 주어졌다고 가정해 보겠습니다. 우리는 처음에 0번째 계단에 서 있으며, 한 번에 1칸, 2칸 또는 3칸씩 올라갈 수 있습니다. 다만 3칸씩 오르는 동작은 최대 k번까지만 허용됩니다. 이 조건 안에서 계단 꼭대기(n번째 계단)까지 도달할 수 있는 방법이 총 몇 가지인지 구하는 것이 목표입니다.예제입력이 n = 5, k = 2라면 출력은 13입니다. 계단을 오를 수 있는 서로 다른 방법은 아래와 같습니다.[1, 1, 1, 1, 1][2, 1, 1, 1][1, 2, 1, 1][1, 1, 2, 1][1,

숫자 리스트 nums와 숫자 k가 주어졌다고 가정해 보겠습니다. 우리는 인덱스 k에서 출발하며, 임의의 인덱스 i에 있을 때 정확히 nums[i]칸만큼 왼쪽 또는 오른쪽으로 점프할 수 있습니다. 이때 리스트의 마지막 인덱스에 도달할 수 있는지 판별하는 것이 이 글의 목표입니다. 예를 들어 입력이 nums = [0, 0, 2, 1, 3, 3, 1, 1], k = 2라면 결과는 True입니다. 인덱스 2에서 시작해 값 2만큼 점프하여 인덱스 4로 이동하고, 다시 값 3만큼 점프하여 마지막 인덱스 7에 도달할 수 있기 때문입니다. 해결

문제 이해하기숫자 리스트 nums가 주어졌을 때, 가능한 모든 연속된 부분 배열(contiguous subarray)을 고려합니다. 각 부분 배열의 합을 계산한 뒤 이 값을 모두 더하고, 최종 결과를 10⁹ + 7(1,000,000,007)로 나눈 나머지를 반환하는 것이 목표입니다.예를 들어 입력이 nums = [3, 4, 6]이라면 다음과 같은 부분 배열들이 존재합니다.[3], [4], [6], [3, 4], [4, 6], [3, 4, 6]각 부분 배열의 합은 순서대로 3, 4, 6, 7, 10, 13이며, 이를 모두 더하면 43

문제 정의길이가 같은 두 개의 비어 있지 않은 문자열 s와 t가 있다고 가정해 봅시다. 우리는 이 문자열들을 여러 부분 문자열로 나누어야 하며, s의 각 조각과 t의 대응되는 조각은 반드시 같은 길이를 가져야 하고 서로 아나그램(anagram), 즉 같은 문자들로만 구성되어야 합니다.목표는 이 조건을 만족하면서 잘라내기 지점(cut index)을 찾아 최대한 많은 수의 분할을 만드는 것입니다. 만약 가능한 방법이 없다면 빈 리스트를 반환하면 됩니다.예시입력이 다음과 같다고 해봅시다.s = bowcattiger, t = owbacti

문제 개요카드 리스트가 주어졌을 때, 카드가 오름차순으로 공개되도록 초기 배치를 만들어야 한다고 가정해 보겠습니다. 카드는 다음과 같은 규칙에 따라 공개됩니다.맨 위의 카드를 제거하여 공개한 뒤, 그다음 카드를 맨 뒤로 보냅니다.카드가 모두 없어질 때까지 1번 과정을 반복합니다.즉, 우리는 카드가 오름차순으로 공개되도록 만드는 올바른 배치 순서를 찾아야 합니다.예시로 이해하기예를 들어 입력이 cards = [1, 2, 3, 4, 5, 6, 7, 8]이라면, 출력은 [1, 5, 2, 7, 3, 6, 4, 8]이 됩니다. 과정을 단계별