Why Pythonic code?

남 코드에 대한 이해도 : 많은 개발자들이 python 스타일로 코딩한다.

효율 : 단순 for loop append 보다 list가 조금 더 빠르다. 익숙해지면 코드가 짧아진다.

 

Split

type의 값을 "기준값"으로 나눠서 List 형태로 변환

a = "   EXTRA   SPACE   "

b = a.split().lower()
c = a.split(' ')

print(b)    # ['EXTRA', 'SPACE']
print(c)    # ['', '', '', 'EXTRA', '', '', 'SPACE', '', '', '']

 

list comprehension

  • 기존 List 사용하여 간단히 다른 List를 만드는 기법
  • 다른 List를 포함해서 새로운 List를 만드는 것.
  • 파이썬에서 가장 많이 사용되는 기법 중 하나
  • 일반적으로 for + append 보다 속도가 빠름
result = []
for i in range(10):
	result.append(i)
	# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

result = [i for i in range(10)]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
result = [i for i in range(10) if i % 2 == 0]
# [0, 2, 4, 6, 8]
result = [i if i % 2 == 0 else -1 for i in range(10)]
# [0, -1, 2, -1, 4, -1, 6, -1, 8, -1]

word_1 = "Hello"
word_2 = "World"
result = [i + j for i in word_1 for j in word_2]
# ['HW', 'Ho', 'Hr', 'Hl', 'Hd', 'eW', 'eo', 'er', 'el', 'ed', 'lW', 'lo', 'lr', 'll', 'ld', 'lW', 'lo', 'lr', 'll', 'ld', 'oW', 'oo', 'or', 'ol', 'od']

case_1 = ["a","b","c"]
case_2 = ["d","e","a"]
result = [i+j for i in case_1 for j in case_2] # case_1부터
# ['ad', 'ae', 'aa', 'bd', 'be', 'ba', 'cd', 'ce', 'ca']
result = [[i+j for i in case_1] for j in case_2] # case_2부터
# [['ad', 'bd', 'cd'], ['ae', 'be', 'ce'], ['aa', 'ba', 'ca']]
result = []
for i in range(10):
	result.append(i)
	# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

result = [i for i in range(10)]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
result = [i for i in range(10) if i % 2 == 0]
# [0, 2, 4, 6, 8]
result = [i if i % 2 == 0 else -1 for i in range(10)]
# [0, -1, 2, -1, 4, -1, 6, -1, 8, -1]

word_1 = "Hello"
word_2 = "World"
result = [i + j for i in word_1 for j in word_2]
# ['HW', 'Ho', 'Hr', 'Hl', 'Hd', 'eW', 'eo', 'er', 'el', 'ed', 'lW', 'lo', 'lr', 'll', 'ld', 'lW', 'lo', 'lr', 'll', 'ld', 'oW', 'oo', 'or', 'ol', 'od']

case_1 = ["a","b","c"]
case_2 = ["d","e","a"]
result = [i+j for i in case_1 for j in case_2] # case_1부터
# ['ad', 'ae', 'aa', 'bd', 'be', 'ba', 'cd', 'ce', 'ca']
result = [[i+j for i in case_1] for j in case_2] # case_2부터
# [['ad', 'bd', 'cd'], ['ae', 'be', 'ce'], ['aa', 'ba', 'ca']]

여담으로 pprint.pprint를 쓰면 이쁘게 나온다!

 

enumerate & zip

enumerate : list의 element를 추출할 때 번호를 붙여서 추출

  • 나오는 형태는 Tuple
for i, v in enumerate('abc'):
	print("{0}  {1}".format(i,v))
	# 0  a
	# 1  b
	# 2  c

for i, v in enumerate(['a','b','c']):
	print("{0}  {1}".format(i,v))
	# 0  a
	# 1  b
	# 2  c

zip : 두 개의 list의 값을 병렬적으로 추출함

alist = ['a1','a2','a3']
blist = ['b1','b2','b3']

[[a,b] for a, b in zip(alist, blist)]
# [['a1', 'b1'], ['a2', 'b2'], ['a3', 'b3']]
[c for c in zip(alist, blist)]
# [c for c in zip(alist, blist)]

list(enumerate(zip(alist, blist)))
# [(0, ('a1', 'b1')), (1, ('a2', 'b2')), (2, ('a3', 'b3'))]

 

