본문 바로가기

C++

 (9)
[백준 2309] 일곱 난쟁이 (c++) https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 이 문제는 아홉 난쟁이들 중 7명을 뽑아(조합)하여 키의 합이 100인 경우를 찾는 문제입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include #include using namespace..
[백준 23291번] 어항 정리(C++ 풀이) https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 더보기 우선 NxN 형태의 2차원 벡터를 이용하여 어항의 배치를 표현하였으며, 어항이 존재하지 않는 좌표는 -1로 표현하였다. 그리고 문제에서는 어항이 위로 쌓이게 되지만 편의상 배열의 아래로 쌓이도록 표현하였다. 따라서 위 그림을 배열로 표현하면 다음과 같다. 코드 상에서는 board라는 변수를 사용한다. 1 2 3 4 5 6 7 8 -1 -1 3 14 9 3 11 8 -1 -1 3 5 -..
[백준 2638번] 치즈 (C++ 풀이) 2638번: 치즈 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 더보기 더보기 치즈의 "외부 공기"와 "내부 공기"를 BFS로 판단한 후 각 치즈의 상하좌우의 값을 확인하여 녹일 치즈를 정한다. 다음은 findAirStatusBFS()는 BFS를 이용하여 외부 공기를 판단하는 함수 // BFS를 이용하여 외부공기 판단 void findAirStatusBFS() { queue q; used = vector(N, vector(M, false)); q.push(make_pair(0, 0)); /..
[알고스팟] 시계 맞추기(C++) 문제 설명 더보기 https://www.algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 www.algospot.com 예제 입력 2 12 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12 12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6 예제 출력 2 9 풀이 더보기 우선 스위치에 링크된 시계들을 다음과 같이 정의합니다. vector linkedClocks = { ..
[백준 16234번] 인구이동(C++) 풀이 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 더보기 복잡한 2차원 영역을 1차원으로 변환한 후 bfs 알고리즘을 이용하여 문제 해결하였습니다. 위 사진 처럼 각 국경선이 열린 경우 점선으로 표시가 되는데 이를 나타내기 위해서 2차원 영역을 1차원으로 변환하는 게 좋다.(구현이 가능하지만 복잡해지기 때문에) 각 2차원 좌표에 차례대로 번호를 붙여 1차원 좌표로 변환한다. 2차원 좌표를 1차원 좌표로 변환하는 코드는 다음과 ..
[Algorithm] 보글(Boggle) 게임 문제 (C++) 다음 도서를 참고하여 작성하였습니다. http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9788966260546 알고리즘 문제 해결 전략 세트 - 교보문고 이 책은 프로그래밍 대회 문제를 풀면서 각종 알고리즘 설계 기법과 자료 구조에 대해 배우고, 나아가 문제 해결 능력까지 키울 수 있도록 구성되어 있다. 각 장에는 독자가 스스로 프로그램을 www.kyobobook.co.kr 문제 보글 게임은 다음과 같이 5 x 5 크기의 알파벳 격자를 가지고 하는 게임입니다. 목적은 상하좌우/대각선으로 인접한 칸들의 글자를 이어서 단어를 찾아내는 것입니다. 예를들어 위의 그림에서 (b), (c), (d)는 각각 PRETTY..
[백준 18352번] 특정 거리의 도시 찾기(C++) 문제 출처 www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 더보기 문제에서 조건이 될만한 내용을 파란색으로 표시하였습니다. 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 ..
[백준 20057번] 마법사 상어와 토네이도(C++) https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 문제 더보기 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다. 토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 ..
[프로그래머스][C++] 크레인 인형뽑기 게임(카카오 2019 개발자 겨울 인턴십 문제) 출처 : 프로그래머스 https://programmers.co.kr/ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 간단하게 설명하면 N * N인 배열에서 인형 뽑기 하듯 선택된 열에서 가장 높은 행의 값을 가져와서 바구니에 세로로 담는데 바구니의 맨 위에 있는 인형의 값과 새로 담는 인형의 값이 같은 경우 인형이 사라지게 된다. 사라진 인형의 갯수를 return 하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #includ..

티스토리툴바