[Coding Test]파이썬 자료 구조

Author

SEOYEON CHOI

Published

December 20, 2024

Linear Array 선형 배열

1.

List에서 오름차순에 맞게 x 값을 삽입

def al(list,x):
    for i,j in enumerate(list):
        if j > x  :
            list.insert(i,x)
            break
    else:
        list.append(x)
    return list
al([1,2,3,4,5],9)
[1, 2, 3, 4, 5, 9]
al([1,2,3,4,5],2.3)
[1, 2, 2.3, 3, 4, 5]
for i,j in enumerate([1,2]):
    print(i) # index
    print(j) # value
0
1
1
2
list.insert(index, element)

  • 특정 인덱스 위치에 항목을 삽입하는 데 사용

  • index: 항목을 삽입할 위치를 나타내는 정수입니다.

  • element: 삽입하려는 값입니다.

c = [1,2,3]
c.insert(1,10)
print(c)
[1, 10, 2, 3]

2.

List에서 x값의 index반환, 부재시 -1 반환

def bb(list,x):
    ans = []
    for i,j in enumerate(list):
        if j == x:
            ans.append(i)
    if len(ans)==0:
        ans.append(-1)
    return ans
bb([1,2,3,4,5],3)
[2]
bb([1,2,3,4,5],2.3)
[-1]

Sorting & Searching 정렬과 탐색

오름차순 정렬된 배열에서 x의 index 값을 반환, 부재시 -1 반환

def cc(list,x):
    low = 0
    high = len(list) - 1
    ans = 0
    while(low<=high):
        mid = (low + high) // 2
        if list[mid] == x:
            ans = mid
            break
        elif list[mid] > x:
            high = mid - 1
        else:
            low = mid - 1
    else:
        return - 1
    return ans
cc([3,4,5,6],2)
-1

Recursice Algorithm 재귀알고리즘

재귀

- 피보나치 수열

def aa(x):
    ans = 0
    if x <= 1:
        ans=1
    else:
        ans = aa(x-1) + aa(x-2)
    return ans
aa(3)
3
  • 반복문 사용
def aa(x):
    ans = 0
    if x<=1:
        ans = x
    else:
        now = 1
        before = 0
        for i in range(0,x):
            ans = before + now
            before = now
            now = ans
    return ans
aa(3)
3

Recursive Algorithm 재귀 알고리즘 응용용

재귀적 이진탐색 구현

  • 이진 탐색은 정렬된 리스트에서 검색하려는 값을 찾을 때, 리스트를 절반씩 나누며 탐색하는 방법
def aa(List,x,l,u):
    if x < List[l] or x > List[u]:
        return -1
    mid = (l + u) //2
    if x == List[mid]:
        return mid
    elif x < List[mid]:
        return aa(List, x, l , mid-1)
    else:
        return aa(List, x, mid + 1, u)
aa([1,2,3,4],3,1,3)
2

Comlexity of Algorithms 알고리즘의 복잡도

- Big-O Notation (최악의 경우 시간 복잡도)

  • 정의: Big-O 표기법은 최악의 경우에 알고리즘이 처리하는 최대 시간을 나타냅니다.
  • 목적: 주로 알고리즘의 성능을 평가할 때 사용되며, 상한을 나타냅니다.

- Big-Ω Notation (최선의 경우 시간 복잡도) - 정의: Big-Ω 표기법은 알고리즘이 최선의 경우에 처리하는 최소 시간을 나타냅니다. - 목적: 알고리즘이 최선의 경우에는 얼마나 빠를 수 있는지를 나타내는 하한을 제공합니다.

- Big-Θ Notation (평균적인 경우 시간 복잡도)

  • 정의: Big-Θ 표기법은 알고리즘의 평균적인 경우에 소요되는 시간(또는 공간)을 나타냅니다.
  • 목적: 알고리즘의 성능을 평균적으로 평가할 수 있게 해주며, 상한과 하한을 동시에 나타냅니다.

단일 연결 리스트 구현

class Node:
    def __init__(self,item):
        self.data = item
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None  # 리스트의 첫 번째 노드를 가리킬 포인터 (초기값은 None)

    # 리스트가 비었는지 확인
    def is_empty(self):
        return self.head is None

    # 리스트의 끝에 새로운 노드를 추가
    def append(self, data):
        new_node = Node(data)  # 새로운 노드 생성
        if self.is_empty():  # 리스트가 비어있다면
            self.head = new_node  # head가 새로운 노드를 가리키게 설정
        else:
            current = self.head
            while current.next:  # 마지막 노드까지 이동
                current = current.next
            current.next = new_node  # 마지막 노드의 next를 새로운 노드로 설정

    # 리스트의 시작에 새로운 노드를 추가
    def prepend(self, data):
        new_node = Node(data)  # 새로운 노드 생성
        new_node.next = self.head  # 새로운 노드가 기존 head를 가리키게 설정
        self.head = new_node  # head를 새로운 노드로 갱신

    # 특정 값을 가진 노드를 삭제
    def delete(self, key):
        current = self.head
        if current is None:  # 리스트가 비어있으면 삭제할 수 없음
            return
        if current.data == key:  # 삭제할 노드가 head라면
            self.head = current.next  # head를 다음 노드로 갱신
            current = None  # 기존 노드 삭제
            return
        prev = None
        while current and current.data != key:  # 삭제할 노드를 찾을 때까지 이동
            prev = current
            current = current.next
        if current is None:  # 찾지 못한 경우
            return
        prev.next = current.next  # 현재 노드의 이전 노드가 다음 노드를 가리키게 설정
        current = None  # 현재 노드 삭제

    # 리스트의 모든 요소를 출력
    def display(self):
        current = self.head
        if current is None:
            print("리스트가 비어있습니다.")
            return
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 단일 연결 리스트 인스턴스 생성
sll = SinglyLinkedList()

