알고리즘 스킬

알고리즘 스킬

1. 적은 한정된 범위의 인덱스를 다룰 때는 미리 배열을 만들어 보라

이코테 315p 그리디 기출 5번 볼링공 고르기
Ex) 리스트에서 1~10 까지 등장하는 개수 세야 할 때
미리 arr = [0] * 11 한 뒤 숫자 별로 그냥 나오는대로 1씩 증가

2. 반복되는 심볼로 비교문 수행(경로탐색)할 때는 리스트에 저장하는 방식을 고려하자

이코테 110p 구현 예제 4-1 상하좌우
Ex) UDLR 문자 입력 시 이동방향 결정하는 경우 [‘U’, ‘D’, ‘L’, ‘R’]로 저장 후 꺼내 쓰기

3. 시간제한/메모리 제한을 고려해 데이터 수가 충분히 적다면 완전탐색을 고려해 보자

이코테 113p 구현 예제 4-2 시각
00:00:00 ~ N시:59:59 까지 3이 포함된 시각의 개수를 셀 때 총 시각의 수는 246060 = 10만개도 되지 않으므로 선형으로 하나씩 비교해도 1초 안에 해결이 가능하다.
제한시간 1초 기준
N의 범위가 500인 경우: O(N^3) 으로 해결 가능
N의 범위가 2,000인 경우 O(N^2)으로 해결 가능
N의 범위가 100,000인 경우 O(NlogN)으로 해결 가능
N의 범위가 10,000,000인 경우 O(N)으로 해결 가능
메모리 제한
메모리 제한 128~512MB 기준 리스트 크기 1,000만 단위 이상이면 잘못. 100만도 드뭄

4. 숫자 포함 여부를 비교해야 하는 경우 문자열 변환을 고려해 보라.

이코테 113p 구현 예제 4-2 시각
Ex) 03 25 49 (시간) 에서 3이 포함되는 경우를 찾는 경우 str(h) + str(m) + str(s) 해서
‘3’ in ‘032549’ 으로 비교

5. 알파벳 순서를 이용하는 경우는 아스키 코드를 사용하라

이코테 115p 실전 문제 1 왕실의 나이트
Ex) 소문자 알파벳을 인덱싱 하고 a를 1로 간주하려는 경우
ord(x) – ord(‘a’) + 1

6. 이동경로를 따지는 경우 방향 하나하나 정보를 리스트에 넣자

이코테 115p 실전 문제 1 왕실의 나이트
Ex) 나이트의 8자 움직임을 저장하는 경우
[(-2,-1), (-1,-2), (1,-2) ,(2, -1), (2,1), (1,2), (-1,2), (-2,1)]

7. 문자열 숫자, 알파벳, 대/소문자 확인 시에는 문자열 내장함수를 이용하자

이코테 322p Q.08 문자열 재정렬
https://codedragon.tistory.com/9884

• isalpha() – 알파벳인지 확인
• isdigit(), isdecimal() – 숫자인지 확인
• isalnum() – 알파벳 또는 숫자인지 확인
• index() – 문자 위치 알려주기
• count() – 문자
• “”join(리스트) – 문자열 합치기 – “”안에 들어가는게 구분자.

8. 방향벡터(x,y)를 이용할 때는 두 가지 변수로 나누어 생각하자

이코테 118p 실전문제 2 게임 개발
Ex) dx = [-1, 0, 1, 0] / dy = [0, 1, 0, -1] 로 두고 nx = x + dx[direction] 등으로 풀이

9. for i in range()는 다양한 옵션이 가능하다

이코테 515p A 07 럭키 스트레이트

• range(stop)
• range(start, stop)
• range(start, stop, step)

10. upper() , lower()은 알파벳 이외에 다른 것이 포함된 문자열에도 적용된다.

프로그래머스 Lv.1 카카오 2021 코테 – 신규 아이디 추천
...!@BaT#..y.abcdefghijklm.lower() ->...!@bat#..y.abcdefghijklm

11. 튜플을 요소로 갖는 리스트는 튜플의 1,2 번째 요소를 이용해 정렬이 가능하다.

