백준

[C++] 백준 2504번 괄호의 값

2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 스택 자료구조 문제. 구현력을 필요로 하는 노가다 문제이다. 문제 분석 스택 하나에 입력들을 넣어놨다가, 괄호가 닫히는 경우를 처리해주면 된다. 나같은 경우에는 다음과 같이 처리했다. 현재 입력이 '(' 또는 '['인 경우 -> 그냥 스택에 넣어준다. 현재 입력이 ')' 또는 ']'인 경우 -> 만일 스택의 위에 있는 게 숫자들일 경우, 다 더해준 후 *2 / *3을 해준다. 스택의 위에 있는 게 '(' / '[' 일 경우 '(' / '['를 빼내고 2를 넣어..

[C++] 백준 13460번 구슬 탈출 2

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 구현 / 시뮬레이션 문제로, 설계를 잘하고 구현을 해야 풀 수 있는 문제. 문제 분석 문제의 조건은 다음과 같다. N*M 보드가 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬이 있다. 빨간 구슬을 구멍으로 빼야 한다. 파란 구슬은 구멍으로 빠지면 안된다. 구슬은 직접 움직일 수 없고 보드를 상, 하, 좌, 우로 기울여서 움직여야 한다. -> 이 때, 두 개..

[C++] 백준 1005번 탈출

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 그래프 탐색과 DP를 통해 해결할 수 있는 문제. 특정 건물을 짓기 위해 어떻게 빨리 지을 수 있는 지 알아내는 알고리즘을 작성하는 문제였다. 알고리즘 분류를 보니, 위상 정렬이라는 알고리즘이 있었는데 해당 알고리즘에 대해서는 내가 아는 바가 없었지만 풀 수는 있었다. 문제 풀이 예시 이미지를 통해 문제를 해석해 보았다. 4번 건물을 짓기 위해서는 10초의 시간이 필요하며, 2번과 3번의 건물이 지어져 있어야 한다. 2번 건물을 짓기 위해서는 1초의 시간이..

[C++] 백준 3055번 탈출

3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 4179번 불! 과 같은문제 [C++] 백준 4179번 불! 그래프 탐색 문제. 최근에 이런 비슷한 문제인 3055번 탈출이라는 문제를 풀다가 실패했었다. 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 kimyunseok.tistory.com 그래프 탐색을 두 종류로 나누어서 진행해주면 된다. 저 때 풀이와 완전 다르게 풀었다. 문제 풀이 다음과 같은 조건이 있다. 마법을 부려 숲에 홍수를 낸다. 1마리인 도치가 비버굴..

[C++] 백준 16562번 친구비

16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 그래프 탐색 문제. 그래프가 여러개 존재한다고 생각하고 각 그래프에서 최소값을 찾으면 되는 문제다. 문제풀이 각 친구마다 친구비가 드는데, 친구의 친구도 친구가 된다. 즉, 이는 친구 관계가 edge가 되고 학생은 vertex가 된다고 해석했다. 그 후, 연결된 Vertex들 끼리 그래프 탐색을 한 후에 최소비용을 찾으면 된다. 어차피 최소비용의 학생하고만 친구를 하면 나머지는 자동으로 친구가 될..

[C++] 백준 5430번 AC

5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문자열 파싱, 자료구조를 이용해서 풀 수 있는 문제. 디테일에서 놓친 부분들이 많아서 틀렸습니다를 많이 받았다. 문제풀이 조건을 다음과 같이 해석해서 풀었다. '덱'을 사용해서 풀고, 현재 방향이 front인지 back인지를 저장한다. 시작의 경우 방향은 front가 된다. 'R' 명령어가 들어왔을 경우 : front / back 방향을 반대로 전환한다. 'D' 명령어가 들어왔을 경우 : 현재 덱에서 방향에 있는 수를 하나 pop한다. 이 때 덱이 비어있으면 error가 발생하도록 한다. 코드 전문 /* * 백준 54..

[C++] 백준 23290번 마법사 상어와 복제

https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제 고려해야 할 부분들이 상당히 많은 문제이지만, 특별한 알고리즘은 필요가 없다. 문제 조건 정리 기본 조건 4x4 격자 r행 c열을 (r, c)로 표현 물고기 M마리가 주어지고, 이동 방향(8가지)을 가진다. 상어도 격자 한 칸에 위치한다. 최초에는 둘 이상의 물고기가 같은 칸에 있을 수 있고, 상어와 물고기가 같은 칸에..

[C++] 백준 1043번 거짓말

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 그래프 탐색 문제. 그래프 탐색이라는 점을 발견한다면 어렵지 않게 풀 수 있다. 변수를 잘못 재사용해서 몇 번 틀려버려서 아쉬운 문제. 문제 풀이 문제는 다음과 같은 조건들이 있다. 지민이는 사실 혹은 과장(거짓말)을 말한다. 최초 사실을 아는 사람이 K명이라 할 때, 이 사람들에게는 사실만 말해야 한다. 사실을 들은 사람이 있다면 이 사람들이 있는 파티에서는 사실만 말해야 한다. 즉, 사실 & 과장 둘 다 들을 수는 없다. 따라서 사실을 아는 사람이 있는 파티를 먼저 제..

[C++] 백준 17298번 오큰수

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 자료 구조 - 스택 문제. 알고리즘 분류를 알고 풀어서 쉽게 접근할 수 있었다. 알고리즘 분류를 모르고 풀면 풀 수 있었을지 모르겠다. 문제풀이 다음과 같은 생각을 하고 풀었다. 큐를 두 개 만든다. 하나는 입력을 받아놓는 큐, 하나는 큐에서 꺼낸 수를 저장해놓는 큐. 입력을 받아놓는 큐에서 하나씩 꺼내보며 꺼낸 수를 저장해놓는 큐의 맨 위와 비교한다. 만일 큐가 비어있다면 오큰수가 없다는 뜻이다. 큐가 비어있지 않을 때에는 현재 수와 저장해놓은 큐의 맨 위의 수를 비교한다..

[C++] 백준 16235번 나무 재테크

16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 소속 문제. 구현 / 시뮬레이션 문제 중 골드4지만 꽤 낮은 정답률인 문제이다. 아마 나 포함 대부분 시간 초과 문제가 발생하는 것 같다. 문제 조건 문제의 힌트는 다음과 같다. 땅의 크기가 N x N이다. (r, c)은 r은 행, c는 열을 의미. S2D2라는 로봇은 양분을 추가해줌. 맨 처음 5만큼의 양분이 각 칸에 존재 또한 다음과 같은 순서로 진행된다. 처음에 주어진 조건 M개의 나무를 구매한다. 여러 개 ..