IT-garden

문제

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

단순연결리스트(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