IT-garden

이중연결리스트(Doubly Linked List)는 각 노드가 두 개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키는 연결리스트를 구현한 자료구조입니다.

이중연결리스트는 단순연결리스트의 단점(역방향으로 노드 탐색 불가능, 삽입이나 삭제시 반드시 이전 노드를 가리키는 레퍼런스를 추가로 알아야 함)을 보완하기 위해 나왔습니다.

하지만 노드마다 2개의 레퍼런스를 저장해야 한다는 단점이 있습니다.

이중연결리스트의 기본 구조입니다.

head는 이중연결리스트의 첫 번째 노드가 무엇인가 의미하는 정보입니다.

tail은 이중연결리스트의 마지막 노드가 무엇인가 의미하는 정보입니다.

node는 아이템과 레퍼런스 2개를 가집니다.

item은 항목으로 node값이 저장됩니다.

reference1는 메모리 주소를 의미하며 이전 노드의 위치를 알려줍니다.

reference2는 메모리 주소를 의미하며 다음 노드의 위치를 알려줍니다.

__init__(self) : DList 객체 생성

insert_before() : p가 가리키는 노드 앞에 새 노드를 삽입

insert_after() : p가 가리키는 노드 뒤에 새 노드를 삽입

delete() : 노드 x 삭제

이중연결리스트의 파이썬 코드입니다.

class DList:
    
    class Node:
        def __init__(self, item, prev, link):  # 노드 생성자
            self.item = item  # 항목
            self.prev = prev  # 앞노드 레퍼런스
            self.next = link  # 뒤노드 레퍼런스

    def __init__(self):  # 이중 연결 리스트 생성자
        # head, tail, 항목수로 구성
        # 두 더미노드(head, tail)에는 실제 항목 저장하지 않음
        self.head = self.Node(None, None, None)
        self.tail = self.Node(None, self.head, None)
        self.head.next = self.tail
        self.size = 0

    def size(self):
        return self.size

    def isempty(self):
        return self.size == 0

    def insert_before(self, p, item):  # p가 가리키는 노드 앞에 새 노드를 삽입
        t = p.prev # p 앞의 기존 노드
        n = self.Node(item, t, p)  # 삽입할 노드
        p.prev = n  # 새 노드와 뒤 노드 연결
        t.next = n  # 새 노드와 앞 노드 연결
        self.size += 1 

    def insert_after(self, p, item):  # p가 가리키는 노드 뒤에 새 노드를 삽입
        t = p.next # p 뒤의 기존 노드
        n = self.Node(item, p, t)  # 삽입할 노드
        t.prev = n  # 새 노드와 뒤 노드 연결
        p.next = n  # 새 노드와 앞 노드 연결
        self.size += 1

    def delete(self, x):  # 노드 x 삭제
        f = x.prev # x 앞의 기존 노드
        r = x.next # x 뒤의 기존 노드
        f.next = r  # x를 건너뛰고 x의 앞뒤 노드를 연결
        r.prev = f  # x를 건너뛰고 x의 앞뒤 노드를 연결
        self.size -= 1
        return x.item

    def print_list(self):
        if self.isempty():
            print('List is empty.')
        else:
            p = self.head.next
            while p != self.tail:
                if p.next != self.tail:
                    print(p.item, ' <=> ', end='')
                else:
                    print(p.item)
                p = p.next  # 노드를 차례로 방문

class EmptyError(Exception):  # Underflow시 에러 처리
    pass


s = DList() # 이중 연결 리스트 생성
s.insert_after(s.head, 'apple') 
s.insert_before(s.tail, 'orange')
s.insert_before(s.tail, 'cherry')
s.insert_after(s.head.next, 'pear')
s.print_list()

print('마지막 노드 삭제 후:\t', end='')
s.delete(s.tail.prev)
s.print_list()

print('맨 끝에 포도 삽입 후:\t', end='')
s.insert_before(s.tail, 'grape')
s.print_list()

print('첫 노드 삭제 후:\t', end='')
s.delete(s.head.next)
s.print_list()

print('두 번째 노드 삭제 후:\t', end='')
s.delete(s.head.next.next)
s.print_list()

print('첫 노드 삭제 후:\t', end='')
s.delete(s.head.next)
s.print_list()

print('첫 노드 삭제 후:\t', end='')
s.delete(s.head.next)
s.print_list()

위의 개념과 소스코드는 생능출판의 '파이썬과 함께하는 자료구조의 이해'를 보고 이해하여 정리한 것입니다.

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한조건

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

입출력 예

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

