문제 개요 비어 있지 않은 문자열 s와 단어 목록을 담고 있는 사전 wordDict가 주어집니다. 문자열 s에 공백을 삽입하여 각 단어가 사전에 등록된 유효한 단어가 되도록 문장을 구성하고, 만들 수 있는 모든 가능한 문장을 찾아야 합니다. 예를 들어 문자열이 appleraincoat이고 사전이 [app, apple, rain, coat, raincoat]라고 한다면, 만들 수 있는 문장은 다음과 같습니다. apple rain coat apple raincoat 해결 전략: 재귀 + 메모이제이션 이 문제는 백트래킹(backtra

후위 순회(Postorder Traversal)는 이진 트리 순회 방식 중 하나로, 각 노드를 왼쪽 자식 → 오른쪽 자식 → 루트 순서로 방문합니다. 이 글에서는 재귀 함수 없이 스택(Stack)만을 이용해 후위 순회를 반복적(iterative)으로 구현하는 방법을 살펴보겠습니다.예를 들어 다음과 같은 이진 트리가 주어졌다고 가정해 보겠습니다.이 트리의 후위 순회 결과는 다음과 같습니다.[9, 15, 7, 10, -10]알고리즘 접근 방법재귀 호출은 함수 호출 오버헤드가 있고, 트리의 깊이가 매우 깊은 경우 스택 오버플로우가 발생할

문제 개요2차원 격자 형태의 보드(board)와 단어 목록(words)이 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 사전에 포함된 단어들 중에서 보드 위에서 실제로 만들 수 있는 모든 단어를 찾아내는 것입니다.단어를 구성할 때는 반드시 다음 두 가지 규칙을 지켜야 합니다.각 단어는 순차적으로 인접한 셀의 문자들을 연결하여 만들어야 하며, 인접 셀이란 상·하·좌·우로 붙어 있는 셀을 의미합니다.같은 문자 셀은 하나의 단어 안에서 두 번 이상 재사용될 수 없습니다.예를 들어 아래와 같은 입력이 주어진 경우를 생각해 볼 수 있습니다

개요프로그래밍 문제 중 하나로, 주어진 숫자를 영어 단어 형태로 변환하는 작업이 있습니다. 숫자의 범위는 0부터 2³¹ − 1까지이며, 예를 들어 입력값이 512라면 결과는 Five Hundred Twelve가 되어야 합니다.이번 글에서는 Python을 활용해 이 문제를 단계별로 해결하는 방법을 알아보겠습니다.해결 접근 방식이 문제는 숫자를 자릿수 단위로 나누어 처리하는 재귀적 방법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.less_than_20 리스트: 1부터 19까지의 숫자에 해당하는 영어 단어를 저장합니다. (

문제 정의 하나의 문자열, 즉 비밀번호가 주어졌을 때 이를 강력한(strong) 비밀번호로 만들기 위해 필요한 최소 변경 횟수를 구하는 문제입니다. 강력한 비밀번호는 아래 세 가지 조건을 모두 충족해야 합니다. 길이 조건: 최소 6자 이상, 최대 20자 이하여야 합니다. 문자 종류 조건: 소문자, 대문자, 숫자를 각각 최소 하나씩 포함해야 합니다. 반복 조건: aaa, PPP, 888처럼 같은 문자가 세 번 연속으로 나타나서는 안 됩니다. 예를 들어 입력이 aa26bbb라고 해보겠습니다. 이 문자열에는 대문자가 없고 b가 세 번

문제 개요 정수 n이 주어졌을 때, n을 k진수(k ≥ 2)로 나타냈을 때 모든 자릿수가 1이 된다면 k를 n의 좋은 기반(good base)이라고 부릅니다. 숫자 n이 문자열 형태로 주어지면, 가능한 좋은 기반 중 가장 작은 값을 문자열로 반환해야 합니다. 예를 들어 n이 121이라면 정답은 3입니다. 121을 3진수로 표현하면 11111이 되는데, 실제로 1 + 3 + 9 + 27 + 81 = 121이 성립하기 때문입니다. 핵심 아이디어 밑이 k이고 자릿수가 m개인 모두 1로만 이루어진 수는 다음과 같은 등비수열의 합으로 표현

문제 소개N × N 크기의 격자가 있고, 각 셀 (x, y)에는 램프가 하나씩 놓여 있다고 가정해 봅시다. 처음에는 일부 램프만 켜져 있으며, lamps[i]는 켜져 있는 i번째 램프의 위치를 나타냅니다. 켜진 램프는 자신이 위치한 x축 방향, y축 방향, 그리고 두 대각선 방향의 모든 칸을 비춥니다.이제 i번째 질의 queries[i] = (x, y)에 대해, 셀 (x, y)가 비춰지고 있다면 답은 1, 그렇지 않다면 0입니다. 또한 각 질의가 처리된 후에는 해당 셀 자신과 인접한 8방향 셀에 있는 램프를 모두 꺼야 합니다. 최종

문제 설명100만 행 × 100만 열로 이루어진 거대한 격자(grid)가 있다고 가정해 보겠습니다. 격자에는 통행이 금지된 칸(blocked cell) 목록이 주어져 있으며, 우리는 시작 칸(source)에서 출발해 목표 칸(target)에 도달해야 합니다. 매 이동 시에는 상·하·좌·우로 인접한 칸 중 차단 목록에 없는 칸으로만 걸어갈 수 있습니다.목표는 일련의 이동을 통해 목표 칸에 도달하는 것이 가능한지 판별하는 것입니다.예를 들어 blocked = [[0,1],[1,0]], source = [0,0], target = [0,

데이터를 다루다 보면 문자열로 전달되지만 그 내부 구조는 파이썬 리스트와 동일한 경우가 종종 있습니다. 예를 들어 파일이나 API 응답에서 받은 데이터가 [Mon, 2, Tue, 4]처럼 리스트 모양의 문자열일 수 있는데, 이대로는 인덱싱이나 반복문 등 리스트 연산을 사용할 수 없습니다. 이 글에서는 문자열로 묶인 리스트를 실제 파이썬 리스트 객체로 변환하는 대표적인 세 가지 방법을 소개합니다. 1. eval() 함수 사용하기 eval() 함수는 문자열로 전달된 파이썬 표현식을 그대로 평가하여 실제 결과를 반환합니다. 따라서 리스

Python은 날짜와 시간을 다루는 강력하고 다양한 기능을 제공합니다. 이 글에서는 적절한 형식의 문자열을 datetime 객체로 변환하는 방법과, 그 반대로 datetime 객체를 문자열로 변환하는 방법을 알아보겠습니다.strptime() 함수로 문자열을 DateTime으로 변환하기datetime 모듈의 strptime() 함수는 형식 지정자(format specifier)를 사용하여 문자열을 datetime 객체로 변환할 수 있습니다. 변환하려는 문자열의 구조에 맞는 형식 코드를 함께 전달하면 됩니다.주요 형식 지정자%B: 월의

파이썬에서 리스트(list)는 여러 값을 순서대로 담는 자료구조인 반면, 딕셔너리(dictionary)는 키(key)와 값(value)이 한 쌍을 이루는 형태로 데이터를 저장합니다. 이 글에서는 서로 다른 두 개의 리스트를 하나로 묶어 딕셔너리로 변환하는 대표적인 세 가지 방법을 예제 코드와 함께 소개합니다.1. for문과 remove() 활용두 개의 중첩된 for 루프를 사용하는 방식입니다. 내부 루프에서 한 리스트의 요소를 딕셔너리의 키로 할당하고, 외부 루프가 진행되는 동안 해당 값을 리스트에서 제거하며 처리합니다.예제list

문제 개요부울 표현식이 주어졌을 때, 해당 표현식을 평가한 결과를 구하는 문제입니다. 표현식은 다음과 같은 형태로 구성될 수 있습니다.t — True로 평가됩니다.f — False로 평가됩니다.!(expression) — 내부 표현식의 논리 NOT 결과를 반환합니다.&(expr1, expr2, ...) — 2개 이상의 내부 표현식에 대한 논리 AND 결과를 반환합니다.|(expr1, expr2, ...) — 2개 이상의 내부 표현식에 대한 논리 OR 결과를 반환합니다.예를 들어 입력이 |(!(t),&(t,f,t))라면 출력은 Fal

프로그래밍을 하다 보면 리스트 안에 숫자 형태의 문자열이 들어 있는 경우가 종종 있습니다. 예를 들어 [5, 2, -43, 23]처럼 값 자체는 숫자이지만 따옴표로 묶여 있어 문자열로 취급되는 상황입니다. 이런 경우 연산이나 비교를 위해서는 문자열 요소들을 실제 정수(int) 타입으로 변환해야 합니다.방법 1: int() 함수와 리스트 컴프리헨션 사용파이썬의 int() 함수는 숫자 형태의 값을 받아 정수로 변환해 줍니다. 리스트의 각 요소에 이 함수를 적용하려면 for 반복문을 활용할 수 있는데, 가장 파이썬다운 방식은 리스트 컴프

문자열 안에 여러 요소가 담겨 있어 마치 리스트처럼 보이는 경우가 있습니다. 그런데 이 요소들이 키-값(key-value) 쌍을 나타내고 있다면, 같은 문자열을 딕셔너리로도 표현할 수 있습니다. 이 글에서는 이렇게 리스트 형태로 작성된 문자열을 파이썬 딕셔너리로 변환하는 두 가지 방법을 소개합니다.1. split()과 슬라이싱 활용하기첫 번째 방법은 split() 함수와 슬라이싱을 조합하는 방식입니다. 먼저 문자열 양 끝의 대괄호를 슬라이싱([1:-1])으로 제거한 뒤, 쉼표를 기준으로 요소를 나누고 각 요소를 다시 콜론(:)으로

문자열이 주어졌을 때, 그 안에 포함된 모음(vowel)이 몇 개인지, 어떤 모음들이 사용되었는지 분석해 보겠습니다. Python에서는 다양한 방법으로 이 작업을 수행할 수 있으며, 대표적인 두 가지 방법인 set을 활용한 방법과 fromkeys를 활용한 방법을 소개합니다.1. set을 이용한 방법먼저 문자열에서 고유한(unique) 문자들을 추출한 뒤, 해당 문자가 모음 집합에 속하는지 검사하여 결과를 확인할 수 있습니다.예제 코드stringA = Tutorialspoint is best print(주어진 문자열:\n, strin

프로젝트를 진행할 때 필요한 스킬 목록 req_skills과 사람 목록 people이 주어진다고 가정해 봅시다. 여기서 i번째 사람인 people[i]는 해당 사람이 보유한 스킬들의 리스트를 나타냅니다.문제 정의충분한 팀(sufficient team)이란, req_skills에 포함된 모든 필수 스킬을 팀원 중 적어도 한 명이 가지고 있는 사람들의 집합을 의미합니다. 이러한 팀은 각 사람의 인덱스로 표현할 수 있습니다. 예를 들어 팀이 [0, 1, 3]이라면, 이는 people[0], people[1], people[3] 세 명으로

파이썬에서는 딕셔너리의 키-값 쌍 중 값(value) 자체가 리스트로 구성된 경우가 종종 있습니다. 예를 들어 요일 목록이나 과목 목록처럼 여러 데이터를 하나의 키에 담아야 할 때 유용합니다. 이 글에서는 이렇게 딕셔너리 값으로 저장된 리스트에 포함된 항목의 개수를 세는 대표적인 세 가지 방법을 예제와 함께 살펴봅니다.1. isinstance 함수 활용하기가장 기본적인 방법은 isinstance() 함수를 사용하는 것입니다. 딕셔너리를 순회하면서 각 값이 리스트인지 검사하고, 리스트라면 해당 리스트의 길이만큼 카운트를 증가시킵니다.

문자열 text가 주어졌을 때, 다음 세 가지 조건을 모두 만족하는 최댓값 k를 찾는 문제입니다.각 a[i]는 비어 있지 않은(non-empty) 문자열이어야 합니다.a[1] + a[2] + ... + a[k]의 연결 결과가 주어진 text와 같아야 합니다.모든 i(1 ≤ i ≤ k)에 대해 a[i] = a[k+1-i]가 성립해야 합니다. 즉, 앞쪽에서 i번째 조각과 뒤쪽에서 i번째 조각이 서로 같은 문자열이어야 합니다.예를 들어 입력이 antaprezatepzapreanta라면 출력은 11이 됩니다. 이 문자열은 다음과 같이 11

리스트와 튜플이 함께 주어졌을 때, 리스트의 요소들이 튜플 안에서 몇 번 나타나는지 확인해야 하는 경우가 있습니다. 예를 들어 요일 데이터가 담긴 튜플에서 특정 요일이 몇 번 등장하는지 세는 상황을 생각할 수 있습니다. 이번 글에서는 파이썬으로 이를 해결하는 두 가지 대표적인 방법을 살펴보겠습니다. 1. Counter 활용하기 collections 모듈의 Counter 클래스를 사용하면 튜플에 포함된 각 요소의 등장 횟수를 한 번에 구할 수 있습니다. 이후 for 문과 in 연산자를 조합해, 리스트에 있는 요소 중 튜플 카운트 결과

파이썬 프로그래밍에서 문자열과 특정 문자가 주어졌을 때, 그 문자가 문자열 안에서 총 몇 번 나타나는지 확인해야 하는 경우가 자주 있습니다. 이 글에서는 대표적인 세 가지 방법을 예제 코드와 함께 소개합니다.1. range와 len 함수 활용for 루프를 사용해 인덱스로 문자열의 각 문자에 하나씩 접근하면서 주어진 문자와 일치하는지 비교합니다. range와 len 함수는 문자열을 왼쪽에서 오른쪽으로 순회할 때 비교 작업을 몇 번 수행해야 하는지 범위를 정해주는 역할을 합니다.예제 코드Astr = How do you do char =