백준알고리즘
-
[BOJ - 12886] 돌 그룹백준알고리즘 2020. 2. 27. 00:39
https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다. 강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다. 크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 www.acmicpc.net 문제 논리자체는 딱.. 그 세자리 숫자에 관한 Memoization을 통해 BFS를 써주면되겠다! 라는 생각이들지만, 이러한 생각은 문..
-
[BOJ - 16933] 벽 부수고 이동하기3백준알고리즘 2020. 2. 27. 00:30
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 벽부수고 이동하기 4처럼 조금 이전 시리즈들과 다른문제는아니나, 하나 추가된것이 낮과 밤이라는 조건이 추가가됬다는것이다. 구조체를 구성하고, 낮과 밤일때 매커니즘을 다르게 만들어서 BFS를 진행했고 특이한점이 한가지 있다면, 밤일때 이동하고자 하는벽이 있는상태에 아직 벽을뚫을수 있다면 그자리에서 한턴기다리는 방식을 선택했다.
-
[BOJ - 16946] 벽 부수고 이동하기 4백준알고리즘 2020. 2. 27. 00:14
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다. www.acmicpc.net 이 문제에 대한 가장 간단하고 전형적인 완전탐색 방법은 모든 벽에서 모든 빈공간을 탐색해나가는 것이라고 생각했다. 하지만, 최대 벽의 개수가 1000x1000개인 100만개정도의 숫자가되는데, 이러한..
-
[BOJ - 14500] 테트로미노백준알고리즘 2020. 2. 24. 02:40
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 작년에 진짜 자바에서 빡구현으로 풀었던 문제다. 빡구현을 통해 속도를 챙길수 있지만, 코드작성 시간효율 측면에서 굉장히 비효율적이라..
-
[BOJ - 18429] 근손실백준알고리즘 2020. 2. 14. 17:10
https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 감소하게 된다. 따라서 운동을 하지 않고, 가만히 있다면 매일매일 중량이 감소할 뿐이다. 다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할 지는 마음대로 결정할 www.acmicpc.net 배열크기가 극도로 작아서, 재귀로 풀수있는 쉬운문제다.
-
[BOJ - 4217] 신성 문자백준알고리즘 2020. 2. 14. 17:08
https://www.acmicpc.net/problem/4217 4217번: 신성 문자 문제 고고학자는 초기 문명을 이해하기 위해서 고대 언어로 된 글을 공부하기도 한다. 이집트는 3000년전에 각종 동물이나 사물, 신체의 모습을 본딴 고대 언어 "신성 문자"를 만들었다. 이 문제에서, 아래와 같은 글자 여섯개를 인식하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 하나 또는 그 이상의 신성 문자를 포함하는 그림으로 이루어져 있다. 그림은 1 또는 0으로 이루어져 있고, 1은 검정 픽셀, www.acmicpc.net 디코딩 -> BFS를 통한 Flood Fill -> 안에있는 구멍 개수에 확인 이후, 그에 따른 문자열 담기-> 출력
-
[BOJ - 14632] 고급 작품백준알고리즘 2020. 2. 14. 17:06
https://www.acmicpc.net/problem/14632 14632번: 고급 작품 첫째 줄에 도화지의 세로 크기 N과 가로 크기 M이 주어진다. (1≤N,M≤1,000) 둘째 줄에 도장의 수 K가 주어진다. (1≤K≤500) 그다음 줄부터 도장의 크기와 모양이 K개 주어진다. 한 도장마다 도장의 크기 H, W가 주어지고, 다음 줄부터 H 줄에 걸쳐 도장의 모양이 주어진다. (1≤H,W≤500) 도장은 1번부터 K 번까지 번호가 매겨져 있다. 그 다음 도장을 찍는 좌표의 개수 Q 가 주어진다. (1≤Q≤10,000) 그 다음 줄 부터 Q www.acmicpc.net 단계별로 전부다 칠해서 해결했다. 그런데, 자료형을 쓰는것에 따라 많은시간 차이가나는데, 벡터에 저장한 이후 프로그램을 진행하는것보..
-
[BOJ - 17779]게리맨더링2백준알고리즘 2020. 2. 9. 16:44
https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다 www.acmicpc.net 게리멘더링2, 2019년 하반기 삼성 오전 역량평가 테스트 문제라고한다. 일단.. 풀면서 가장많이 생각난 문제는 SWEA 모의 ..