lambda & map & reduce

lambda

함수 이름 없이, 함수처럼 쓸 수 있는 익명함수

수학의 람다 대수에서 유래함

def f(x, y):
	return x + y

f = lambda x, y : x + y

PEP 8에서는 lambda의 사용을 권장하지 않음

  • 어려운 문법
  • 테스트의 어려움
  • 문서화 docstring 지원 미비
  • 코드 해석의 어려움
  • 이름이 존재하지 않는 함수의 출현
  • 그래도 쓰는..

Map

두 개 이상의 list에도 적용 가능함, if filter도 사용가능

굳이 map을 사용하기 보다는 list comprehension을 사용하도록

ex = [1,2,3,4,5]
f = lambda x: x ** 2

list(map(f, ex))
# [1, 4, 9, 16, 25]
[f(value) for value in ex]

 

reduce

map function과 달리 list에 똑같은 함수를 적용해서 통합

대용량 데이터를 핸들링할 때, 주로 사용.

from functools import reduce

ex = [1,2,3,4,5]
f = lambda x, y: x + y

print(reduce(f,ex))
# 15

 

generator

Iterable data

  • Sequence형 자료형에서 데이터를 순서대로 추출하는 object
  • 내용이 아닌 위치정보(주소값)에 대한 정보가 저장됨.
  • next를 하면 다음 메모리 주소에 있는 값을 불러옴.
  • cities_주소 → seoul_주소 → busan_주소 → jeju_주소 → 없으므로 에러
cities = ["seoul", "busan", "jeju"]

memory_address = iter(cities)
# <list_iterator at 0x1ec8cbc6788>
next(memory_address) # seoul
next(memory_address) # busan
next(memory_address) # jeju

generator

  • iterable object를 특수한 형태로 사용해주는 함수
  • element가 사용되는 시점에 값을 메모리에 반환
  • yield를 사용해 한번에 하나의 element만 반환함.
  • 용량을 줄일 수 있기 때문에 대용량인 경우 사용하는 것이 효율적임.
import sys

def general_list(value):
	result = []
	for i in range(value):
		result.append(i)
	return result

result = general_list(50)
sys.getsizeof(result)
# 528
import sys

def generator_list(value):
	result = []
	for i in range(value):
		yield i