프로그래머스 Lv.1 카카오 2019 코테 – 실패율
람다 사용법 튜플 정리하기
첫 번째 원소로 오름차순 정렬하기
v.sort(key = lambda x : x[0])
첫 번째 원소로 내림차순 정렬하기
v.sort(key=lambda x:-x[0])
첫 번째 원소로 오름차순 정렬 후 첫 번째 원소가 같은 경우 두 번째 원소로 오름차순 정렬하기
v.sort(key=lambda x:(x[0],x[1]))
n 번째 문자 기준으로 문자열 리스트 정렬하기
프로그래머스 Lv.1 문자열 내 마음대로 정렬하기
v.sort(key = lambda x : x[n])

12. 문자열을 문자별로 분리하려면 list()를 쓰면 된다.

프로그래머스 Lv.1 문자열 내림차순으로 배치하기
Ex) list("Zbcdefg") -> [‘Z’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’]
반대는 join()을 이용하면 된다.

13. sorted()를 쓰면 다양한 방법으로 정렬된 리스트를 반환할 수 있다.

프로그래머스 Lv.1 문자열 내림차순으로 배치하기
Sorted( ) 사용법
정렬된 리스트
sorted(기존 리스트)
딕셔너리 키 기준 정렬
sorted(딕셔너리.items())
딕셔너리 키 기준 정렬하고 키만 담아 반환
sorted(딕셔너리.keys() or sorted(딕셔너리)
딕셔너리 value 기준으로 정렬
sorted(딕셔너리.items(), key=operator.itemgetter(1))
sorted(딕셔너리.items(), key=lambda x: x[1])

14. 알파벳 ASCII 이용할 떄는 ord( ) / chr( )

프로그래머스 Lv.1 시저 암호
알파벳 -> 아스키
ord(s)
아스키 -> 알파벳
chr(n)

15. 실수 리스트의 총합을 구할 때는 sum( )

프로그래머스 Lv.1 약수의 합
Ex) sum([1, 2, 3]) -> 6

16. 최대공약수(GCD), 최소공배수(LCM)는 유클리드 호제법을 이용한다.

프로그래머스 Lv.1 최대공약수와 최소공배수
유클리드 호제법
N % M = R
N = M , M = R 관계를 반복해서 나머지 계산이 0이 되는 경우 그 때의 M이 GCD
LCD == (N * M) // GCD

모듈을 이용하면 2개 이상 수에 대해
math.gcd( ), math.lcm( ) 이용 가능하다.

17. 입력값이 복잡한 문자열인 경우 strip(), split(), replace() 을 적극적으로 이용하자

프로그래머스 Lv.2 카카오 2019 코테 튜플
Ex) s = "{{2},{2,1},{2,1,3},{2,1,3,4}}" -> [‘2’,’2,1’,’2,1,3’,’2,1,3,4’]
s = s.lstrip(‘{‘).rstrip(‘}’)
arr = list(list(s.split(‘},{‘))

18. 여러 개의 구분자로 split 하는 경우 re 모듈 정규식을 이용하자

프로그래머스 Lv.2 카카오 2020 인턴십 수식 최대화
re.split(‘[ | | ]’, string)
Ex) "100-200300-500+20" -> [100, 200, 300, 500, 20]
list(map(int, re.split(‘[ | + | - ]’, string)))

re.split(symbol, string, n)
n을 쓰면 원하는 횟수만큼만 자를 수 있다.

18. 소수인지 판별할 때는 약수의 중간 값이 \sqrt\mathbf{N}에 가까움을 이용하자

프로그래머스 Lv.1 소수 만들기
Ex) 8의 약수 1,2,4,8 에서 약수의 중간(2)은 \sqrt\mathbf{N}을 넘지 않는다.
따라서 IsPrime( )을 구현할 때는 i * i <= N 조건을 만족하는 경우만 반복하면 된다.
이 때 복잡도는 \sqrt\mathbf{N}이 된다.

19. 배열에서 순열/조합을 사용하는 경우는 itertools를 이용한다.

프로그래머스 Lv.1 소수 만들기
from itertools import comibations(permutaions, product) as cb(pt, pd)
combinations(리스트, 뽑는 수)
permutations(리스트, 뽑는 수)
product(리스트)
product(리스트)는 각 요소의 iterable한 값들로 데카르트 곱을 반환한다.
각 메소드는 튜플을 요소로 하는 객체를 반환한다.
사용할 때 이를 적절히 매핑/리스트화해서 이용하자.

