https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net # 조건 VPS를 판별하는 문제이다. VPS란, 괄호가 짝이 맞는 경우를 말하는데, (())와 같이 괄호안에 올바른 괄호가 들어가 있는 경우도 포함이다. 첫 째줄에는 테스트 케이스 수 N, 그 이후에는 괄호 문자열이 주어진다 # 접근 방법 및 SOLUTION 전형적인 STACK문제라고 생각이 들었다. 여는 괄호가 온다면 괄호 리스트에서 POP과 동시에 STACK에 넣..

백준 5557_1학년 # Problem 줄 지어있는 숫자 들이 있을 때 아래의 조건을 지키며 등식을 완성하여라 마지막 두 숫자 사이에는 '=', 나머지 숫자 사이에는 '+'또는 '-' 이 때, 왼쪽부터 계산을 할 때, 중간 결과값이 모두 0이상 20이하여야 한다. 올바른 등식의 수를 구하는 프로그램 작성 # 접근 방법 모든 경우의 수를 구하게 되면 2^100의 경우의 수가 생기므로 dp로 풀어야 될 것 같다. bottom-up 방식으로 DP TABLE 이용 DP TABLE의 경우 최댓값이 20이 넘어가면 안된다는 조건이 있기 때문에 21개만 만들어주면 된다. 점화식 equation[i][j+number[i]] += equation[i-1][j] equation[..

https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net # 조건 - D km 길이의 고속도로를 지나는데 이 고속도로는 심각하게 커브가 많아 운전하기 힘들다. - 이 고속도로에는 지름길이 존재하는데 - 모든 지름길은 일방통행이며, 고속도로 역주행은 불가 - 운전해야하는 최소 거리를 구하여라 # 접근 방법 및 풀이 과정 - 문제를 읽으며 드는 생각은 거리를 기록해둔 후 이를 통하여 최소 값을 구하면 될 것같다. - 내가 이용하는 지름길의 거리와..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net # 조건 정수 4를 1,2,3의 합으로 나타내는 방법은 총 7가지 합을 나타낼 때는 수를 1개이상 사용 정수 n이 주어졌을 때, 1,2,3의 합으로 나타내는 방법의 수를 구하라 # 나의 접근 방법 1,2,3으로 나타낼 수 있는 경우의 수를 구하는 문제이므로 6의 경우 1,1,1,1,1,1 에서 3,3 까지 오면된다. 1만 이용하는 방법에서 총 1의 개수 = 주어지는 n 이 때, 1,2,3으로 이루어진 길이 n의 중복순열을 구한 후 합이 n과 같다면 카운트 해준다. 길이 n은 2가 1개 들어갔을 ..

https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net # 조건 - 크기가 있는 상자들이 주어질 때, 앞의 상자가 뒤의 상자보다 크기가 작다면 뒷 상자에 앞의 상자 넣을 수 있다. - 예) 1 - 6 - 2 - 5- 7의 크기를 가진 상자가 주어질 때, 1- 6 -7 (3개) 또는 1-2-5-7 (4개)의 방법으로 상자를 넣을 수 있다. - 한 번에 최대 많은 상자를 넣었을 때의 개수를 구하여라. # 접근 방법 넣을 수 있는 모든 경우의 수를 구한다면 시간 초..

해시 구조를 이해하기 위해서 먼저 해시 테이블에 대해 알아보자. 1. 해시 테이블? 연관 배열 구조를 이용하여 키(key)와 결과 값(value)를 저장하는 자료구조 연관 배열 구조란 - key와 value가 1:1로 연관 되어 있는 구조이다. 파이썬의 Dictionary! 지원하는 명령 key와 value 저장 key가 주어질 때, 연관 value를 얻는 명령 key와 value가 주어질 때, 원래 key의 value값 수정 key가 주어질 때, 연관 value 제거\ 구조 해시 테이블의 경우 키(Key), 해시 함수(Hash Function), 해시(Hash), 값(value), 저장소(Bucket, Slot)로 이루어져 있다. 위 그림에서 볼 수 있듯이 키(key)는 해시함수(hash functio..

OTT, 유튜브 등을 시청할 때 '버퍼링' 때문에 짜증났던 기억이 있을 것이다. 왜 일어나는 것일까? 배웠던 Queue 구조를 활용하여 버퍼에 대해 알아보자. 또한 queue를 파이썬에서 더 간편하고 빠르게 사용하게 해주는 deque에 대해서도 알아보자. 목차 1. 버퍼 2. deque 모듈 1. 버퍼 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 영역 버퍼링: 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작 자료 구조 버퍼는 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용 순서대로 입/출력/전달되어야 하므로 FIFO 방식의 자료구조인 큐가 활용 그림을 통해 키보드 버퍼의 수행 과정을 보자. Queue와 버퍼에 대해 '마이쮸 나눠주기'를 구현해보며 이해해보자..

이전에 배웠던 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조이다. 동적 자료형인 리스트 자료형을 사용한다 선입선출 구조(FIFO : First In First Out) 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 한다. 즉, 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소가 가장 먼저 삭제된다. 기본 연산 삽입 : enQueue(item) - 큐의 뒤쪽(rear 다음)에 원소를 삽입하는 연산 삭제 : deQueue() - 큐의 앞쪽(front)에서 원소를 삭제하고 반환하는 연산 createQueue() - 공백 상태의 큐를 생성하는 연산 isEmpty() - 큐가 공백상태인지를 확인하는 연산 isFull() - 큐가 포화상태인지를 확인하는 연산 Qpeek() - 큐의 앞쪽(fro..

예전에 보았던 배열, 2차원 리스트와 같이 자료구조의 하나인 Stack에 대해서 알아보자. 알고리즘 문제를 풀면서도 많이 사용될 것이고 그 다음 구조, 알고리즘을 풀기 위해서는 잘 알아두는 것이 좋아보인다. # Stack 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 구조 저장된 자료는 선형 구조를 갖는다. 선형구조 : 자료 간의 관계가 1ㄷ1의 관계를 갖는다. 비선형구조: 자료 간의 관계가 1대 N의 관계를 갖는다 (예: 트리) 스택에 자료를 삽입하거나 자료를 꺼낼 수 있다. 마지막에 삽입한 자룔르 가장 먼저 꺼낸다. 즉 후입선출(LIFO, Last in First Out) 구조를 갖는다. 스택 구현 위하여 필요한 자료구조와 연산 자료구조: 자료를 선형으로 저장할 저장소 배열 사용 가능 저장소 자체를 스..