IndexError 이유

input n 이 0일 때 dp[1] = stairs[1] 에서 stairs[1]에 접근하기 때문
또한 n 이 1, 2, 3 일때도 dp 초기화에서 같은 문제가 발생한다.
input n이 0 이면 stairs에는 -1만 들어있는 상태이기 때문에, 리스트가 stairs[0]까지만 접근이 가능하다.
그런데 있지도 않은 stairs[1]에 접근하려고 하니 IndexError가 떴던 것

IndexError가 난 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import collections

n = int(input())
stairs = [-1]
for _ in range(n):
    stairs.append(int(input()))

dp = collections.defaultdict(int)
dp[1] = stairs[1]
dp[2] = stairs[1]+stairs[2]
dp[3] = max(stairs[1] + stairs[3], stairs[2]+stairs[3])

for i in range(4, n+1):
    dp[i] = max(dp[i-2]+stairs[i], dp[i-3]+stairs[i-1]+stairs[i])

print(dp[n])

IndexError 해결방법1

staris 도 defaultdict(int)로 선언해준다.

• 메모리 32692KB
• 시간 112ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import collections

n = int(input())
stairs = collections.defaultdict(int)
for i in range(1, n+1):
    stairs[i] = int(input())

dp = collections.defaultdict(int)
dp[1] = stairs[1]
dp[2] = stairs[1]+stairs[2]
dp[3] = max(stairs[1] + stairs[3], stairs[2]+stairs[3])

for i in range(4, n+1):
    dp[i] = max(dp[i-2]+stairs[i], dp[i-3]+stairs[i-1]+stairs[i])

print(dp[n])

IndexError 해결 방법2

if문으로 n이 0일 때와 dp 초기화에 해당하는 n이 1,2,3 일 때를 모두 if문으로 예외처리해준다.

• 메모리 32716KB
• 시간 108ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import collections

n = int(input())
stairs = [-1]
for _ in range(n):
    stairs.append(int(input()))

dp = collections.defaultdict(int)
if n == 0:
    print(0)
elif n == 1:
    print(stairs[1])
elif n == 2:
    print(stairs[1]+stairs[2])
elif n == 3:
    print(max(stairs[1] + stairs[3], stairs[2]+stairs[3]))
else:
    dp[1] = stairs[1]
    dp[2] = stairs[1]+stairs[2]
    dp[3] = max(stairs[1] + stairs[3], stairs[2]+stairs[3])

    for i in range(4, n+1):
        dp[i] = max(dp[i-2]+stairs[i], dp[i-3]+stairs[i-1]+stairs[i])

    print(dp[n])

정리 이유

프로그래밍 문제를 해결하기 위해 필요해서 Node() 클래스를 직접 정의해서 사용하였는데, 그 노드가 담긴 리스트를 정렬하려니,
그냥 sorted()를 쓰면

TypeError: ‘<’ not supported between instances of ‘Node’ and ‘Node’

와 같은 에러 메세지가 뜬다.

Node 클래스는 직접 만든 클래스라 sorted()의 내부 함수로는 어떤 기준으로 정렬해야할 지 알 수 없기 때문이다.
그래서 검색해보니, sorted()의 key 매개변수를 이 순서를 지정해 줄 수 있다는 사실을 알게 되어 정리해둔다.

sorted() 정렬 순서 지정하기

sorted(list)

• 오른차순으로 정렬된다.

sorted(list, reversed=True)

• 내림차순으로 정렬된다.

sorted(list, key=function())

• function()내용에 따라 오름차순으로 정렬된다.

sorted(list, reversed=True, key=function())

• fucnction()내용에 따라 내림차순으로 정렬된다.

정리 이유

파이썬 알고리즘 인터뷰 p638 의 카데인 알고리즘을 보는데
best_sum = -sys.maxsize 라고 선언하는 부분을 처음봐서
sys.maxsize에 대해 찾아보고 정리하였다.

sys.maxsize

