효팍이의 프로그래밍

문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 M과 N, 그리고 K가 빈칸을 ..

문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 출력 첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다. 예제 입력1 5 8 1 2 2 1 3 3 1 4 1 1 ..

문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. 출력 각 테스트 케이스에 대해서, 섬의 개수를 출력한다..

문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다. 출력 첫째 줄부터 V개의 줄..

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 예제 입력1 5 17 출력1 4 코드 from collections ..

문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,0..

문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 ..

문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 ..

문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보..

문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때, ..

문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열..

문제 연결 리스트를 뒤집어라. 입력 : 1 → 2 → 3 → 4 → 5 → NULL 출력 : 5 → 4 → 3 → 2 → 1 → NULL 코드 """ fixme https://leetcode.com/problems/reverse-linked-list/ Q15. 역순 연결 리스트 연결 리스트를 뒤집어라. 입력 : 1 → 2 → 3 → 4 → 5 → NULL 출력 : 5 → 4 → 3 → 2 → 1 → NULL """ class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def reverseListRecur(self, head: ListNode) -> ListNode: def re..

파이썬 정규표현식 re 모듈 사용법 메타문자 파이썬에서는 특수한 기능을 하는 문자가 존재합니다. 이를 메타문자라고 하며 아래와 같이 존재합니다. $()*+.?[]\^{}| 정규표현식에 a는 문자 a와 매칭되지만 (는 (와 매칭되지 않습니다. 메타문자인 소괄호 (를 매칭하고자 하면 백슬래쉬인 \를 앞에 붙여 \(라 작성해야 문자 (와 매칭이 가능합니다. 이에 관한 설명은 여기를 참조하면 좋을 것 같습니다. re 모듈의 함수 match(pattern, string, flag) match()는 해당 패턴으로 문자열이 시작하는지를 판단합니다. import re print(re.match('a', 'ab')) print(re.match('a', 'bba')) print(re.match('a', 'ba')) # #..

문자열 내장 함수 upper() 문자열을 대문자로 변경합니다. >>> string = 'abc' >>> string.upper() 'ABC' lower() 문자열을 소문자로 변경합니다. >>> string = 'ABC' >>> string.lower() 'abc' capitalize() 첫 문자만 대문자로 변경하고, 나머지 문자들은 소문자로 변경합니다. >>> string = 'aBC' >>> string.capitalize() 'Abc' splitlines() 개행 문자를 기준으로 쪼갠다. >>> string = 'IU is \nvery pretty.' >>> string.splitlines() ['IU is ', 'very pretty.'] join() 리스트를 문자열로 바꿀 때 사용한다. >>> l..

문제 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 입력 : height = [0,1,0,2,1,0,1,3,2,1,2,1] 출력 : 6 입력 : height = [4,2,0,3,2,5] 출력 : 9 코드 from typing import List class Solution: def trapTwoPointer(self, height: List[int]) -> int: if not height: return 0 volume = 0 left, right = 0, len(height) - 1 left_max, right_max = height[left], height[right] while left < right: left_max, right_max = max(left_max, heig..

문제 당신은 전문털이범이다. 어느 집에서든 돈을 훔쳐올 수 있지만 경보 시스템 때문에 바로 옆집은 훔칠 수 없고 한 칸 이상 떨어진 집만 가능하다. 각 집에는 훔칠 수 있는 돈의 액수가 입력 값으로 표기되어 있다. 훔칠 수 있는 가장 큰 금액을 출력하라. 입력 : [1, 2, 3, 1] 출력: 4 설명 첫 번째 집에서 1, 세번째 집에서 3, 따라서 1 + 3 = 4 입력 : [2, 7, 9, 3, 1] 출력 : 12 설명 첫 번째 집에서 2, 세 번째 집에서 9, 다섯 번째 집에서 1, 따라서 2 + 9 + 1 = 12이다. 코드 """ fixme. https://leetcode.com/problems/house-robber/ fixme. Q88. 집도둑 fixme. 당신은 전문털이범이다. 어느 집에서..

0-1 배낭 문제 분할 가능 배낭 문제와 달리 짐을 쪼갤 수 없는 0-1 배낭 문제를 풀이해 보자. 이 문제는 '탐욕 선택 속성'이 있는 문제가 아니며 '중복된 하위 문제들' 속성을 갖고 있으므로 다이나믹 프로그래밍으로는 풀 수 있다. 단가 순으로 그리디하게 배치해서 풀이했던 분할 가능 배낭 문제와 달리, 0-1 배낭 문제는 짐을 쪼갤 수 없다. 이 경우 모든 경우의 수를 계산해야 한다. 먼저, 입력값으로 짐을 정의하고 zero_one_knapsack() 풀이 함수를 호출한다. cargo = [ (4, 12), (2, 1), (10, 4), (1, 1), (2, 2), ] print(zero_one_knapsack(cargo)) zero_one_knapsack() 함수는 다음과 같이 정의한다. def z..

문제 피보나치 수를 구하라. F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1. 입력 : n = 2 출력 : 1 입력 : n = 3 출력 : 2 입력 : n = 4 출력 : 3 코드 """ fixme. https://leetcode.com/problems/fibonacci-number/ fixme. Q85. 피보나치 수 fixme. 피보나치 수를 구하라. fixme. 입력 : n = 2 fixme. 출력 : 1 """ import collections import numpy as np class Solution: def fib(self, N: int) -> int: if N int: if N int: self.dp[1] = 1 for i in range..

그리디 알고리즘 그리디 알고리즘이란 바로 눈앞의 이익만을 좇는 알고리즘을 말한다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다. 그리디 알고리즘이 잘 작동하는 문제들은 탐욕 선택 속성을 갖고 있는 최적 부분 구조인 문제들이다. 여기서 탐욕 선택 속성이란 앞의 선택이 이후 선택에 영향을 주지 않는 것을 말한다. 다시 말해 그리디 알고리즘은 선택을 다시 고려하지 않는다. 또한 최적 부분 구조란 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다. 이렇게 탐욕 선택 속성과 최적 부분 구조의 2가지 조건을 만족하면 최적해를 찾을 수 있다. 하지..

문제 숫자와 연산자를 입력 받아 가능한 모든 조합의 결과를 출력하라. 입력 : "2 - 1 - 1" 출력 : [0, 2] 설명 ((2 - 1) - 1) = 0 (2 - (1 - 1)) = 2 입력 : "2 * 3 - 4 * 5" 출력 : [-34, -14, -10, -10, 10] 설명 (2 * (3 - (4 * 5))) = -34 ((2 * 3) - (4 * 5)) = -14 ((2 * (3 - 4)) * 5) = -10 (2 * ((3 - 4) * 5)) = -10 (((2 * 3) - 4) * 5) = 10 코드 """ fixme. https://leetcode.com/problems/different-ways-to-add-parentheses/ fixme. Q84. 괄호를 삽입하는 여러 가지 방법..

리스트 append()와 extend()의 차이점 >>> a = [1,2,3] >>> b = [4,5] >>> a.append(b) >>> a [1, 2, 3, [4, 5]] 리스트에 또 다른 리스트를 삽입할 때 append()는 이처럼 리스트 전체를 또 다른 엘리먼트로 처리한다. >>> a = [1,2,3] >>> b = [4, 5] >>> a.extend(b) >>> a [1, 2, 3, 4, 5] 반면 extend()는 삽입 대상의 리스트를 풀어서 각각의 엘리먼트로 확장(Extend)해 삽입한다. 출처 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]

eval() eval() 함수는 문자열을 파싱하고 파이썬 표현식으로 처리해주는 역할을 한다. 다음 예를 보면 이해가 쉽다. >>> '4+5' '4+5' >>> eval('4+5') 9 출처 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]

문제 원형으로 경로가 연결된 주유소 목록이 있다. 각 주유소는 gas[i] 만큼의 기름을 갖고 있으며, 다음 주유소로 이동하는데 cost[i]가 필요하다. 기름이 부족하면 이동할 수 없다고 할 때 모든 주유소를 방문할 수 있는 출발점의 인덱스를 출력하라. 출발점이 존재하지 않을 경우 -1을 리턴하며, 출발점은 유일하다. 입력 : gas = [1,2,3,4,5], cost = [3,4,5,1,2] 출력 : 3 설명 3번 인덱스(기름을 4만큼 충전할 수 있는)에서 출발할 경우는 다음과 같다. 3번 → 4번 -1 fuel 3 4번 → 0번 -1 fuel 6 0번 → 1번 -1 fuel 4 1번 → 2번 -1 fuel 2 2번 → 3번 -1 fuel 0 정확하게 기름이 0까지 소모되며, 모든 주유소를 방문할 수..

문제 문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라. 입력 : S = "AD0BEC0DEBANC", T = "ABC" 출력 : "BANC" 코드 """ fixme. https://leetcode.com/problems/minimum-window-substring/ fixme. Q76. 부분 문자열이 포함된 최소 윈도우 fixme. 문자열 S와 T를 입력받아 O(n)에 T의 모든 문자가 포함된 S의 최소 윈도우를 찾아라. fixme. 입력 : S = "AD0BEC0DEBANC", T = "ABC" fixme. 출력 : "BANC" """ import collections class Solution: def minWindowPointer(self, s: str, t..

문제 두 정수 a와 b의 합을 구하라. +또는 -연산자는 사용할 수 없다. 입력 a = 1, b = 2 출력 3 입력 a = -2, b = 3 출력 1 코드 전가산기 구현 class Solution: def getSum(self, a: int, b: int) -> int: MASK = 0xFFFFFFFF INT_MAX = 0x7FFFFFFF a_bin = bin(a & MASK)[2:].zfill(32) b_bin = bin(b & MASK)[2:].zfill(32) result = [] carry = 0 sum = 0 for i in range(32): A = int(a_bin[31 - i]) B = int(b_bin[31 - i]) # 전가산기 구현 Q1 = A & B Q2 = A ^ B Q3 = Q..

파이썬의 진법 표현 파이썬이 이진수(binary), 십진수(decimal), 16진수(hexadecimal)를 저장하고 표현하는 방법을 살펴보자. 먼저 이진수와 십진수는 다음과 같이 각각 bin()과 int()를 사용해서 서로 변환할 수 있다. >>> bin(87) '0b1010111' >>> int('0b1010111', 2) 87 bin()을 사용하면 이진수가 문자형 0b1010111으로 리턴된다. 반면 int()을 사용하면, 문자형인 이진수가 십진수 숫자 정수형 87로 리턴된다. 이진수임을 의미하는 접두사(Prefix) 0b는 다음과 같이 생략도 가능하다. >>> int('1010111', 2) 87 bin()을 사용해 변수에 값을 할당하면 다음과 같이 문자형이 된다. >>> a = bin(87) ..

any()와 all() 함수 >>> any([True, False, False]) True any()는 포함된 값 중 어느 하나가 참이라면 항상 참으로 출력한다. 논리 연산의 OR과 비슷하다. 반면 all()이라는 함수는 모든 값이 참이어야 True를 출력한다. >>> all([True, False, False]) False >>> all([True, True, True]) True 이처럼 all()은 논리 연산의 AND와 유사하다. 출처 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]

문제 연결 리스트를 삽입정렬로 정렬하라. 코드 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def insertionSortList(self, head: ListNode) -> ListNode: cur = parent = ListNode(0) while head: while cur.next and cur.next.val head.val: cur = parent return parent.ne..

파이썬 콤마(,) 연산자 a += b, 연산자와 변수 뒤에 콤마(,)가 붙어 있다. 이렇게 하면 어떻게 동작할까? 먼저 콤마(,)가 없는 기본적인 추가 연산을 해보자. >>> a = [1] >>> b = [2, 3] >>> a += b >>> a [1, 2, 3] 단순히 +-를 했을 때는 요소를 이어붙인다. 행렬의 연결 연산과 동일하다. 이번에는 콤마를 넣어보자. >>> a = [1] >>> b = [2, 3] >>> a += b, >>> a [1, [2, 3]] 이렇게 중첩 리스트가 된다. 콤마는 중첩 리스트로 만들어주는 역할을 하며, 대괄호 []를 부여한 것과 동일한 역할을 한다. >>> a += [b] >>> a [1, [2, 3]] 출처 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [..

@staticmethod 데코레이터 @staticmethod는 자바의 메소드 static 선언과도 비슷한데, 이렇게 정의한 메소드는 클래스와 독립적인 함수로서의 의미를 강하게 갖는다. 파라미터에도 항상 따라붙는 self가 빠져 있고, 함수 자체가 별도의 자료형으로 선언되어 있다. class CLASS: def a(self): pass @staticmethod def b(): pass 이 같은 클래스가 선언되어 있을 때, 함수 a()와 b()의 타입을 출력해보자. >>> type(CLASS.a), type(CLASS.b) (, ) 클래스를 생성하지 않고 바깥에서 직접 호출했을 때 타입은 이처럼 둘 다 함수가 된다. >>> cls = CLASS() >>> type(cls.a), type(cls.b) (, )..