5주차 코딩테스트 요점(기본 문제, 자료구조)

1. sys.stdin.readline()

sys 라이브러리의 sys.stdin.readline().strip()을 통해서 한줄한줄 입력을 받아 올 수 있습니다. input()보다 실행시간이 빨라 시간제한이 있는 코딩테스트 문제에선 꼭 사용애햐 하는거 같습니다. 

strip() 을 하는 이유는 입력받을때 '\n'인 개행문자를 같이 받기 때문에 한줄씩 받으려면 사용해줘야 합니다. 

strip()은 불피요한 개행문자와 공백문자를 제거해줍니다. 

 

2. pop()

pop()을 하면 리스트기준 제일 뒤에 있는 데이터를 뽑아 리턴합니다. 하지만 pop(0)와 같이 인덱스를 넣어주면 리스트 처음 데이터를 뽑아 리턴합니다. 

 

3. heapq 라이브러리(최소 힙 라이브러리)

3-1. 최소 힙

import heapq를 하면 사용할 수 있으며 값이 작은 값부터 처리하기 위해 사용하는 라이브러리 입니다. 

위 사진과 같이 함수를 사용하면 손 쉽게 최소 힙을 구현할 수 있습니다. 

 

3-2. 최대 힙

위 코드와 같이 사용한다면 최대 힙 또한 구현할 수 있습니다. 원하는 데이터에 음수를  적용하여 삽입후 반환 할 때는 음수를 적용하여 원상태로 반환 할 수 있습니다. 

4. sort()

위 코드와 같이 sort() 함수의 key 옵션을 주어서 원하는 형식으로 정렬 할 수 있습니다. 또한 정렬의 1순위 2순위 같이 여러개 적용도 가능합니다. 

 

5. print()함수 내 언패킹

print 함수 내 *xy 언패킹하여 print문 조금 사용하는 방식입니다. 하지만 둘다 O(n) 방식이여서 실행 시간은 별로  차이나지 않지만 print문 반복사용으로 인한 오버헤드가 발생할 수 있어 알아두면 좋을거 같습니다. 

 

6. 최대공약수 최소공배수

최대공약수는 math.gcd(a, b)로 쉽게 구할 수 있으며 최소공배수는 a*b/ 최대공약수 로 쉽게 구할 수 있습니다. 

a*b/ 최대공약수는 유클리드 알고리즘입니다. 

(for문으로 풀려고 고생하다 좋은 정보를 알았습니다)

 

7. deque 라이브러

from collections import deque 을 한 후 사영할 수 있으며 사용 가능한 함수는 다음과 같습니다. 

위 사진과 같이 사용할 수 있습니다. 

큐와 덱 문제는 위 라이브러이의 함수로 쉽게 풀 수 있다는 사실을 다 풀고 알았습니다. 

 

7-1 헷갈릴만한 함수

extendleft 함수는 원하는 데이터를 왼쪽에서부터 반대로 삽입 합니다.

 

rotate 함수는 원하는 방향으로 미는 함수입니다. 양수는 오른쪽으로 음수는 왼쪽으로 밉니다. 

 

8. print() 함수 문자열 포매팅과 리스트 처리

[1, 2, 3, 5, 8] 이런식의 출력을 공백 없이 [1,2,3,5,8]로 출력하는 방법입니다. deque 타입에 정수가 들어있는 number데이터에 map함수를 적용해 str문자열로 변경시킨 후 ,f로 조인을 합니다. 그러하면 1,2,3,5,8이 나옵니다. 그 후 f-string 으로  밖에 []대괄호를 씌우는 방법입니다.

 

9. json 함수

import json으로 사용할 수 있으며 문자열인 '[1,2,3,4]'를 [1, 2, 3, 4] 로 변환 하는 json.loads함수가 있습니다. json 형태의 문자열을 파이썬 객체로 변환합니다. 입력 형태에 맞게끔 반환 해줍니다. (dict 형식을 넣으면 dict형식으로 나옵니다) 

반대로 dumps를 하면 파이썬 객체를 json형식으로 변경해줍니다. 

 

10. 소수 찾기

위 코드는 자연수 a와 b가 주어지면 그 사이에 존재하는 모든 소수를 출력하는 문제입니다. 

저 코드에서 중요한 점은 두번째 for문에 범위를 math.sqrt(i)+1 로 주었다는 점입니다. 소수가 아닌 숫자는 1과 자신이 아닌 수로 나누어지는 수가 있는 수입니다. 예를 들어 8은 2*4, 4*2 로 나누어 집니다. 여기서 요점은 사실 2*4가 가능하면 4*2는 당연히 가능하다는 것입니다. 이를 이용해 판별하는 수에 루트를 씌어(math.sqrt) 숫자에 절반만 판단해도 된가는 점이지요. 이렇게 실행시간을 대폭 단축 시킬 수 있습니다(저 방식을 사용하지 않으면 시간 초과가 나옵니다). 

또한 1은 모든 숫자를 나눌 수 있어 a가 1이면 2부터 시작하게 +1 해주었습니다. 이 방식이 싫다면 마지막 print()문의 if 조건에 and i != 1 을 추가해도 됩니다. 하지만 이 방법보단 위 코드 방법이 실행시간이 미세하게 빨랐습니다. 

 

11. 튜플 언팩킹 결과

result 는 튜플이 들어있는 리스트 입니다. 즉 [(1,2),(1,3)] 이런식으로 들어있습니다. 그중 for문으로 한줄씩 가져오면 r은 (1,2)와 같은 튜플이 가져와 집니다. 이것을 언패킹을 하여 print()하면 1 2와 같은 식으로 출력 됩니다. 

 

12. itertools 라이브러리(중요!)

from itertools import * 로 사용할 수 있습니다. 여러 경우의 수와 수열을 구할때 매우 유요하여 코딩테스트에 많이 나온다고 합니다. 함수는 다음과 같습니다.