• python3에서 Py_ssize_t 타입이 가질 수 있는 가장 큰 정수를 리턴하는 것이다.
• 즉, 이 sys.maxsize 크기의 List가 python3에서 만들 수 있는 최대 크기의 List이다.
• 일반적으로 32비트 플랫폼에서는 2^31 - 1 이고
• 64비트 플랫폼에서는 2^63 - 1 이다.

python3에서 int 자료형 정수 최대값, 최소값

• maximum = sys.maxsize
• minimum = -(sys.maxsize+1)

float(‘inf’) 와의 차이

파이썬에서 코딩할 때 아주 큰 값을 잡기 위해 float(‘inf’)를 자주 사용하는데, 이는 float 자료형의 양의 무한대값이다.
무한대 값과 Py_ssize_t 타입이 가질 수 있는 가장 큰 정수 값은 서로 의미하는 것이 다르다.

float 자료형의 양의 무한대 값과 음의 무한대 값

maximum = float(‘inf’)
minimum = float(‘-inf’)

int(float(‘inf’)) 혹은 int(float(‘-inf’)) 는 불가하다.

OverflowError : cannot convert to float infinity to integer

위와 같은 오류 메세지가 뜬다.

참고 문서

https://docs.python.org/3/library/sys.html#sys.maxsize
An integer giving the maximum value a variable of type Py_ssize_t can take.
It’s usually
2^31 - 1 on a 32-bit platform
2^63 - 1 on a 64-bit platform.

https://www.python.org/dev/peps/pep-0353/
PEP 353 – Using ssize_t as the index type

typing 모듈

문제 상황

리트 코드에서 푼 문제를 VSCode에 옮겨 놓으니

1

def maxSubArray(self, nums: ***List***[int]) -> int:

타입 힌트를 주는 List에 밑줄이 생기며 아래와 같은 오류 메세지가 나왔다.

“List” is not defined

문제 해결

1

from typing import List

를 import 해줌으로써 해결했다.

문제 원인

리트 코드에서는

1

from typing import *

를 기본적으로 import 처리해두기 때문에 별도로 import하지 않고 사용했지만,
VSCode에서는 별도로 imort가 필요했던 것이다.

그 외 리트코드에서 기본적으로 import 처리해 둔 모듈

• import collections
• import heapq
• import functools
• import itertools
• import re
• import sys
• import math
• import bisect
• from typing import *

참고 문서

https://docs.python.org/3/library/typing.html
https://www.python.org/dev/peps/pep-0484/

TIL/python
https://hyunjungc-dev.github.io/2021/04/01/collections-%EB%AA%A8%EB%93%88%EC%9D%98-Counter-%ED%81%B4%EB%9E%98%EC%8A%A4/

이 문제의 경우, 프로그래머스의 다른 사람의 풀이를 보니 collections 모듈의 Counter()를 이용하면, 더 쉽게 풀 수 있었다.
collections 모듈의 Counter()는 잘 몰라서 위의 TIL/python 카테고리 안에 공부해서 정리했다.

Programmers level 1

완주하지 못한 선수

participant 배열과 completion 배열의 관계를 생각해야한다.

1. participant 배열과 completion 배열의 관계

• participant에는 참여한 모든 선수들의 이름이 들어있고
• completion에는 완주한 선수들의 이름이 들어가 있다.
• 이때, 둘 배열의 길이차는 항상 1이다.

2. 완주 못한 선수는 항상 1명

• 각 배열을 순서대로 정렬했을 때, 일치하지 않는 인덱스의 선수가 완주하지 못한 선수가 된다.

sort를 이용

1
2
3
4
5
6
7

def solution(participant, completion):
    participant.sort()
    completion.sort()
     for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]

collection 모듈의 Counter()를 이용
프로그래머스 다른 사람의 풀이

1
2
3
4

import collections
def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

정리 이유

완주하지 못한 선수 문제 풀이에서 처음 본 모듈이기 때문에 익히고 잊지 않기 위해 정리해둔다.

Counter 클래스