20. 약수는 \sqrt\mathbf{N}을 기점으로 좌우 곱 대칭 관계에 있다.

프로그래머스 Lv.1 약수의 개수의 덧셈
\sqrt\mathbf{N}을 기점으로 대칭되기 때문에, 제곱수인 경우 약수의 개수가 홀수고, 아니라면 짝수이다.

21. 2진수, 8진수, 16진수 변환하는 방법

2진수: 0b~
8진수: 0o~
16진수: 0x~~~
숫자에서 다른 진수의 문자열로 변환하기

bin(42)
'0b101010'
oct(42)
'0o52'
hex(42)
'0x2a'
다른 진수의 문자열을 숫자형으로 변환하기
int('0b101010', 2)
42
int('0o52', 8)
42
int('0x2a', 16)
42

22. range() step 옵션으로 for문을 내림차순으로 사용할 수 있다.

프로그래머스 Lv.1 3진법 뒤집기
기본: for i in range(start, stop) -> start ~ stop -1 까지 반복
Step: for i in range(start, stop, step) -> start ~ stop -1 step 간격 반복
내림차순: for i in range(stop, start, -1) -> stop ~ start +1
범위에 신경을 써 주어야 함 start -1 을 입력해 주면 stop ~ start 까지 내림차순으로 반복
reversed(range(start, stop))
기존의 range( )를 뒤집음.

23. 문자열을 특정 길이까지 같은 문자로 채우는 경우 rjust( ), ljust( ), zfill( )을 사용한다.

프로그래머스 Lv.1 카카오 2018 비밀지도
val = "77".rjust(5, "0") -> 00077
rjust(길이, 문자) 길이가 될 때까지 왼쪽에 문자 추가
val = "222".ljust(5, "a") -> 222aa
ljust.(길이, 문자) 길이가 될 때까지 오른쪽에 문자 추가
val = "2".zfill(3) -> 002
zfill(길이) 길이가 될 때까지 왼쪽에 0 추가

24. 특정 조건일 때 특정 값을 적용하는 경우 dictionary를 사용하자.

프로그래머스 Lv.1 카카오 2018 [1차] 다트게임
Ex) bonus가 ‘S’인 경우는 1제곱, ‘D’인 경우는 2제곱, ‘T’인 경우는 3제곱을 해 준다.
bonus = {'S' : 1, 'D' : 2, 'T' : 3}
if (option in bonus):
value = value ** bonus[option]
옵션의 인덱스를 따로 찾을 필요 없이 key값으로 호출할 수 있다.

25. 배열의 정렬 상태를 유지하고 가장 작은/큰 값을 추출해 이용할 때는 힙을 사용하자

프로그래머스 Lv.2 더 맵게
import heapq as hq
hq.heapify(list)
hq.heappush(heap,item)
hq.heappop(heap)
힙 모듈
Max Heap을 사용하려면 list의 item을 음수로 바꿔준 뒤 heap을 구성하면 된다.
for item in list:
hq.heappush(heap, -item)

26. GCD는 재귀로 쉽게 구현할 수 있다.

프로그래머스 Lv.2 N개의 최소공배수
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)

27. 여러 개의 최소공배수는 각 LCM을 누적 반복하면 구할 수 있다.

프로그래머스 Lv.2 N개의 최소공배수
리스트의 앞 두 수의 최소공배수를 구한 뒤, 구한 최소공배수와 다음 수와의 최소공배수로 갱신한다.

28. 하노이 탑은 재귀함수로 구현할 수 있다.

프로그래머스 Lv.2 하노이의 탑
1. n == 1이 되면 1번에서 3번으로 옮김
2. 1번에서 n-1 탑을 2번에 옮기는 재귀 실행
3. 1번의 n번째 판을 3번에 옮김
4. 2번의 n-1 탑을 3번에 옮기는 재귀 실행

29. split( )을 사용하면 공백이 중복되는 경우 공백 개수를 무시하고 없앤다.

프로그래머스 Lv.2 JadenCase 문자열 만들기
공백 한 개 만을 기준으로 split하려면 split(‘ ‘)을 사용해야 한다.

30. caplitalize( )는 첫 번째 문자만 대문자화 하고, 뒤는 소문자화 한다.