나의 풀이

def solution(phone_book):
    answer = True
    for i in range(len(phone_book)):
        a = phone_book[:i] + phone_book[i+1:] 
        for j in a:
            jj = j[:len(phone_book[i])]
            if phone_book[i] == jj:
                answer = False
                break
        if answer == False:
            break
    return answer

1. 전화번호부에 적힌 전화번호를 하나씩 기준으로 삼아 다른 번호의 접두어인 경우가 있는지 확인합니다.
2. 하나라도 접두어인 경우가 있으면 반복문을 나오고 False를 출력합니다.

다른 사람의 풀이

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

전화번호부를 정렬하고 기준인 번호보다 뒤에 있는 전화번호부만 확인합니다.
뒤에 있는 전화번호가 기준인 번호로 시작하면 False를 리턴합니다.

프로그래머스 '전화번호 목록' : https://programmers.co.kr/learn/courses/30/lessons/42577

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한조건

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

나의 풀이

def solution(prices):
    answer = [0] * len(prices)
    for i in range(len(prices)):
        c=0
        for j in range(i+1,len(prices)):
            c += 1
            if prices[i] > prices[j]:
                break
        answer[i] = c      
    return answer

1. 리스트 prices의 각 원소들을 기준으로 잡고 뒤의 값들과 비교합니다.
2. 만약 앞에 있는 값이 뒤에 있는 값보다 크면 for문을 나와 개수를 리스트 answer에 넣습니다.
3. 마지막에 리스트 answer를 리턴합니다.

프로그래머스 '주식가격' : programmers.co.kr/learn/courses/30/lessons/42584

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,m=map(int,input().split()) 
a=[list(map(int,input())) for i in range(n)]
ch=[[[0,0] for j in range(m)] for i in range(n)]

dx=[-1,0,1,0]
dy=[0,1,0,-1]

def bfs():
    de=deque()
    de.append([0,0,0])
    ch[0][0][0]= 1
    while de:
        x,y,z=de.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if a[nx][ny] == 0 and ch[nx][ny][z] == 0:
                    ch[nx][ny][z] = ch[x][y][z] + 1
                    de.append([nx,ny,z])
                elif a[nx][ny] == 1 and  z == 0 and ch[nx][ny][z+1] == 0: 
                    ch[nx][ny][z+1] = ch[x][y][z] +1
                    de.append([nx,ny,z+1])
                              
bfs()
if ch[n-1][m-1][0] != 0 and ch[n-1][m-1][1] != 0: # 벽을 거친 경우와 거치지 않은 경우 둘 다 가능한 경우
    print(min(ch[n-1][m-1][0],ch[n-1][m-1][1]))
elif ch[n-1][m-1][0] != 0: # 벽을 거치지 않은 경우만 가능한 경우
    print(ch[n-1][m-1][0])
elif ch[n-1][m-1][1] != 0: #벽을 거친 경우만 가능한 경우
    print(ch[n-1][m-1][1])
else: # 불가능한 경우
    print(-1)

배열 ch를 x좌표, y좌료, 부순 것 개수로 3차원으로 만듭니다.
기본 BFS에서 벽이 나왔는데 벽을 뚫은 적이 없는 경우 세번째 차수 값을 바꿔 ch에 저장하고 그 값을 큐에 넣습니다.
한번 BFS를 수행하고 벽을 거쳤을 때와 거치지 않은 것 중 최단 거리를 구합니다.

백준 알고리즘 2206번 : www.acmicpc.net/problem/2206

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

예제 입력과 출력

알고리즘 분류

문자열 처리 

정답

import sys
input = lambda : sys.stdin.readline().rstrip()

while True:
    a=input()
    st=[]
    if a == '.':
        break

    for i in a:
        if i == '[' or i == '(':
            st.append(i)
        elif i == ']':
            if len(st) != 0 and st[-1] == '[':
                st.pop()
            else:
                st.append(']')
                break
        elif i == ')':
            if len(st) != 0 and st[-1] == '(':
                st.pop()
            else:
                st.append(')')
                break
        
    if len(st) == 0:
        print('yes')
    else:
        print('no')

백준 알고리즘 4949번 : www.acmicpc.net/problem/4949

문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

예제 입력과 출력

정답

import sys
input = lambda : sys.stdin.readline().strip()

k=int(input())
st=[]

for i in range(k):
    a=int(input())
    if a == 0:
        st.pop()
    else:
        st.append(a)

print(sum(st))

백준 알고리즘 10773번 : https://www.acmicpc.net/problem/10773