알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 삼성 SW 역량 테스트 기출문제였습니다. 생각보다 귀찮은 구현 문제였습니다. 모래가 4방향으로 뿜어지는 것을 구현하는게 포인트였습니다. 토네이도가 어떻게 움직이냐에 따라서 모래의 움직임이 달라집니다. 4방향으로 움직임으로 저는 모두 만들었습니다. 1. 소용돌이 구현하기 void tornado() { int move = 1; int cnt = 1; ..

문제 링크입니다. https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 삼성 SW 기출문제 였습니다. 간단한 산수 문제였음으로 쉽게 풀 수 있었습니다. 먼저 한개의 강의실에는 한명의 감독관이 필요합니다. 따라서 B의 값보다 작은 강의실은 모두 1입니다. B의 값보다 큰 값을 가진 강의실의 경우, 보조 감독관이 필요합니다. 이때, 보조 감독관이 몇명 필요한지를 구해야합니다. 예시를 들어보면, 4..

문제 링크입니다. https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net BFS와 구현이 합쳐진 문제였습니다. 같은 색깔의 뿌요가 4개 이상인지를 찾은 뒤, 해당 뿌요들을 없앱니다. 그 뒤, 남아있는 뿌요를 아래로 내린 뒤, 다시 뿌요 그룹을 찾는 문제였습니다. 1. 같은 색의 뿌요 찾기 void puyo_boom(int a, int b, char c) { queue q; q.push({ a,b }); check[a][b] =..

문제 링크입니다. https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 삼성 SW 역량테스트 기출문제입니다. 문제 조건에 따라 구현만 하면 되는 문제였습니다. 1. 파이어볼 움직이기 typedef struct fire { int x; int y; int m; int s; int d; }fire; int dx[8] = { -1,-1,0,1,1,1,0,-1 }; int dy[8] = { 0,1,1,1,0,-1,-1..

문제 링크입니다. https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 삼성 SW 역량테스트 기출 문제였습니다. 그래프 탐색 + 구현 문제로 구현해야할 것이 많은 문제였습니다. 한 일반 블록에서 상하좌우로 접한 블록 그룹을 찾은 뒤, 조건에 따라 정렬을 합니다. 이때 블록 그룹에는 무지개 블록은 항상 포함 가능합니다. 크기 -> 무지개 블록 수 -> 기준 블록의 행 -> 기준 블록의 열 순으로 블록 그룹을 정렬하고 가장 큰 그룹을 제거합니다. 블..

문제 링크입니다. https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 삼성 SW 역량 테스트 기출문제 였습니다. 문제에서 주어진 조건대로 구현하면 풀 수 있는 문제였습니다. 구현 문제에 익숙하지 않으시다면 어려울 것 같습니다. 모든 경우를 탐색해야 함으로 DFS를 통해 확인했습니다. CCTV는 1번~5번까지 있습니다. 1번 -> 한방향 2번 -> 2방향(평행) 3번 -> 2방향(수직) 4번 -> 3방향 5번 -> 4방향 6번 -> 벽 M..

엄청 오랜만에 일상이네요..ㅎ 물론 전에 올린 것들은 전부 비공개로 했으니 처음보는 일상물일거 같네요 최근에 가장 중요한 일이라고 한다면 당연히 시험이겠죠..ㅠ 물론 공부는 하나도 안했지만..ㅎ(어떻게든 되지 않을까요...?) 사진 정말 잘나온거 같아서 기분 좋네요ㅎ 탑..? 어쨋든 저 탑이 제 자취방에서 조금만 걸어나오면 보입니다. 멀리서 보면 예쁘고 궁금했기에 언젠가는 가봐야겠다고 생각했는데, 드디어 가봤습니다. 근데 20분 내내 오르막길만 걸었습니다.. 그래도 도착한 뒤 봤을때는 후회없을 정도로 예뻤습니다. 야경은 덤이였고요. 가끔 기분 전환하고 싶을때 갈거 같습니다. 비록 잘찍진 못하지만, 풍경 사진을 잘찍는 방법은 좋은 장비인거 같습니다..ㅎㅎ 최근에 가장 중요한 일을 하나더 꼽자면 핸드폰을 바..

문제 링크입니다. https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net BFS를 이용한 문제였습니다. 기존 벽 부수기 문제와는 다르게 밤과 낮 기능이 추가된 문제였습니다. 따라서 저는 구조체를 이용해 queue에 현재 좌표, 벽을 부순 횟수, 이동 횟수, 밤과 낮을 저장해줬습니다. 해당 좌표를 방문했는지를 확인하는 check배열은 2차원 배열로 선언하면 안됩니다. 벽을 1번 부수고 (X,Y)에 도달할 수도 있으며,..

문제 링크입니다. https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net map과 string을 이용하면 간단하게 풀 수 있는 문제였습니다. N과 M의 범위가 100,000 이기에 pair를 사용해 다중 for 문을 사용하면 시간 초과가 생길 수 있습니다. 따라서 map을 이용해, 사이트 주소와 비밀번호를 저장한 뒤, 해당 사이트의 비밀번호만 출력할 수 있도록 해야합니다. 이를 생각하고 풀면 간단한 문제였습니다. 자세한 ..

문제 링크입니다. https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 문자열을 이용한 문제였습니다. "IOI" 를 확인하는 과정에서 다중 for문을 사용한다면 시간초과가 생기기에 다른 접근이 필요한 문제였습니다. 저같은 경우에는 IOI가 연속적으로 몇번 나오는지를 확인하는 방법으로 풀었습니다. 예제입력을 통해서 확인해보겠습니다. OOIOIOIOIIOII 해당 문자열이 주어졌을때, ..

문제 링크입니다. https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 간단한 그래프 문제였습니다. X -> Y 까지 가는데 거쳐가야하는 수를 구하는 문제였습니다. 예시를 통해 확인해보겠습니다. 7 -> 3 을 가는데 7 -> 2 -> 1 -> 3 으로 이동할 수 있습니다. 따라서 촌수가 3이 됩니다. M개의 line이 주어졌을때, X와 Y를 서로 양방향으로 저장해줍니다. 시작점을 queue에 넣어준 뒤, 갈 수 있는 점들을 확인..

문제 링크입니다. https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 재귀로 풀 수 있는 문제였습니다. 원리는 https://junseok.tistory.com/117 참고해주세요! 백준 2630 - 색종이 만들기(C++) 문제 링크입니다. https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 12..