result = generator_list(50)
sys.getsizeof(result)
# 120
sys.getsizeof(list(generator_list(50)
# 472

When generator

  • list 타입의 데이터를 반환해주는 함수는 generator로!

→ 특히 사용하면 읽기 쉽고, 중간 과정에서 loop가 중단될 수 있을때

  • 큰 데이터를 처리할 때는 generator expression을 고려

→ 데이터가 커도 처리의 어려움이 없음.

  • 파일 데이터를 처리할 때도 generator를 사용하자

 

asterisk

함수에 입력되는 parameter의 변수명을 사용하여 argument를 넘김.

# Keyword arguments
def print_name_keyword(name, you_name):
	print("Hello {}, my name is {}".format(you_name, name))

print_name_keyword(name="aaa",you_name="bbb")

# default arguments
def print_name_default(name, you_name="NAVER"):
	print("Hello {}, my name is {}".format(you_name, name))

print_name_default("hwan")
# Hello NAVER, my name is hwan
print_name_default("hwan", "AA")
# Hello AA, my name is hwan

가변인자(variable-length)

  • 개수가 정해지지 않은 변수를 함수의 parameter로 사용하는 법
  • Keyword arguments와 함계, argument 추가가 가능
  • Asterisk(*) 기호를 사용하여 함수의 parameter를 표시함
  • 입력된 값은 tuple type으로 사용할 수 있음
  • 가변인자는 오직 한 개만 맨 마지막 parameter 위치에 사용가능
def asterisk_test(a, b, *args):
	print(a)
	print(b)
	print(args)
	print(type(args))

asterisk_test(1,2,3,4,5)
# 1
# 2
# (3, 4, 5)
# <class 'tuple'>

키워드 가변인자(Keyword variable-length)

  • Parameter 이름을 따로 지정하지 않고 입력하는 방법
  • asterisk(*) 두개를 사용하여 함수의 parameter를 표시함
  • 입력된 값은 dict type으로 사용할 수 있음
  • 가변인자는 오직 한 개만 기존 가변인자 다음에 사용
def kwargs_test(**kwargs):
	print(kwargs)
	print(type(kwargs))

kwargs_test(first=3, second=4, third=5)
# {'first': 3, 'second': 4, 'third': 5}
# <class 'dict'>

결론으로는 argument는 그냥 파라미터, 키워드 파라미터, 가변인자, 키워드 가변인자 순으로 작성해야함.

def test_3(one, two=3, *args, **kwargs):
	print(one,two, args, kwargs)

test_3(1,2,3,4,5,6,6,a=100,b=200)
# 1 2 (3, 4, 5, 6, 6) {'a': 100, 'b': 200}

 

asterisk(*)

  • 흔히 알고 있는 *를 의미함.
  • tuple, dict 등 자료형에 들어가 있는 값을 unpacking
  • 함수의 입력값, zip 등에 유용하게 사용가능
def asterisk_test(a, *args):
	print(a, args)
	print(type(args))

def asterisk_test2(a, args):
	print(a, *args)
	print(type(args))

asterisk_test(1,*(2,3,4,5,6)) # (1,2,3,4,5,6)과 같음
# 1 (2, 3, 4, 5, 6)
# <class 'tuple'>
asterisk_test(1,(2,3,4,5,6))
# 1 2 3 4 5 6
# <class 'tuple'>

data = ([1,2,],[3,4,],[5,6,])
print(*data)
# [1, 2] [3, 4] [5, 6]
for i in zip(*data):
    print(i)
# (1, 3, 5)
# (2, 4, 6)

def asterisk_test(a,b,c,d):
    print(a,b,c,d)
    
data = {"b":1,"c":2,"d":3}
asterisk_test(10, **data)
# 10 1 2 3

Python의 시작

  • 1991년 귀도 반 로섬이 발표한 언어
  • 플랫폼 독립적
  • 인터프리터 언어
  • 객체 지향 언어
  • 동적 타이핑 언어
  • 처음 C언어로 구현됨

 

이름의 유래

귀도 반 로섬이 Monpy Python's Flying circus라는 코미디프로를 좋아하여 해당 프로그램에서 이름을 따서 Python이라고 지었다고 합니다.

혹은 그리스 신화 속에서 델포이 신탁소를 지키던 뱀인 피톤에서 유래했다고도 합니다. 정확한 것은 아니지만 이러한 이유 때문에 아나콘다라는 이름이 나왔다고 생각(?)할 수 있습니다ㅎㅎ

 

Python의 특징

플랫폼 독립적인 인터프리터 언어

  • 플랫폼(OS) : 윈도우, 리눅스, 안드로이드, Mac os, ios 등 프로그램이 실행하는 운영체제를 플랫폼이라고 합니다.
  • 독립적인(관계없는, 상관없는) : OS에 상관없이 한번 프로그램을 작성하면 사용가능.
  • 인터프리터(통역기를 사용하는 언어) : 소스코드를 바로 실행할 수 있게 지원하는 프로그램 실행 방법.

결론적으로 파이썬은 파이썬 문법에 따라서 적으면 되지만 운영체제에서 작동을 하기 위해선 각각의 운영체제에 맞는 인터프리터 프로그램을 설치해서 번역해주는, 해석해주는 것이라고 생각하면 됩니다.

 

컴파일러와 인터프리터 언어의 차이점

  컴파일러 인터프리터
작동방법 소스코드를 기계어로 먼저 번역
해당 플랫폼에 최적화되어 프로그램을 실행
별도의 번역과정 없이 소스코드를 실행한 시점에 해석하여 컴퓨터가 처리할 수 있도록 함.
장점
단점
실행속도가 빠름
한 번의 많은 기억 장소 필요
간단히 작성, 메모리가 적게 필요
실행속도가 느림
주요 언어 C, C++, C#, Java 파이썬, 스칼라

 

객체 지향 언어

실행 순서가 아니라 단위 모듈(객체) 중심으로 프로그램을 작성합니다.

하나의 객체는 어떤 목적을 달성하기 위한 행동(method)와 속성(attribute)을 가지고 있습니다.

 

객체 지향 특징

  1. 캡슐화(Encapsulation)
    • 데이터(속성)와 데이터를 처리하는 함수를 하나로 묶는 것.
    • 캡슐화된 객체의 세부 내용이 외부에 은폐(정보 은닉)되어, 변경이 발생할 때 오류의 파급효과가 낮아짐.
    • 재사용 용이
  2. 정보은닉(Information Hiding)
    • 캡슐화에서 가장 중요
    • 다른 객체에게 자신의 정보를 숨기고 자신의 연산만을 통하여 접근 허용.
  3. 추상화(Abstractions)
    • 불필요한 부분을 생략하고 객체의 속성 중 가장 중요한 것에만 중점을 두어 개략화한 것.
    • 모델화 하는 것.
  4. 상속성(Inheritance)
    • 이미 정의된 상위 클래스(부모 클래스)의 모든 속성과 연산을 하위 클래스가 물려 받는 것.
    • 상속성을 이용하면 하위 클래스는 상위 클래스의 모든 속성과 연산을 자신의 클래스 내에서 다시 정의하지 않고서도 즉시 자신의 속성으로 사용가능.
  5. 다형성(Polymorphism)
    • 메시지에 의해 개체(클래스)가 연산을 수행하게 될 때 하나의 메시지에 대해 각 객체(클래스)가 가지고 있는 고유한 방법(특성)으로 응답할 수 있는 능력을 의미.
    • 객체(클래스)들은 동일한 메소드명을 사용하며 같은 의미의 응답을 함.

동적 타이핑 언어

프로그램이 실행하는 시점에 프로그램이 사용해야할 데이터에 대한 타입을 결정합니다.

간단하게 프로그램이 실행하는 시점이란 것이 동적이라는 것으로 생각하면 됩니다.

 

Why Python?!

  • 쉽고 간단하며 다양합니다.
  • 이해하기 쉬운 문법 -> 사람의 시간이 줄어든다.(사람의 시간이 기계의 시간보다 중요함)
  • 다양한 라이브러리 : 파이썬 대부분의 라이브러리가 다른 사용자에 의해서 구현되어 있습니다.

처음 들었지만 너무나 맘에 들었던 말로 마무리하겠습니다.😀

Life is short. You need Python!

문제후기

  1. 해당 조건(N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다)을 확인하고 완전탐색을 하게되면 시간초과가 발생할 것을 예상했습니다. 알고리즘은 이분탐색(logN)을 활용해야겠다고 생각하게 됐습니다
  2. 배열에 있는 값을 어떻게 하면 이분탐색으로 할 수 있을지 고민하는데 오래걸렸습니다. 같이 문제푸는 사람과 이야기를 하다가 몫과 나머지를 활용하면 어떻게 되지 않을까라는 말이 나와 몫을 활용하기 시작했습니다.
  3. 몫을 활용해서 해당 숫자가 정답을 만족하게 되는 경우 마지막값(end)을 땡기고 만족하지 않는 경우 시작값(start)을 미루는 방식으로 진행했습니다.

자세한 예시를 들어보면

문제에서 제시한 예시 3으로 보여드리겠습니다. 3을 2차배열로 만들게 되면 아래와 같아집니다.

1 2 3
2 4 6
3 6 9

 

위의 도표를 봤을때 찾는 방식은 행의 첫번째 값을 기준으로 나누는 것입니다. 중간값은 시작(1), 마지막(9)이므로 5입니다.

  1.  첫 번째 줄은 1번 값이 1. 그러므로 중간값을 1로 나누면 5//1 = 5이므로 N 3보다 크므로 5보다 작은값은 3개.
  2.  두 번째 줄은 1번 값이 2. 그러므로 중간값을 2로 나누면 5//2 = 2이므로 N 3보다 작으므로 5보다 작은값은 2개.
  3.  세 번째 줄은 1번 값이 3. 그러므로 중간값을 3로 나누면 5//3 = 1이므로 N 3보다 작으므로 5보다 작은값은 1개.
  4. 전체 총 6개가 5보다 작습니다.
  5. 시작값과 마지막값을 조정하면서 위의 과정을 반복해 K번째 값을 찾으면 됩니다.

문제링크

 

1300번: K번째 수

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B

www.acmicpc.net


from sys import stdin

# Input 값
N = int(stdin.readline())
K = int(stdin.readline())

# 이분탐색 시작값과 마지막 값.
start, end = 1, N ** 2
answer = 0  # 정답값

# 이분탐색 실행.
while start <= end:
    middle = (start + end) // 2
    count = 0
    # 해당 값이 N이상으로 나눠지는지, N개인지, 그보다 적은지 판단
    # middle보다 작은 값 갯수 카운팅
    for i in range(1, N+1):
        count += min(middle//i, N)
    
    # 만약 갯수가 K보다 많거나 작으면 end값 땡겨서 범위 축소
    if count >= K:
        end = middle - 1
        answer = middle
    # 만약 갯수가 K보다 적으면 start값 땡겨서 범위 축소
    else:
        start = middle + 1
print(answer)
print(start)

'백준' 카테고리의 다른 글

[백준] 가장 긴 바이토닉 부분 수열 -Python  (0) 2021.01.18
[백준] RGB거리 -Python  (0) 2021.01.14
[백준] 욕심쟁이 판다 -Python  (0) 2021.01.12
[백준] 절대값 힙 -Python  (0) 2021.01.10
[백준] 미확인 도착지 -Python  (0) 2021.01.09

문제후기

  1. 문제를 보고 DP를 활용하는 문제라고 판단했습니다.
  2. 계산을 편하게 하기 위해서 좌표와 메트릭스의 크기를 동일하게 하고 계산했습니다.
  3. 물 웅덩이가 없는 경우 해당 위치까지 똑같은 크기만큼 이동했기 때문에 비교할 필요 없이 더하면 됩니다.
  4. 물 웅덩이가 있는 경우 값을 0으로 만들어 제외했습니다.

문제링크

 

코딩테스트 연습 - 등굣길

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m =

programmers.co.kr


def solution(m, n, puddles):

    # 매트릭스 제작.
    matrix = [[0] * (m + 1) for _ in range(n + 1)]

    # 출발, 집 좌표
    matrix[1][1] = 1

    # DP 시작
    for y in range(1, n + 1):
        for x in range(1, m + 1):
            # 출발 값
            if y == 1 and x == 1:
                continue
            # 웅덩이가 있는 경우 패쓰
            if [x, y] in puddles:
                matrix[y][x] = 0
            else:
                # 해당 위치 값은 이전값 2개의 합.
                matrix[y][x] = matrix[y - 1][x] + matrix[y][x - 1]

    return matrix[n][m] % 1000000007

문제 후기

비슷한 문제를 이전 카카오 코테에서도 효율성으로 인해서 풀지 못한 기억이 있었다. 이번 문제 역시 제한사항으로 백만이 주어지는 것을 보고 단순 완전탐색으로 할 경우 효율성에서 오류가 날 것으로 봤다.

그래도 테스트 해보고 싶어 완전탐색으로 1차적으로 코딩을 했고, 예상했던 것처럼 효율성에서 실패했다.

2차로 했을때는 heap을 사용해서 풀었더니 해결됐다.

 

해결 방식은 테스트케이스가 어떻게 나오는지 직접해보면 규칙이 보인다. minimum 값이 어디있는지 확인해보면서 하면 규칙을 찾기 쉽다.

문제 설명

일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.

  1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
  2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.

여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.

당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.

일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.


제한 사항

  • a의 길이는 1 이상 1,000,000 이하입니다.
    • a[i]는 i+1 번째 풍선에 써진 숫자를 의미합니다.
    • a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.
    • a의 모든 수는 서로 다릅니다.

입출력 예

a result
[9,-1,-5] 3
[-16,27,65,-2,58,-92,-71,-68,-61,-33] 6

입출력 예 설명

입출력 예 #1

  • 첫 번째 풍선(9가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
    1. [9, -1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
    2. [9, -5] 에서 9, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
  • 두 번째 풍선(-1이 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
    1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
    2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
  • 세 번째 풍선(-5가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
    1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
    2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
  • 3개의 풍선이 최후까지 남을 수 있으므로, 3을 return 해야 합니다.

입출력 예 #2

  • 최후까지 남을 수 있는 풍선은 -16, -92, -71, -68, -61, -33이 써진 풍선으로 모두 6개입니다.

# 단순 계산 알고리즘(완전탐색)
def solution2(a):
    answer = 0

    minimum = min(a)
    min_idx = a.index(minimum)
    answer += 1
    min_lidx, min_ridx = 0, len(a) - 1

    if min_idx == 0:
        min_ridx = a.index(min(a[min_idx+1:]))
        answer += 1
    elif min_idx == len(a) - 1:
        min_lidx = a.index(min(a[:min_idx]))
        answer += 1
    else:
        min_ridx = a.index(min(a[min_idx + 1:]))
        min_lidx = a.index(min(a[:min_idx]))
        answer += 2

    while min_lidx > 0:
        min_lidx = a.index(min(a[:min_lidx]))
        answer += 1

    while min_ridx < len(a) - 1:
        min_ridx = a.index(min(a[min_ridx+1:]))
        answer += 1

    return answer
import heapq

# 힙을 활용한 탐색
def solution(a):
    
    answer = 0      # 결과값
    min_idx = a.index(min(a))   # 가장 작은 숫자의 인덱스
    answer += 1
    heap_left, heap_right = [], []  # min_idx를 기준으로 왼쪽, 오른쪽
    
    # 만약 min_idx의 왼쪽이 없을 경우
    if min_idx == 0:
        for i in range(min_idx+1, len(a)):
            heap_right.append((a[i],i))
    # 만약 min_idx의 오른쪽이 없을 경우
    elif min_idx == len(a) - 1:
        for j in range(min_idx):
            heap_left.append((a[j],j))
    # min_idx의 왼쪽, 오른쪽
    else:
        for i in range(min_idx+1, len(a)):
            heap_right.append((a[i],i))
        for j in range(min_idx):
            heap_left.append((a[j],j))

    # 왼쪽, 오른쪽 heap정렬
    heapq.heapify(heap_left)
    heapq.heapify(heap_right)

    temp  = 1000000     # 확인용 변수
    while heap_left:
        chk_lmin = heapq.heappop(heap_left)
        chk_idx = chk_lmin[1]
        # 가장 작은 값 인덱스가 0인 경우
        if chk_idx == 0:
            answer += 1
            break
        # heap에서 가장 작은 값은 이전 값보다 왼쪽에 있어야함.
        elif chk_idx < temp:
            answer += 1
            temp = chk_idx

    temp2 = 0   # 확인용 변수
    while heap_right:
        chk_rmin = heapq.heappop(heap_right)
        chk_idx = chk_rmin[1]
        # 가장 작은 값 인덱스가 마지막인 경우
        if chk_idx == len(a) - 1:
            answer += 1
            break
        # heap에서 가장 작은 값은 이전 값보다 오른쪽에 있어야 함.
        elif chk_idx > temp2:
            temp2 = chk_idx
            answer += 1
    return answer

문제 후기

단순히 숫자의 조합으로 해결할 수 있어서 처음에는 같은 수가 있는 순열 식을 활용하려 했다.

문제를 예를 들면 [2,1(a),1(b)] [2,1(b),1(a)] 와 같은 것이다.

계산 하는 방식은 총 갯수 n, 중복하는 숫자의 갯수 m이면 n!/ m! 이다. 따라서 1,2의 갯수만큼 나누는 것으로 했다. 하지만 Factorial의 특성으로 인해서 특정 숫자를 넘어가면 시간초과가 발생했다.

다시 처음부터 경우의 수를 확인해본 결과 1,2,3,5,8,13... 순으로 피보나치수열인 것을 확인할 수 있었다.

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

  • 타일을 가로로 배치 하는 경우
  • 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

  • 가로의 길이 n은 60,000이하의 자연수 입니다.
  • 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예

nresult

n result
4 5

입출력 예 설명

입출력 예 #1
다음과 같이 5가지 방법이 있다.


# 같은 수가 있을 때 순열 공식을 활용.
def solution(n):
    answer = 1
    count_one = n - 2
    count_two = 1

    while count_one > 1:

        answer += math.factorial(count_one+count_two) // (math.factorial(count_one) * math.factorial(count_two))
        count_one -= 2
        count_two += 1

        # print(answer)
        # print(count_one, count_two)
    if count_one == 1:
        answer += math.factorial(count_one + count_two) // (math.factorial(count_one) * math.factorial(count_two))
    else:
        answer += 1
    return answer % 1000000007
# 피보나치 수열로 계산
def solution(n):
	answer = 1
    start1 = 1
    start2 = 2

    num = 2
    while num < n:
        answer = start1 + start2
        start1 = start2
        start2 = answer
        num += 1
    return answer % 1000000007

문제 후기

2018 카카오 블라인드채용에서 나온 문제입니다. 문제를 풀면서 확인하는 능력은 문자열을 계산하는 능력으로 music info 부분을 잘 처리해야한다고 생각하고 문제를 풀었습니다. 자세한 문제 해설은 사이트(tech.kakao.com/2017/11/14/kakao-blind-recruitment-round-3/)에서 확인해보세요

문제 설명

방금그곡

라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, 라디오 등에서 나온 음악에 관해 제목 등의 정보를 제공하는 서비스이다.

네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다. 그런데 라디오 방송에서는 한 음악을 반복해서 재생할 때도 있어서 네오가 기억하고 있는 멜로디는 음악 끝부분과 처음 부분이 이어서 재생된 멜로디일 수도 있다. 반대로, 한 음악을 중간에 끊을 경우 원본 음악에는 네오가 기억한 멜로디가 들어있다 해도 그 곡이 네오가 들은 곡이 아닐 수도 있다. 그렇기 때문에 네오는 기억한 멜로디를 재생 시간과 제공된 악보를 직접 보면서 비교하려고 한다. 다음과 같은 가정을 할 때 네오가 찾으려는 음악의 제목을 구하여라.

  • 방금그곡 서비스에서는 음악 제목, 재생이 시작되고 끝난 시각, 악보를 제공한다.
  • 네오가 기억한 멜로디와 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다.
  • 각 음은 1분에 1개씩 재생된다. 음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다. 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생된다.
  • 음악이 00:00를 넘겨서까지 재생되는 일은 없다.
  • 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다. 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다.
  • 조건이 일치하는 음악이 없을 때에는 `(None)`을 반환한다.

입력 형식

입력으로 네오가 기억한 멜로디를 담은 문자열 m과 방송된 곡의 정보를 담고 있는 배열 musicinfos가 주어진다.

  • m은 음 1개 이상 1439개 이하로 구성되어 있다.
  • musicinfos는 100개 이하의 곡 정보를 담고 있는 배열로, 각각의 곡 정보는 음악이 시작한 시각, 끝난 시각, 음악 제목, 악보 정보가 ','로 구분된 문자열이다.
    • 음악의 시작 시각과 끝난 시각은 24시간 HH:MM 형식이다.
    • 음악 제목은 ',' 이외의 출력 가능한 문자로 표현된 길이 1 이상 64 이하의 문자열이다.
    • 악보 정보는 음 1개 이상 1439개 이하로 구성되어 있다.

출력 형식

조건과 일치하는 음악 제목을 출력한다.

입출력 예시

m musicinfo answer
ABCDEFG [12:00,12:14,HELLO,CDEFGAB, 13:00,13:05,WORLD,ABCDEF] HELLO
CC#BCC#BCC#BCC#B [03:00,03:30,FOO,CC#B, 04:00,04:08,BAR,CC#BCC#BCC#B] FOO
ABC [12:00,12:14,HELLO,C#DEFGAB, 13:00,13:05,WORLD,ABCDEF] WORLD

설명

첫 번째 예시에서 HELLO는 길이가 7분이지만 12:00부터 12:14까지 재생되었으므로 실제로 CDEFGABCDEFGAB로 재생되었고, 이 중에 기억한 멜로디인 ABCDEFG가 들어있다.
세 번째 예시에서 HELLO는 C#DEFGABC#DEFGAB로, WORLD는 ABCDE로 재생되었다. HELLO 안에 있는 ABC#은 기억한 멜로디인 ABC와 일치하지 않고, WORLD 안에 있는 ABC가 기억한 멜로디와 일치한다.


def solution(m, musicinfos):
    answer = ["(None)",-1]
    m = list(str(m))
    word = 0

    # "#"합치기
    while word < len(m):
        if m[word] == "#":
            m[word - 1] += "#"
            del m[word]
        else:
            word += 1

    # 시간 계산
    for music in musicinfos:
        arr = music.split(',')  # 시작, 종료, 노래, 계이름
        start, end = arr[0].split(':'), arr[1].split(':')   # 시간 확인
        start_hour, start_min = int(start[0]), int(start[1])    # 시작 시작
        end_hour, end_min = int(end[0]), int(end[1])        # 종료 시간

        hour, min =  end_hour - start_hour, end_min - start_min # 플레이 시간

        time = hour * 60 + min + 1  # 시간 -> 분

        name = arr[2]   # 노래 제목
        scale = list(str(arr[3]))   # 음계
        chk = 0
        # "#" 합치기
        while chk < len(scale):
            if scale[chk] == "#":
                scale[chk - 1] += "#"
                del scale[chk]
            else:
                chk += 1

        idx = 0
        res = []
        # 시간 만큼 계이름 입력
        while idx < time:
            res.append(scale[idx % len(scale)])
            idx += 1


        loc = 0     # 체크 시작 위치
        # 시작위치 처음부터 끝까지 확인
        while loc < len(res) - len(m):
            correct = True  # 일치여부 확인
            for c in range(len(m)):
                # m 과 계이름 확인
                if res[loc+c] != m[c]:
                    correct = False
                    break

            # 일치하면 재생 시간 계산.
            if correct:
                if answer[1] < time:
                    answer = [name, time]
                    break
            loc += 1
    
    return answer[0]    # 이름 출력

문제 후기

이전에는 중복을 없애는 것은 단순하게 dictionary를 사용해서 hash만 생각했었다. 해당 문제를 풀면서 집합의 개념을 다시 한번 확인했고 부분집합(issubset)의 활용하는 것을 알게 됐습니다.

문제 설명

후보키

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

  • 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
    • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
    • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 학번을 가지고 있다. 따라서 학번은 릴레이션의 후보 키가 될 수 있다.
그다음 이름에 대해서는 같은 이름(apeach)을 사용하는 학생이 있기 때문에, 이름은 후보 키가 될 수 없다. 그러나, 만약 [이름, 전공]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.
물론 [이름, 전공, 학년]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.
따라서, 위의 학생 인적사항의 후보키는 학번, [이름, 전공] 두 개가 된다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

제한사항

  • relation은 2차원 문자열 배열이다.
  • relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
  • relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
  • relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
  • relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

입출력 예

Relation Result
[["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2

입출력 예 설명

입출력 예 #1
문제에 주어진 릴레이션과 같으며, 후보 키는 2개이다.


# 순열 구현
def perm(lst, n):
    arr = []
    if n > len(lst):
        return arr

    if n == 1:
        for i in lst:
            arr.append([i])
    else:
        for i in range(len(lst)):
            temp = [val for val in lst]
            temp.remove(lst[i])
            for p in perm(temp, n-1):
                arr.append([lst[i]]+p)
    return arr
# 조합 구현
def comb(lst, n):
    arr = []

    if n > len(lst):
        return arr

    if n == 1:
        for i in lst:
            arr.append([i])

    else:
        for i in range(len(lst)-n+1):
            for temp in comb(lst[i+1:], n-1):
                arr.append([lst[i]] + temp)
    return arr


def solution(relation):
    # 행, 열 정의
    row, col = len(relation), len(relation[0])

    col_arr = [num for num in range(col)]

    candidate_key = []  # 후보키 가능 리스트, 유일성 만족
    key_list = []       # 키 리스트
    result_key = []     # 결과값

    # 조합으로 가능한 키 리스트 추출.
    for num in range(1, col+1):
        key_list.extend(comb(col_arr, num))

    # 키 리스트로 후보키 유일성 체크
    for key_col in key_list:
        check_key = []
        
        # 키가 후보키인지 확인
        for rel in range(row):
            data = ""
            for num in key_col:
                data += relation[rel][num]
            if data not in check_key:
                check_key.append(data)
            else:
                break
                
        # 키가 유일성을 만족.
        if len(check_key) == row:
            # 집합 형태로 추가.
            candidate_key.append(set(key_col))

    # 최소성확인
    for key in candidate_key:
        tmp = True
        if not result_key:
            result_key.append(key)
        else:
            for chk in result_key:
                # 부분집합으로 존재하면 최소성 만족 x
                if chk.issubset(key):
                    tmp = False
                    break
            if tmp:
                result_key.append(key)
    # 최종 후보키 출력
    return len(result_key)

+ Recent posts