알고리즘

[BOJ/C++] 9012번 괄호

문제 설명 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 ..

[BOJ/C++] 3986번 좋은단어

문제 설명 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다. 평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자. 입력 첫째 줄에 단어의 수 ..

[BOJ/C++] 4949번 균형잡힌 세상

문제 설명 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이..

[바킹독 알고리즘] 0x08강:스택의 활용(수식의 괄호 쌍)

수식의 괄호쌍이란? 주어진 괄호, 문자열이 올바른지 아닌지 판단하는 문제이다. 첫번째 예시의 괄호쌍만 본다면 {()} 로 올바른 괄호쌍이지만, 두번째는 {(})로 올바르지 않은 괄호쌍이다. 문제 해결을 위한 관찰 괄호쌍들이 잘 짝을 이루었는지를 판단하려면 " 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라 생각해도 된다." (대박 이렇게 생각하면 stack으로 문제를 풀 수 있는거같다.) 문제 해결방법 위 방법을 문제에 활용해 stack에 적용하면 문제를 해결할 수 있다. 결론적으로 stack의 empty() 여부로 올바른 짝인지 아닌지 확인 할 수 있다.!! 문제현황 연습 문제 ✔ 4949 균형잡힌 세상 정답 코드 기본 ..

[BOJ/C++] 10814번 나이순 정렬

문제 설명 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다. 출력 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다...

[BOJ/C++] 1021번 회전하는 큐

문제 설명 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때..

[바킹독 알고리즘] 0x07강:Deque

덱 Deque : 양쪽 끝에서 삽입과 삭제 모두 가능 성질 1. 원소의 추가,제거 O(1) 2. 제일 앞/뒤 원소 확인 O(1) 3. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 구현 덱의 Head와 Tail의 초기값이 MX인 이유는 헤드와 테일에서 모두 삽입삭제가 가능하기 때문이다. 위 이미지와같이 삽입/삭제가 일어나기 때문에 H가 0 일경우 더이상 왼쪽으로 삽입 할 수 없어서 MX로 잡아둔다. (선형으로 구현) #include using namespace std; const int MX = 100005; int dat[2 * MX + 1]; int head = MX, tail = MX; void push_front(int x) { dat[--head] = x; //앞에다 삽입하는..

[바킹독 알고리즘] 0x06강:Queue

Queue: FIFO (First In First Out) 성질 원소 추가 O(1) , 제거 O(1) 제일 앞/뒤 원소 확인 O(1) 나머지 원소 확인 변경이 원칙적으로 불가 // 큐의 원소가 들어가는 배열을 원형으로 만들어서 불필요한 공간낭비를 줄임. const int MX=10000005; int dat[MX]; int head=0, tail=0; void push(int x){ dat[tail++] = x; } void pop(){ head++; } int front() { return dat[head]; } int back() { return dat[tail]; } void test() { push(10); push(20); push(30); cout

[BOJ/C++] 17298번 오큰수

문제 설명 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1..

[BOJ/C++] 6198번 옥상 정원 꾸미기

문제 설명 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다. 그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다. 예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우 = = = = - = = = = -> 관리인이 보는 방향 = - = = = = = = = = = 10 3 7 4 12 2 -> 빌딩의 높이 [1][2][3][4][5][6] -> 빌딩의 번호 1번 관리인은 2, 3, 4번 ..

[BOJ/C++] 2493번 탑

문제 설명 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면,..

[바킹독 알고리즘] 0x05강:Stack

Stack : Last In First Out 원소의 추가, 제거 O(1) 제일 상단 원소 확인 O(1) 제일 상단이 아닌 나머지 원소 확인/변경 원칙적으로 불가능 배열로 스택 구현 #include using namespace std; const int MX=10000005; int dat[MX]; int pos = 0; //삽입해야할 index void push(int x){ dat[pos++]=x; } void pop() { pos--; } int top(){ return data[pos-1]; } STL 스택 문제 현황 연습 문제 ✔ 10828 스택 정답 코드 기본 문제 ✔ 10773 제로 정답 코드 응용 문제 1874 스택 수열 정답 코드 응용 문제 ✔ 2493 탑 정답 코드 응용 문제 ✔ 619..