내일배움캠프 TIL (221124): 소수 판별하기, 링크드리스트 구현하기

Jiumn·2022년 11월 24일

[스파르타코딩클럽] 내일배움캠프 개발일지

목록 보기

10/108

오늘 한 일

알고리즘 실시간 강의 2일차였다. 링크드리스트의 정의와 구현하는 방법에 대해 배웠다.
링크드리스트의 개념을 이해하고 클래스로 구현하는 것까지는 간단(?)한 편이었으나, 원하는 위치에 노드를 추가하고, 삭제하는 것이 이해하는 것이 쉽지 않았다. 아래에 코드로 정리해봤다.

소수 판별하기

어제 공부한 파이썬 알고리즘 문제 다시 한번 정리...

Q. 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.

원래 배열의 형태로 반환해야 되는 문제인데,
우선은 그 전에 어떤 수가 소수인지 알아내는 방법부터 찾아봤다.

소수는 1과 자신 외에는 나눠지지 않는 수다.
그러므로 해당 수를 n이라고 할 때, 2부터 n-1 까지를 n에 나눠봤을 때
나머지가 0이면 소수가 아니고, 나머지가 0이 아니어야 소수다.

for range 반복문에 넣어서 반복문을 돌리고, if 조건문으로 분기하는 함수를 만들어준다.

[나의 답안]

def isPrime(n):
    for num in range (2, n): # 2부터 n-1일까지 반복해서 숫자를 하나씩 꺼내준다.
        if n % num == 0:
            return print('소수가 아니다')
        else:
            return print('소수다')

isPrime(n)

당연히 한번에 결과가 나올 리가 없다...! (해탈)
if 문이 함수 안에 들어갔기 때문에 return 값을 반환할 때 else 없이 들여쓰기를 주의해서 해줘야 한다. (역시나 기초적인 실수)

[모범 답안]

def is_prime(n):
    for num in range (2, n): # 2부터 n-1일까지 반복해서 숫자를 하나씩 꺼내준다.
        if n % num == 0:
            return print('소수가 아니다')
    return print('소수다')

is_prime(4)

이때, 알고리즘의 성능을 확인해보면 N만큼 확인해야 하기 때문에 시간 복잡도가 O(N)라고 할 수 있다. 이 알고리즘을 개선하기 위한 방법은 어떤 게 있을까?

약수의 성질을 이용하면 된다.

소수는 '해당 수의 제곱근에서 그 이하의 모든 수를 나눠봤을 때 나눠지지 않으면 소수'라는 글을 봤는데 왜 제곱근이지...? 라는 의문이 가시지 않았다.

그 의문을 이해하게 만들어준 한 영상!

*참고 영상: [이것이 코딩 테스트다 with Python] 37강 소수 판별 알고리즘

약수는 대칭의 성질을 가지고 있어서 가운데를 기준으로 나눠 그 이하의 수를 나눠봐도 소수인지 알 수가 있다.

[모범 답안]

import math

def is_prime(x):
	for i in range(2, int(math.sqrt(x)) +1):
    	if x % i == 0:
        return False
    return True

파이썬 중첩 for문

그렇다면 특정 정수 이하의 소수의 집합은 어떻게 구할 수 있을까?

[답안 예시] (중첩 for문이 있어서 효율이 좋은 알고리즘은 아니라고 한다.)

input = 20

def find_prime_list_under_number(number):
    prime_list = []
    for n in range(2, number + 1):
        for i in range(2, n):
            if n % i == 0:
                break
        else:
            prime_list.append(n)

    return prime_list


result = find_prime_list_under_number(input)
print(result)

이 답안에는 중첩 for문이 포함되는데, 어떻게 동작하는지 이해가 가지 않았다.
그래서 중첩 for문부터 이해해야겠다 싶어 유튜브를 찾아보다가 다음 영상을 발견했다.

참고 영상: 파이썬 기초 강의 [26강 중첩 for문]

2개의 주사위를 돌릴 때 합계 구하기, 구구단 구하기와 같은 간단한 예시들이 있어서 드디어 중첩 for문을 이해할 수 있었다. ㅠㅠ
(간단하게 설명하자면 첫 번째 for문이 1번 수행할 때, 두 번째 for문은 n번 수행하는 방식.)

클래스, 링크드 리스트(linked list) 만들기

오늘의 헬게이트. 링크드 리스트...!

파이썬에는 삽입과 삭제가 쉬운 배열(array)보다 쉬운 자료구조인 링크드 리스트라는 것이 존재한다.

클래스로 링크드 리스트를 만들고, 원하는 곳에 삽입/삭제하는 코드를 구현해보자.

# node를 클래스로 만들어주기
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# 링크드리스트를 클래스로 만들어주기
class LinkedList:
	# head 생성
    def __init__(self, value):
        self.head = Node(value)

# 링크드리스트 맨 끝에 node 추가하기
    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)
        
# 모든 노드 출력하기
    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

그중에서도 가장 헬이었던...
원하는 노드 가져오기, 그리고 중간에 노드 추가 또는 삭제하기

# 원하는 노드를 가져오기
    def get_node(self, index):
        # node를 head부터 쭉 돌면서 index를 찾아야 함 (이하 전체 코드)
        # node를 head로 지정
        node = self.head
        # 한번 이동할 때마다 횟수를 세어줌 = index
        count = 0
        # 노드 돌기 시작 (반복문) - 찾으려는 인덱스가 같거나 커질 때까지 계속 돌아야 함
        while count < index:
        # 노드를 계속 다음 노드로 옮겨줌
            node = node.next
        # 노드를 다음 노드로 옮길 때마다 +1
            count += 1
        # 내가 찾으려는 인덱스의 노드 반환
        return node

    # 중간에 새로운 노드 추가 ( a - b - c 라는 링크드리스트의 a - b 사이에 d를 추가하는 경우)
    # 1. a를 index로 지정
    # 2. b를 next_node로 지정
    # 3. d를 new_node로 지정
    # 4. a의 다음 노드를 d로 저장: index.next = new_node
    # 5. d의 다음 노드를 b로 저장: new_node.next = next_node
    def add_node(self, index, value):
        # 새로운 노드 생성
        new_node = Node(value)

        # index가 0일 때 예외 처리 (index -1 = -1이 되기 때문)
        if index == 0:
            # self.head = new_node 로 지정하면 안 됨 / 이전에 있던 head node가 사라짐
            # 원래 head 였던 노드를 새 노드의 next로 지정
            new_node.next = self.head
            # head를 new_node로 변경
            self.head = new_node

        # 클래스 내부에 있는 get_node() 함수 호출 / index번째 노드를 가져와서 node에 저장
        node = self.get_node(index - 1)
        # 새로운 노드는 현재 노드(node)의 다음 것
        next_node = node.next
        # 노드(node)의 다음은 new_node
        node.next = new_node
        # new_node의 다음은 next_node
        new_node.next = next_node

여기서 중요한 건 index = 0 일 때 예외 처리를 잊으면 안된다는 것.

# 원하는 위치의 노드를 삭제
    def delete_node(self, index):
        # head를 제거하고 싶을 때
        if index == 0:
            # head 다음의 node를 head로 지정
            self.head = self.head.next
            return

        # 원하는 위치의 node를 가져온다
        node = self.get_node(index - 1)
        # 원하는 위치의 node 다음 다음의 node를 연결
        node.next = node.next.next

linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)

# 현재 상태: [5] -> [12] -> [8]
# 목표: [5] -> [6] -> [12] -> [8]

linked_list.add_node(1, 6)
linked_list.print_all()