태야

재귀 호출은 함수가 자기 자신을 다시 호출하는 것을 뜻한다. 알고리즘 공부에 있어서 중요한 개념이므로 확실하게 공부해야 한다. 재귀 호출에서 중요한 것이 반드시 '종료 조건'이 있어야 한다는 것이다. 만약 종료 조건이 없으면 무한루프에 빠지기 때문이다.

재귀 호출의 일반적인 형태

def func(입력):
	if 입력 값이 충분히 작으면: #종료 조건
    	return 결과
    ...
    func(더 작은 입력 값)  	# 더 작은 값으로 재귀 호출
    ...
    return 결과

재귀 호출의 세 가지 요건

1. 함수 안에서 자기 자신을 다시 호출한다.
2. 재귀 호출할 때 인자로 주어지는 입력 크기가 작아진다.
3. 특정 종료 조건이 만족되면 재귀 호출을 종료한다. 즉, 종료 조건이 있어야 한다.

[예 제]

1. 1부터 n까지 더하기

def call_sum(n):
    if n <= 1:
        return n

    return n + call_sum(n-1)


print(call_sum(100))

함수 안에서 자기 자신을 계속해서 호출하는 방식으로 1부터 n까지 합을 구한다. 

2. 팩토리얼 구하기

def fact(n):
    if (n <= 1):
        return 1

    return n * fact(n-1)


print(fact(1))  # 1
print(fact(10))  # 10! = 3628800

종료 조건으로 n이 1과 같거나 작아지면 1을 리턴하게 해 마지막으로 1이 곱해지면서 결과를 리턴한다.

3. 최댓값 찾기

def find_max(nums, n):
    if n == 1:
        return nums[0]

    max_num = find_max(nums, n-1)

    if (max_num > nums[n-1]):
        return max_num
    else:
        return nums[n-1]


a = [17, 92, 18, 24, 35]
print(find_max(a, len(a)))  # 92

사실 리스트에서 최댓값, 최솟값을 구할 때 max(), min() 함수를 사용하면 쉽게 구할 수 있다.

<내 코드>

import sys
from collections import deque

n = int(sys.stdin.readline())
deque = deque()


def push(queque, x):
    deque.append(x)


def pop(deque):
    if(not deque):
        return -1
    else:
        return deque.popleft()


def size():
    return len(deque)


def empty():
    if(not deque):
        return 1
    else:
        return 0


def front():
    if(not deque):
        return -1
    else:
        return deque[0]


def back():
    if(not deque):
        return -1
    else:
        return deque[-1]


for i in range(n):
    oper = sys.stdin.readline().split()

    if (oper[0] == "push"):
        push(deque, oper[1])
    elif(oper[0] == "pop"):
        print(pop(deque))
    elif(oper[0] == "size"):
        print(size())
    elif(oper[0] == "empty"):
        print(empty())
    elif(oper[0] == "front"):
        print(front())
    elif(oper[0] == "back"):
        print(back())

이 문제는 시간 복잡도가 O(1)이 되어야 하는데, 일반적인 리스트의 pop() 함수를 사용하면 첫 번째 요소를 pop 할 때는 O(n)의 시간이 소요된다. 그래서 collections의 deque를 사용했다. pop 부분에서 popleft를 이용해 시간을 단축시킬 수 있다. deque는 스택과 큐를 합친 자료구조이다.

<내 코드>

n = int(input())
words = set()
for i in range(n):
    words.add(input())

sortWords = sorted(words, key=lambda x: (len(x), x))

for i in sortWords:
    print(i)

단어의 중복을 제거하기 위해 set() 집합을 사용했다. 입력값으로 들어오는 문자열들을 집합에 넣고, sorted 함수를 이용해 각 문자열을 1차로 길이에 따라 정렬하고, 길이가 같다면 2차로 사전의 오름차순으로 정렬하게 코드를 작성했다.

<내 코드>

n = int(input())
dots = []
for i in range(n):
    dots.append(list(map(int, input().split())))

dots = sorted(dots, key=lambda x: (x[1], x[0]))

for i in dots:
    print(*i)

 알고리즘, 자료구조 - 순차 탐색(선형 탐색) 

순차 탐색이란?

리스트 또는 배열 안에 있는 첫 번째 자료부터 하나씩 비교하면서 원하는 데이터를 찾아가는 알고리즘이다. 데이터를 따로 조작할 필요가 없어 단순하지만 비효율적이라는 단점을 지니고 있다. 추가로 순차 탐색은 단방향으로 탐색을 수행하기 때문에 선형 탐색(Linear Search)라고도 부른다.

순차 탐색은 최악의 경우에 최대 n번의 비교를 필요로 하기에 시간 복잡도는 O(n)이 된다.

이는 데이터가 n개가 되면 그에 따른 연산 수도 n개를 따라가기 때문에 자료수가 많아질수록 연산의 속도가 느리다는 단점이 있다.

예제

# 리스트에서 특정 숫자의 위치 찾기

def search_num(a, x):
	n = len(a)
    for i in range(0, n): #리스트 a의 모든 값에 대해 반복
    	if x == a[i] : 	# 찾는 숫자와 값이 일치하면
        	return i	# 인덱스 값 반환
    
    return -1
    
a = [17, 92, 18, 33, 58]
print(search_num(a, 18)) # 2 출력
print(search_num(a, 900)) # -1 출력(해당 값이 없기에)

# 학생 번호를 입력시 해당하는 학생의 이름을 반환
def find_student(number, stuNo, stuName):
    num = len(stuNo)
    for i in range(0, num):
        if(stuNo[i] == number):
            return stuName[i]

    return "해당 학생은 없습니다."


stu_no = [39, 14, 67, 103]
stu_name = ["Justin", "John", "Mike", "Summer"]

print(find_student(39, stu_no, stu_name)) #출력 - "Justin"