프로그래머스 Lv.2 JadenCase 문자열 만들기
“aBCdEfG”.capitalize()
“Abcdefg”

31. 포함 여부를 확인하는 문제는 해시테이블을 이용한다

프로그래머스 Lv.2 전화번호 목록
딕셔너리는 in 함수의 복잡도가 O(1)이므로 딕셔너리로 포함여부를 찾는 것이 좋다.

32. 문제를 나눌 수 있고 중복연산이 필요한 경우는 다이나믹 프로그래밍을 고려하라.

프로그래머스 Lv.2 가장 큰 정사각형 찾기
DP 테이블을 만들어 메모이제이션을 한다.
1. 점화식을 이용해 답을 구하는 경우는 연산에 필요한 만큼 초기화된(0) 배열 생성
2. 이미 문제에 리스트가 있는 경우는 최종값을 구할 수 있도록 내부 요소 변경

33. 슬라이싱을 할 때 끝 인덱스가 마지막을 넘어도 자동으로 마지막 인덱스까지 자른다.

프로그래머스 Lv.2 가장 큰 수
temp = ‘abcd’
print(temp[:1000])

abcd
lambda 정렬 방법
1. 길이 순 정렬
sort(key = lambda x : len(x))
2. 기존 값에 변화를 준 뒤 그 기준에 따라 정렬 (ex: 일의자리 순)
sort(key = lambda x : x % 10)

34. for 문에서 Key 변수는 while 문과 달리 n-1로 종료된다.

프로그래머스 Lv.2 괄호 회전하기
for i in range(n):
반복문을 끝까지 순회한 뒤 i는 n-1이 됨.

35. 두 리스트의 겹치는 요소를 찾을 때는 집합과 딕셔너리를 이용하자

프로그래머스 Lv.2 카카오 2018 [1차] 뉴스 클러스터링
딕셔너리의 in 함수가 O(1) 임을 이용한다.
두 리스트 A와 B가 있는 경우
A_set = list(set(A))
for v in B:
B_dic[v] = 1
A_set[i] in B_dic
조건을 이용하여 ANB(교집합) 리스트에 append
중복 포함을 허용하는 경우는 A_dic, B_dic의 value를 증가시켜
min(A_dic[v], B_dic[v])
만큼 ANB에 v를 append하면 된다.

36. 재귀함수를 사용하면 반드시 Recursion limit을 설정하자

이코테 DFS BFS 미로탈출
import sys
sys.setrecursionlimit(10**7)
재귀함수를 사용하는 경우 이 옵션을 써야 에러를 피할 수 있다.

2023.05.08(월)
프로그래머스 1레벨부터 파이썬 풀이 다시 시작

37. set 메서드

프로그래머스 Lv.1 약수의 합
set( ) 선언, set([1,3,5,7])
리스트를 집합으로 변환 가능 -> 중복요소 제거
in – ele in s – bool 값 반환
update – 여러 요소 전달 s.update([1,3,4])
remove – 제거 – 없으면 오류 발생
discard – 제거 – 없어도 오류 발생 x
| - 합집합 , & - 교집합, - - 차집합, ^ - 대칭차집합

38. range( ) 는 범위의 시작과 끝이 같으면 종료된다.

-> range(1, 1)
반복문에 넣으면 동작하지 않음.

39. 문자열을 list( ) 로 감싸면 문자별 요소로 리스트 저장된다.

프로그래머스 Lv.1 자릿수 더하기
list(“abc”) -> [‘a’,’b’,’c’]

40. 문자열 메서드는 기존 문자열 변환이 아니라 새 문자열을 반환한다.

프로그래머스 Lv.1 문자열 내 p와 y의 개수
a = s.lower()
a와 s는 다른 문자열

41. int(문자열) 을 수행하면 문자열을 그대로 정수로 바꾼 결과를 반환한다.

프로그래머스 Lv.1 문자열을 정수로 바꾸기
val = int(“1253”)
val == 1253

42. find( ) 함수와 index( ) 함수의 차이

프로그래머스 Lv.1 추억 점수
find( )
는 문자열에서 사용 가능하고 찾는 문자가 없으면 -1을 반환한다.
index( )
는 리스트와 튜플에서 사용 가능하고 찾는 문자가 없으면 오류를 발생시킨다.