알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 우선순위 큐를 이용하는 문제입니다. 오름차순을 저장하는 큐, 내림차순을 저장하는 큐를 모두 만들어주면 됩니다. 최솟값과 최댓값을 경우에 따라 제거해야 합니다. 이때 큐를 하나만 만들어서 구현을 하면 연산의 갯수가 너무 많기에 시간 초과가 생깁니다. 따라서 오름차순, 내림차순을 저장하는 큐를 만들어 각각 관리해줘야 합니다. (221 , 221 , 15 , 13 , 100 , -..

문제 링크입니다. https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net Deque과 문자열을 이용해 풀 수 있는 문제였습니다 문제를 풀기 위해서는 구현해야할 것이 3가지가 있습니다. 1. 문자열이 주어졌을때, 숫자를 구하기 2. 함수 P 실행하기 3. 실행한 결과 출력하기 1. 문자열이 주어졌을때, 숫자구하기 string num; for (int i = 0; i = '0' && number[i] 0) { Number.push_back(s..

문제 링크입니다. https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 수학적 규칙을 찾아 푸는 문제였습니다. 부터 까지 달력이 증가할 때, 는 몇 번째 해인지를 구하는 문제입니다. 먼저 달력이 어떻게 증가하는지 확인하겠습니다. 규칙을 찾기 위해서 카잉 달력을 끝까지 확인해보겠습니다. 로 이루어진 카잉 달력을 X값의 변화에 따라 나열해봤습니다. 이때 X 값이 같을 때 Y값 변화를 확인해보겠습니다. M = 10, N = 12 인 경우, X값이 5일때 Y값..

문제 링크입니다. https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문자열과 그리디 알고리즘을 사용하여 푸는 문제였습니다. 크게 2가지의 과정을 통해 문제를 풀면 됩니다. 1. 문자열을 숫자와 수식으로 변경해 저장하기 2. 숫자를 뺄 경우 뺄 수 있는 최댓값을 구하기 1. 문자열을 숫자와 수식으로 변경하기 void get_number() { string now_number; for (int i = 0; i < formula.size(); i..

문제 링크입니다. https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net map을 사용해서 푸는 문제입니다. 예시를 통해 확인해보겠습니다. 첫번째 입력에서는 headgear가 hat과 turban으로 2가지가 있으며, eyewear는 sunglasses로 1가지가 있습니다. 이때 1가지 이상만 입으면 됨으로 각각 1개씩 입는 경우인 3가지, (hat, sung..

문제 링크입니다. https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net map을 사용하는 문제였습니다. 출력을 2가지로 나눠서 해야합니다. 1. 포켓몬의 이름이 들어왔을 경우 -> 해당 포켓몬의 입력 번호 2. 포켓몬의 번호가 들어왔을 경우 -> 해당 번호 포켓몬의 이름 2번 출력의 경우는 쉽게 만들 수 있습니다. string 배열을 만든뒤, 입력 순서에 맞게 포켓몬을 저장해주면 됩니다. 1번 출력의 경우는 포켓몬의 이름..

문제 링크입니다. https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 삼성 SW 역량테스트 문제입니다. 구현이 까다로웠지만, 출력 예시를 보면서 문제를 풀면 되는 문제였습니다. 문제를 풀기 위해서는 몇가지 구현을 해야합니다. 1. 원판 돌리기 2. 원판에서 겹치는 수 없애기 3. 겹치는 수가 없을 경우 평균을 구한뒤 원판을 바꾸기 1. 원판 돌리기 X는 돌릴 원판을 결정하는 수, D는 방향(시계 or 반시계), K는 돌릴 횟수, M..

문제 링크입니다. https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 삼성 SW 역량테스트 문제입니다. 문제를 풀기 위해서는 2가지를 알아야합니다. 1. 드래곤 커브 구현하기 2. 정사각형 갯수 세기 먼저 드래곤 커브를 구현 하겠습니다. 위의 그림을 통해 설명하겠습니다. 1세대에서 2세대로 넘어갈 경우, 1세대의 움직임에서 반시계 방향으로 90도 움직인 방향으로 먼저 움직인 뒤, 1세대의 방향으로 움직입니다. 2세대에서 ..

문제 링크입니다. https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 삼성 SW 역량테스트 기출 문제입니다. 까다로운 기출문제 였습니다. 문제에서 구현할 것은 물고기의 움직임 + 상어의 움직임 입니다. 물고기가 움직일 때는 조건이 있습니다. 먹힌 물고기가 아니며, 이동한 칸이 상어가 있는 곳이 아닐 경우에만 이동할 수 있습니다. int map[5][5]; // 상어가 위치한 칸은 -1이다. info info_fish[17]; in..

문제 링크입니다. https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 삼성 SW 역량테스트 기출문제입니다. 정렬을 한 뒤의 MAP의 저장이 중요했습니다. 정렬을 하는 기준은 수의 등장횟수(오름차순)이며, 등장횟수가 같다면 수가 커지는 순서로 정렬을 하면 됩니다. 예를 들어, (3 , 3 , 2 , 1 , 2) 가 있다고 했을 때, (1 , 1 , 2 , 2 , 3 , 3)으로 정렬이 됩니다. 행의 갯수가 열의 갯수보다 많거나 같을 때에..

문제 링크입니다. https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 재귀를 사용하는 문제였습니다. 답이 나오는 과정입니다. 1. map을 한번 확인해본다 1-1. map이 0이나 1로만 모두 차있다면 해당 값을 출력합니다. 1-2. 위의 경우가 아니라면 map을 4개로 나눈뒤 (를 출력합니다. 2. 4개로 나뉜 map을 다시 확인해봅니다. 3. 1~2과정을 반복한뒤, 확인이 끝날때마다 )을 출력합니다. 1. map을 확인하는 과정 v..

문제 링크입니다. https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 구현 능력을 물어보는 문제였습니다. 블럭을 조건에 따라 움직였을때 어느턴에서 끝나는지를 물어보는 문제입니다. 1. 블럭이 움직이는 조건(움직이려는 블럭이 맨 밑에 있을 경우에만 이동이 가능합니다) 1-1. 흰색칸일 경우 -> 해당 칸으로 이동합니다. 이미 말이 있는 경우는 X번 말 위의 말이 모두 이동합니다. ex) 1 2 3 4 5 -> 1 2 / 3 4 5 1-2. 빨간칸일 ..