IT-garden

단순연결리스트(Singly Linked List)는 동적 메모리 할당을 이용해 노드들을 한 방향으로 연결하여 리스트를 구현한 자료구조입니다.

단순연결리스트는 삽입이나 삭제 시 항목들의 이동이 필요없습니다.

하지만 항목을 탐색하려면 항상 첫 노드부터 원하는 노드를 찾을 때까지 차례로 방문하는 순차탐색을 이용해야 합니다.

단순연결리스트의 기본 구조입니다.

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

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

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

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

Insert_front() : 새 노드를 단순연결리스트의 맨 앞에 삽입, 시간복잡도 : O(1)

Insert_after() : p가 가리키는 노드의 다음에 삽입, 시간복잡도 : O(1)

delete_front() : 단순연결리스트의 첫 노드 삭제, 시간복잡도 : O(1)

delete_after() : p가 가리키는 노드의 다음 노드 삭제, 시간복잡도 : O(1)

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

class SList:
    
    class Node:
        def __init__(self, item, link):  # 노드 생성자
            self.item = item  # 항목
            self.next = link  # 다음 노드 레퍼런스
            
    def __init__(self):  # 단순 연결 리스트 생성자
        self.head = None
        self.size = 0  

    def size(self):
        return self.size

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

    def insert_front(self, item):  # 연결 리스트의 맨 앞에 새 노드 삽입
        if self.is_empty():  # 연결 리스트가 empty인 경우
            self.head = self.Node(item, None)  # head가 새 노드 참조
        else: 
            self.head = self.Node(item, self.head)  # head가 새 노드 참조
        self.size += 1

    def insert_after(self, item, p):  # p가 가리키는 노드 다음에 새 노드 삽입
        p.next = SList.Node(item, p.next)  # 새 노드가 p 다음 노드
        self.size += 1

    def delete_front(self):  # 연결 리스트의 맨 앞 노드 삭제 
        if self.is_empty():  # empty인 경우 에러 처리
            raise EmptyError('Underflow')
        else:
            self.head = self.head.next  # head가 둘째 노드를 참조
            self.size -= 1

    def delete_after(self, p):  # p가 가리키는 노드의 다음 노드 삭제
        if self.is_empty():  # empty인 경우 에러 처리
            raise EmptyError('Underflow')
        t = p.next
        p.next = t.next  # p 다음 노드를 건너뛰어 연결
        self.size -= 1

    def search(self, target):  # 노드 탐색(순차탐색)
        p = self.head
        for k in range(self.size): 
            if target == p.item:
                return k  # 탐색 성공
            p = p.next
        return None  # 탐색 실패

    def print_list(self):
        p = self.head
        while p:
            if p.next != None:
                print(p.item, ' -> ', end='')
            else:
                print(p.item)
            p = p.next  # 노드들을 순차탐색

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



s = SList() #객체생성
s.insert_front('orange')
s.insert_front('apple')
s.insert_after('cherry',s.head.next)
s.insert_front('pear')
s.print_list()

print('cherry는 %d번째' % s.search('cherry'))
print('kiwi는', s.search('kiwi'))   

print('배 다음 노드 삭제 후:\t\t', end='')
s.delete_after(s.head)
s.print_list()

print('첫 노드 삭제 후:\t\t', end='')
s.delete_front()
s.print_list()
print('첫 노드로 망고, 딸기 삽입 후:\t', end='')
s.insert_front('mango')
s.insert_front('strawberry')
s.print_list()
s.delete_after(s.head.next.next)

print('오렌지 다음 노드 삭제 후:\t', end='')
s.print_list()

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

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

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

n=int(input())
a=list(map(int,input().split()))

dp=[1]* n
c=copy.deepcopy(a)

for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]+1:
            dp[i]= dp[j]+1
            c[i] = max(c[i],c[j]+a[i])
        
print(max(c))

가장 긴 증가하는 부분수열의 알고리즘과 같게 만들고 수열의 합을 기록하는 배열을 하나 추가합니다.
a[i] > a[j] and dp[i] < dp[j]+1 조건이 만족하면 가장 값이 큰 경우를 배열 c에 넣습니다.

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

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

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

