코딩 테스트 대비를 위해 알아두면 좋은 팁

스택(Stack)과 큐(Queue)

스택과 큐란 무엇인가?

스택 : 후입 선출 (LIFO), 파이썬의 리스트로 커버 가능

큐 : 선입 선출 (FIFO), 데크(deque)를 이용해야 좋은 성능

(리스트는 동적 배열로 구현되어 있어 큐의 연산을 수행하기에는 효율적이지 않다)

 

---

데크(Deque)

 

데크란 무엇인가?

 

데크는 양쪽에서 삭제와 삽입을 모두 처리할 수 있는 자료구조로, 스택과 큐의 특징을 모두 갖는다. 

구현은 배열이나 연결 리스트 모두 가능하다.

파이썬에서는 collections 모듈에서 deque로 지원한다.

 

list = [1,2,3,4]
deque = collections.deque(list,maxlen=10) // 최대 길이를 지정할 수 있다.
deque.pop()
deque.append()
deque.popleft()
deque.appendleft()

 

---

정렬

 

정렬에는 어떤 종류가 있는가?




이미지 출처: https://gyoogle.dev/blog/algorithm/

거품 정렬 (bubble sort)

선택 정렬 (Selection sort)

삽입 정렬 (Insertion sort)

퀵소트 (Quick sort)

list = [2,3,1,5,7,6]
list.sort() // [1,2,3,5,6,7]
list.sort(reverse = True) // [7,6,5,3,2,1]
sorted(list) // [1,2,3,5,6,7]

- list.sort : 저장 O, 반환값 X

- sorted(list) : 저장 X, 반환값 O

 

list.sort(key = lambda x: (x[0],x[1])) // 첫 글자를 기준으로, 두 번째 글자를 기준으로 정렬

 

---

for else문

 

for i in range(10):
	if i==10:
    		answer = true
    		break
else:
	answer = false

 

---

순열조합

파이썬에서는 itertools라는 편리한 라이브러리를 제공한다

for k in range(3):
	for comb in combinations([1,2,3,4,5],k):
    		print(comb)

// [1],[2],[3],[4],[5],[1,2],[1,3],[1,4],...

 

itertools.combinations

itertools.permutations

 

---

카운터

'AAABBBBCCCCCDD'와 'AABBCCCCCD' 중 같은 갯수를 갖는 알파벳은?

 

 

 

파이썬은 collections.Couter라는 라이브러리를 제공한다 (C 대문자 주의)

s = 'AAAABBBCCCCCDD'
collections.Counter(s) // Counter{ 'A':4, 'B':3, 'C':5, 'D':2 }

추가 메서드,

- most_common(n) : 가장 큰 n개를 리스트에 담아 반환

- substract() : 다른 카운터 객체 또는 문자열과 뺄셈

 

---

파이썬의 삼항 연산자 유사 기능

A는 B가 집에 있으면 1이고 집에 없으면 2이다. 파이썬 코드 한 줄로 표현해보시오.

A = 1 if B in home else 2

 

 

---

리스트 컴프리헨션

1~10 중 홀수들에 대해 그 값의 2배를 갖는 리스트를 파이썬 코드 한 줄로 표현하시오.

 

 

 

 

[ n*2 for n in range(1,10+1) if n%2==1 ]