C++ 코딩테스트 공부 (중단)/c++ 알고리즘 공부

C++ 스택 자료구조 문제풀이

2022. 5. 19. 22:10

 

top = -1로 시작

 

top = -1;
void push(int x) {
	stack[++top] = x;
}

int pop() {
    return stack[top--];
}

#include<stack> 하면 해당 함수를 사용할 수 있다.

 

 

문제 : K진수 출력

10진수 N이 입력되면 K진수로 변환하여 출력하는 프로그램 작성

(10<=N<=1,000) 과 K(2, 5, 8, 16)

 

ex) 11 2 -> 1011

 

my그림 == 예술의 경지

스택의 push, pop 이용하면 1011 나옴

 

코드를 작성해보자

 

#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

int main() {
    int n, k;
    stack<int> s;
    char str[20] = "0123456789ABCDEF";
    scanf("%d %d", &n, &k);
    
    while(n>0) {
        s.push(n % k);
        n = n / k;
    }
    while(!s.empty()) {
        printf("%c", str[s.top()]);
        s.pop();
    }
    return 0;
}

 

 

문제 : 올바른 괄호

 

괄호가 입력되면 올바른 괄호이면 "YES", 올바르지 않으면 "NO"를 출력한다.

(())()는 YES, (()()))는 NO

스택을 이용해서 문제풀이

 

#include<iostream>
#include<string>
#include<stack>
#include<algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    stack<char> s;
    string b;
    cin >> b;
    bool ending = false;
    
    for(int i=0; i<b.size(); i++) {
        if (b[i] == '(') s.push('(');
        else {
            if(s.empty()) {
                printf("NO\n");
                ending = true;
                break;
            }
            else s.pop();
        }
    }
    
    if (ending == false) {
        if(s.empty()) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}

 

 

 

문제 : 기차운행 (stack 응용)

 

A도시에서 출발한 기차는 B도시로 도착한다.

그런데 도로 중간에 T자형 교차로가 있어 출발한 기차의 도착 순서를 조정할 수 있다.

 

교차로에서는 다음과 같은 두 개의 작업을 한다.

P(push)작업 : A도시에서 오는 기차를 교차로에 넣는다.

O(out)작업 : 교차로에 들어온 가장 최근 기차를 B도시로 보낸다.

만약 2 1 3 기차 번호 순으로 A도시에서 출발하더라도

B도시에는 T교차로를 이용하여 1 2 3 순으로 도착하게 할 수 있다.

그 작업 P, P, O, O, P, O순으로 작업을 하면 B도시에 1, 2, 3 순으로 도착한다.

1부터 N까지 번호를 가진 기차가 A도시에서 어떤 순으로 출발하든,

B도시에 번호순으로 도착 하도록 하는 교차로 작업을 출력한다.

모든 기차는 교차로에 들어가야만 B도시로 갈 수 있다.

번호순서대로 도착이 불가능하면 impossible 이라고 출력한다.

 

▣ 입력설명

첫 번째 줄에 자연수 N(3<=N<=30)가 주어진다.

두 번째 줄에 A도시에서 출발하는 기차번호순이 차례대로 입력된다.

 

▣ 출력설명

교차로 작업을 순서대로 P와 O로 출력한다.

 

▣ 입력예제

3

2 1 3

 

▣ 출력예제

PPOOPO

 

 

풀이 :

 

impossible이 아닐 경우

 

impossible일 경우

소스코드 :

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, a, t;
    int j = 1;
    stack<int> s;
    vector<int> v(n+1);
    cin >> n;
    for(int i=1; i<=n; i++) {
        v[i] = i;
    }
    vector<char> result;
    for(int i=1; i<=n; i++) {
        cin >> t;
        s.push(t);
        result.push_back('P');
        while(true) {
            if(s.empty()) break;
            if(v[j] == s.top()) {
                s.pop();
                j++;
                result.push_back('O');
            }
            else break;
        }
    }
    
    if(!s.empty()) {
        cout << "impossible" << "\n";
    }
    else {
        for(int i=0; i<result.size(); i++) {
            cout << result[i];
        }
    }
    

    return 0;
}

 

 

 

출처 (학습 자료) :

 

it 취업을 위한 알고리즘 문제풀이

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#curriculum

'C++ 코딩테스트 공부 (중단) > c++ 알고리즘 공부' 카테고리의 다른 글

C++ 재귀함수 알고리즘(+스택 이용)  (0) 2022.05.20
정렬 - 삽입정렬  (0) 2022.04.07
정렬 - 선택정렬, 버블정렬  (0) 2022.04.06
그리디 알고리즘  (0) 2022.04.04
'C++ 코딩테스트 공부 (중단)/c++ 알고리즘 공부' 카테고리의 다른 글
  • C++ 재귀함수 알고리즘(+스택 이용)
  • 정렬 - 삽입정렬
  • 정렬 - 선택정렬, 버블정렬
  • 그리디 알고리즘
daramG
daramG
dotori Java
daramG
다람쥐의 개발 블로그
daramG
전체
오늘
어제
  • 분류 전체보기 (193)
    • Java 코딩테스트 공부 (67)
      • Java 알고리즘 공부 (37)
      • Java 백준 문제풀이 (27)
      • Java 코테 나만의 팁 (3)
    • SQL Study (0)
      • Programmers SQL 문제풀이 (0)
      • SQLP 준비 (0)
    • 웹 개발 지식 정리 (0)
      • Servlet (0)
      • Java 정리 (0)
    • 자바 스프링 (45)
      • 스프링 공부 (4)
      • 스프링 게시판 프로젝트 (6)
      • 부트 블로그 JPA 프로젝트 (30)
      • react & springboot (5)
      • 스프링 오류창고 (0)
      • 리액트 + 스프링 프로젝트 (0)
      • pf (0)
      • pfError (0)
    • React (6)
      • React 정리 (3)
      • React 오류 창고 (3)
    • C++ 코딩테스트 공부 (중단) (20)
      • c++ 백준 문제풀이 (15)
      • c++ 알고리즘 공부 (5)
    • Unity (3)
      • Unity 공부 (3)
    • WebRTC (2)
      • WebRTC 강의학습 정리 (0)
      • WebRTC 프로젝트 (1)
    • 김영한님의 스프링 강의 학습 (10)
      • 스프링 강의 목차 (1)
      • 인텔리제이 & 스프링 기초 (1)
      • 스프링 핵심 원리 (8)
    • 전공 지식 정리 (40)
      • interview (0)
      • Java (0)
      • 운영체제 (4)
      • 데이터베이스 설계 (10)
      • 소프트웨어 공학 (3)
      • 유닉스 (14)
      • 디지털 논리회로 (0)
      • 인공지능 (7)
      • js (0)
      • etc (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 스프링부트 블로그 프로젝트
  • 인공지능
  • 백준 c++
  • Java 코테 나만의 팁
  • java
  • java 알고리즘
  • 스프링 공부
  • 김영한의 스프링 핵심 원리
  • 스프링부트 프로젝트
  • React&Spring 강의수강
  • 김영한 스프링 입문
  • 김영한 스프링 강의
  • 무서운 이야기
  • Unity 공부
  • 노마드코더의 zoom클론코딩
  • 코테 알고리즘
  • 부트 jpa 게시판 프로젝트
  • 데이터베이스 설계
  • 유닉스
  • 운영체제
  • Java 백준 문제풀이
  • 스프링 프로젝트
  • C++ 알고리즘
  • 디지털 논리회로

최근 댓글

최근 글

hELLO · Designed By 정상우.
daramG
C++ 스택 자료구조 문제풀이
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.