전체 글

[바킹독 알고리즘] 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이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때..

[Kotlin 문법] 스코프함수

스코프함수 kotlin내에는 여러 스코프함수가 존재하는데 각 스코프함수가 어떤 경우에 사용해야하는지 헷갈려서 정리하기위해 관련 포스팅을 해보고자 한다. 1. 람다함수도 여러줄 가능하다. 2. 파라미터가 없으면 중괄호 안 구문만 써주면된다. 3. 파라미터가 1개라면 it을 대체해서 사용가능하다. 스코프함수의 종류 apply, run, with, also, let이 존재한다. 차근차근 어떨 때 사용할 수 있는지 알아보자 1. apply 인스턴스 생성 후 변수에 담기 전 초기화 과정 수행할 때 사용한다. 리턴으로 자신의 인스턴스를 리턴한다. 2. run 이미 인스턴스가 만들어진 후 인스턴스의 함수나 속성을 scope내에서 사용해야할 때 유용하다 3. with run과 동일하다. 하지만 참조 연산자를 param..

[Kotlin 문법] 오버라이딩과 추상화

오버라이딩과 추상화 오버라이딩이란? 서브클래스가 슈퍼클래스를 상속받게되면 슈퍼클래스 안에 있는 함수와 동일한 이름의 함수를 가질 수 없다. 같은이름 다른 기능의 함수를 만들려면 override를 반드시 해줘야한다! => 즉 슈퍼클래스의 메서드를 서브클래스에서 재정의하는 것을 오버라이딩이라 한다. 슈퍼클래스의 함수에 open을 붙이면 서브클래스에서 오버라이딩이 가능하다. fun main() { Tiger().eat() } open class Animal{ open fun eat() { println("음식을 먹습니다.") } } class Tiger : Animal() { override fun eat() { println("고기를 먹습니다.") } } 위와같이 Animal 클래스의 eat()메서드를 Ti..

[Kotlin] 클래스와 상속

클래스와 상속 클래스란? 간단히 말하면 어떤 변수와 그 변수를 사용하는 기능(메서드)들을 묶어둔 것이다. 클래스 기본구조 fun main() { Person("서현",22).introduce() } class Person(var name:String, var age:Int) { fun introduce() { println("안녕하세요 ${this.name}입니다 나이는 ${this.age} 입니다.") } } 다음과 같이 Person 클래스를 생성하고, introduce라는 메서드를 만들어서 사용할 수 있다. 클래스 생성자 생성자란? 새로운 인스턴스를 만들기위해 호출하는 함수로 초기화 기능과 인스턴스 생성시 수행할 구문을 작성 할 수 있다. 아래와 같이 init 함수 안에 생성시 초기화 할 구문을 넣어..

[바킹독 알고리즘] 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..