• Counter 객체는 아이템에 대한 개수를 계산해 딕셔너리로 리턴한다.
• Counter 객체가 리턴하는 딕셔너리의
• 키에는 아이템의 값이
• 값에는 해당 아이템의 개수가 들어간다.

Counter 객체 사용

1
2
3
4

import collections
arr = [1,2,3,4,5,5,5,6,6]
cnt = collections.Counter(arr)
print(cnt)

위의 코드는 아래와 같은 Counter 객체를 출력한다.

Counter({5: 3, 6:2, 1: 1, 2: 1, 3: 1, 4: 1})
5가 3개, 6이 2개, 1이 1개, 3이 1개, 4가 1개로 개수가 많은 것부터 출력된다.

Counter 객체에서 가장 빈도수가 높은 요소를 추출하고 싶다면

most_common(1) 함수를 사용한다.

1

print(cnt.most_common(1))

위의 코드는 [(5,3)]와 같이 (가장 높은 빈도를 가지는 아이템, 그 아이템의 개수)가 튜플로 묶여 출력된다.

가장 빈도가 높은 n개의 요소를 추출하고 싶다면

most_common(n) 함수를 사용한다.

1

print(cnt.most_common(2))

위의 코드는 [(5,3), (6,2)]를 출력한다.

most_common() 안에 매개변수를 넣지 않는다면

1

print(cnt.most_common())

[(5, 3), (6, 2), (1, 1), (2, 1), (3, 1), (4, 1)]와 같이 모든 요소가 출력된다.

dictionary와 관련된 특수한 형태의 컨테이너 자료형

• collections.defaultdict 클래스를 가지는 defaultdict 객체
• collections.Counter 클래스를 가지는 Counter 객체
• collections.OrderdDict 클래스를 가지는 OrderedDict 객체

참고 자료

• 파이썬 알고리즘 인터뷰 p132-p134

정리이유

문자열을 다루는 문제에서 자주 쓰이기에 익혀두기 위해 정리해둔다.

정규표현식 문자열 치환

re.sub(정규 표현식, 대상 문자열, 치환 문자)

• 정규 표현식 : 검색 패턴을 지정
• 대상 문자열 : 검색 대상이 되는 문자열
• 치환 문자 : 변경하고 싶은 문자

메타 문자

문자 클래스 []

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment

[1차] 캐시

캐시(페이지) 교체 알고리즘 : LRU(Least Recently User) 문제이다.

1. 캐시 Miss!

• 데이터가 들어왔을 때, 그 데이터가 캐시에 없다면, 캐시 Miss!이다.
• 이 경우, 가장 오래 전에 사용된 데이터를 제거하고 새로 들어온 데이터를 삽입한다.

2. 캐시 Hit!

• 데이터가 들어왔을 때, 그 데이터가 캐시에 있다면, 캐시 Hit!이다.
• 이 경우, 해당 데이터를 꺼내 캐시의 맨 뒤에 넣어준다.
• = 가장 최근에 쓰였을 수록 맨 뒤에 있다.
• = 가장 나중에 쓰였을수록 맨 앞에 있다.

queue를 이용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def solution(cacheSize, cities):
    cache = []
    running_time = 0
    cities = list(map(lambda city: city.lower(), cities))
    for ref in cities:
        if cacheSize == 0: # cacheSize가 0인 경우 예외 처리
            return len(cities)*5
        if not ref in cache:
            if len(cache) < cacheSize:
                cache.append(ref)
            else:
                cache.pop(0)
                cache.append(ref)
            running_time += 5

        else:
            cache.pop(cache.index(ref))
            cache.append(ref)
            running_time += 1

    return running_time

주의

• cacheSize가 0인 경우 예외 처리

  • if cacheSize == 0인 경우, 모든 경우 Miss!가 난다.

• cities의 이름이 대소문자가 섞여나오는데 구분하지 않음

  • list(map(lambda city: city.lower(), cities)) 이용하여 모든 문자를 대문자 혹은 소문자로 변경한다.