# 값 추가
sll.append(10)
sll.append(20)
sll.append(30)
sll.prepend(5)  # 리스트의 맨 앞에 5 추가

# 리스트 출력
print("리스트 내용:")
sll.display()

# 값 삭제
sll.delete(20)  # 20 삭제

# 삭제 후 리스트 출력
print("20을 삭제한 후 리스트 내용:")
sll.display()

# 값 삭제 (head 노드)
sll.delete(5)  # 5 삭제

# 삭제 후 리스트 출력
print("5를 삭제한 후 리스트 내용:")
sll.display()
리스트 내용:
5 -> 10 -> 20 -> 30 -> None
20을 삭제한 후 리스트 내용:
5 -> 10 -> 30 -> None
5를 삭제한 후 리스트 내용:
10 -> 30 -> None

연속 연결 리스트

class ContiguousLinkedList:
    def __init__(self):
        self.nodes = []  # 노드를 저장할 리스트 (배열처럼 사용)
        self.head = None  # 리스트의 첫 번째 노드의 인덱스 (초기값은 None)
    
    # 리스트가 비었는지 확인
    def is_empty(self):
        return self.head is None
    
    # 새로운 노드를 추가 (끝에 추가)
    def append(self, data):
        new_node = [data, None]  # 새로운 노드는 데이터와 None을 가짐 (다음 노드 없음)
        self.nodes.append(new_node)  # 노드를 리스트에 추가
        
        if self.is_empty():
            self.head = 0  # 첫 번째 노드가 추가되면 head를 0으로 설정
        else:
            # 마지막 노드를 찾고, 그 노드의 '다음'을 새 노드로 설정
            current_index = self.head
            while self.nodes[current_index][1] is not None:
                current_index = self.nodes[current_index][1]
            
            self.nodes[current_index][1] = len(self.nodes) - 1  # 마지막 노드의 'next'를 새 노드 인덱스로 설정
    
    # 리스트의 맨 앞에 노드를 추가
    def prepend(self, data):
        new_node = [data, self.head]  # 새 노드는 데이터와 기존 head를 가짐
        self.nodes.append(new_node)  # 노드를 리스트에 추가
        self.head = len(self.nodes) - 1  # 새 노드가 head가 되도록 설정
    
    # 특정 값을 가진 노드 삭제
    def delete(self, key):
        if self.is_empty():
            return
        
        current_index = self.head
        prev_index = None
        
        # key 값이 head인 경우
        if self.nodes[current_index][0] == key:
            self.head = self.nodes[current_index][1]  # head를 다음 노드로 갱신
            return
        
        # 나머지 노드들에서 삭제할 노드를 찾기
        while current_index is not None and self.nodes[current_index][0] != key:
            prev_index = current_index
            current_index = self.nodes[current_index][1]
        
        if current_index is None:
            return  # key 값이 없으면 종료
        
        # 현재 노드를 삭제
        self.nodes[prev_index][1] = self.nodes[current_index][1]  # 이전 노드의 'next'를 현재 노드의 'next'로 설정
    
    # 리스트 출력
    def display(self):
        if self.is_empty():
            print("리스트가 비어있습니다.")
            return
        
        current_index = self.head
        while current_index is not None:
            print(self.nodes[current_index][0], end=" -> ")
            current_index = self.nodes[current_index][1]
        print("None")
# 연속 연결 리스트 인스턴스 생성
cll = ContiguousLinkedList()

# 값 추가
cll.append(10)
cll.append(20)
cll.append(30)
cll.prepend(5)  # 리스트의 맨 앞에 5 추가

# 리스트 출력
print("리스트 내용:")
cll.display()

# 값 삭제
cll.delete(20)  # 20 삭제

# 삭제 후 리스트 출력
print("20을 삭제한 후 리스트 내용:")
cll.display()

# 값 삭제 (head 노드)
cll.delete(5)  # 5 삭제

# 삭제 후 리스트 출력
print("5를 삭제한 후 리스트 내용:")
cll.display()
리스트 내용:
5 -> 10 -> 20 -> 30 -> None
20을 삭제한 후 리스트 내용:
5 -> 10 -> 30 -> None
5를 삭제한 후 리스트 내용:
10 -> 30 -> None