n=int(input())
a=list(map(int,input().split()))

dp=[1] * n
dp2=[1] * n
for i in range(n): # 앞에서부터 부분 증가수열 개수
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]+1:
            dp[i] = dp[j]+1

for i in range(n-1,-1,-1): # 뒤에서부터 부분 증가수열 개수
    for j in range(n-1,i-1,-1):
        if a[i]> a[j] and dp2[i] < dp2[j]+1:
            dp2[i] = dp2[j]+1

li=[0] * n
for i in range(n):
    li[i]=dp[i]+dp2[i]-1

print(max(li))

가장 긴 부분 수열을 앞에서부터 실행하고 뒤에서부터 실행합니다.
두 배열의 값을 합치고 1을 뺍니다.(자기자신의 길이도 포함하기 때문에)
두 배열의 값을 합친 것 중 가장 큰 값을 출력합니다.

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

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

n=int(input())
a=list(map(int,input().split()))

dp=[1]* n

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            dp[i]= max(dp[i],dp[j]+1)
            
print(max(dp))

수열 A = {10, 20, 10, 30, 20, 50} 이라면
부분 수열은 {10}, {10, 20}, {10, 20, 30}, {10, 20, 30, 20} 과 같은 것이 있습니다.
이 중 부분수열이 전부 증가하는 요소로 된 것을 증가하는 부분 수열이라 합니다.
가장 긴 증가하는 부분 수열은 부분수열 중 모두 증가하는 요소로 된 길이가 긴 부분수열입니다.

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

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘 

정답

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

n=int(input())
a=[]

for i in range(n):
    a.append(list(map(int,input().split())))
    
a.sort(key = lambda x: (x[1], x[0]))

c=0 # 회의 개수
t=0 # 회의실 시간

for s,e in a:
    if s >= t:
        t = e
        c += 1

print(c)

리스트 a를 끝나는 시간으로 정렬합니다.
끝나는 시간이 같을 경우 시작하는 시간 순으로 정렬합니다.

3 3
1 3
인 경우 답은 2인데 끝나는 시간으로만 정렬 해놓으면 답이 1로 나오는 것을 방지하기 위해서입니다.

리스트 a에서 처음부터 검사해서 시작시간이 t보다 작거나 같으면 해당 시간에 회의실을 사용한다 생각하고 c를 더해주고 t를 e로 바꿉니다.

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

문제

월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.

예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.

4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

회장은 회원들 중에서 점수가 가장 작은 사람이 된다. 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 회원의 수만큼 붙어 있다. 마지막 줄에는 -1이 두 개 들어있다.

출력

첫째 줄에는 회장 후보의 점수와 후보의 수를 출력하고, 두 번째 줄에는 회장 후보를 오름차순으로 모두 출력한다.

예제 입력과 출력

알고리즘 분류

플로이드 와샬 알고리즘 

정답

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

INF=sys.maxsize

n=int(input())
a=[[INF]*(n+1) for i in range(n+1)]

while True:
    s1,s2=map(int,input().split())
    
    if s1 == -1 and s2 == -1:
        break
    a[s1][s2] = 1
    a[s2][s1] = 1

for i in range(1,n+1): # 자기자신의 경로
    a[i][i] = 0

for k in range(1,n+1): # 거치는 거
    for i in range(1,n+1):
        for j in range(1,n+1):
            if a[i][j] == 1 or a[i][j] == 0:
                continue
            elif a[i][j] > a[i][k] + a[k][j]:
                a[i][j] = a[i][k] + a[k][j]     

r=[]
for i in range(1,n+1):
    r.append(max(a[i][1:]))

m=min(r)
print(m, r.count(m))
for i,v in enumerate(r):
    if v == m:
        print(i+1,end=' ')

전체 배열을 INF로 하고 자기자신으로 가는 경로는 0으로 설정합니다.
플로이드 와샬 알고리즘을 적용하고 각 행에서 가장 큰 값을 각 회원의 점수로 매깁니다.
점수들 중 가장 작은 값을 회장 후보의 점수로 삼고 후보의 수와 회장 후보를 출력합니다.

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