알고리즘
-
BOJ) 연구소알고리즘/백준 2020. 7. 2. 16:09
연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 풀이 배열 복사 문제로 고생을 조금 했다. 바이러스가 퍼지는 부분을 갱신할 때, 기존 MAP에 덮어 씌우면 답과 거리가 멀어지기 때문이다. 왜냐하면, char[][] map은 dfs에 계속 이용이 되기 때문에.. 다른 값들에 영향을 미친다. 배열 복사 이후에 바이러스가 퍼지고, 안전 구역을 탐색하니까 답을 맞출 수 있었다. 일단 3번 답을 구했는데, 첫번째로 구했던 답은 LinkedList를 이용하는 것이었다. 바이러스를 퍼뜨릴 때, LinkedList를 이용해서 B..
-
BOJ) NM과 K (1)알고리즘/백준 2020. 7. 2. 15:56
NM과 K (1) 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접� www.acmicpc.net 풀이 N x M의 격자판에서 k개를 선택하여, 해당 칸의 수를 더했을 때 최대 값이 되는 경우를 찾는 문제다. 또한 k 개를 선택할 때, 특정 좌표의 상하좌우로 인접해있으면 안된다는 조건이 있었다. 두 조건에 따라서 코드를 짜내려갔다. 방문체크를 하면서, 방문한 적이 없는 경우 상하좌우를 체크해주고, 선택이 가능한 경우면 sum에 더해서 다시 탐색하도록 했다. k 개 만큼 선택을 했을 때, 최대 값을 비교하면서 최신화 해주며 답을 구..
-
BOJ) 계란으로 계란치기알고리즘/백준 2020. 6. 30. 15:01
계란으로 계란치기 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 이 문제가 너무 좋은 점은, 테스트 케이스가 충분히 주어졌기 때문이다. 그래서 그런지 정답 비율이 꽤나 높다. 문제가 제시한 조건을 살펴보면, 계란이 일렬로 나열되어있고 가장 왼쪽 계란부터 오른쪽 끝까지 순차적으로 들어서 계란판에 있는 다른 계란을 내려 치는 것이다. 두 계란의 내구도는 각각 상대 계란의 무게만큼 감소하게 된다. 한번 내리친 다음에, 손에 들고있던 계란을 내려놓고 다음 계란을 든다. 이때, 조건이 손에 쥔 계란..
-
BOJ) 뱀과 사다리 게임알고리즘/백준 2020. 6. 30. 14:48
뱀과 사다리 게임 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 풀이 이 문제는 BFS를 활용해 푸는 것이 효율적인 문제다. 딱히 어려운 점은 없었지만, 어이없이 두 번 실수한 부분이 있었다. 첫번째는 while을 통해서 입력받을 때다. for문을 두 번 쓰자니 번거로울 것 같아서 while로 한번에 받으려고 조건을 넣었었는데, 바보같이 or( || ) 조건이 아니라 and( && ) 조건을 걸었었다. 그리고, 처음 시작하는 좌표가 문제에서 1부터라고 제시돼 있었..
-
BOJ) 두 동전알고리즘/백준 2020. 6. 29. 16:05
두 동전 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, �� www.acmicpc.net 풀이 블로그에 올리기 창피한 코드지만, 기록을 먼저 해두고 나중에 다시 풀고자 올린다. 브루트 포스를 제대로 사용했다기 보다, 시뮬레이션 문제로 인식하고 풀었기 때문에 메모리와 시간 효율성이 현저히 떨어진다. 그래도 로직을 설명하자면, 입력을 받을 때 먼저 두 동전의 위치를 저장했다. 그리고 해당 동전을 step에 따라 돌면서, 10을 초과하면 -1을 출력하고 10 이하에서 동전이 하나 남는 경우는 step을 출력했다. 동전을 이동시킬 때는, 범위..
-
BOJ) 이모티콘알고리즘/백준 2020. 6. 29. 15:56
이모티콘 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만�� www.acmicpc.net 풀이 푸는데 시간이 조금 걸렸다. 처음에 풀었을 때는 n이 300정도 이상일 때, 시간이 너무 오래걸려서 가지치기를 계속 해줬다. 그래서 700정도까지는 통과할 수준으로 나올 수 있는데, 1000까지는 도저히 무리였다. 이 때는, visit을 이용하지 않았다. 굳이 필요 없었다고 생각했다. 하지만, visit변수를 만들어야겠다는 생각을 했고, screen에 표시된 스마일 갯수에 대해서만 visit을 체크해줬다. 그렇게 하니까 몇가지 경우에서 틀린 답이 ..
-
BOJ) 1,2,3 더하기알고리즘/백준 2020. 6. 29. 15:49
1,2,3 더하기 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net 풀이 브루트 포스 문제로 입력값 n을 1, 2, 3 숫자의 합으로 나타낼 수 있는 경우의 수를 구하는 문제다. 또한, 순서가 있기 때문에, 1+1+2 와 1+2+1은 다른 것으로 간주한다. 예전에 풀었던 문제인데, 기억에 남아있지 않아서 새롭게 풀었다. 먼저, 예전에 풀었던 방식은 점화식을 통해서 답을 찾았었다. dn = dn-3 + dn-2 + dn-1 이라는 식이 나와서..
-
BOJ) 로마 숫자 만들기알고리즘/백준 2020. 6. 26. 15:51
로마 숫자 만들기 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 풀이 Brute force 문제를 푼지 오래된 것 같아서 도전했다. n=20이기 때문에, 통과하려면 가지치기를 어떻게 해야하나 많은 고민을 해봤다. 질문 탭에도 게시글이 몇 개 없어서, 참고할 수도 없었다. 그래서, 처음 선택한 방법은 로마 숫자 1,5,10,50을 n만큼 2차원 배열을 만들어서 각 숫자가 0~n까지 반복하면 만들어지는 숫자를 저장했다. 이후에, 해당 숫자를 선택하면서 count를 i개 씩 줄여줬는데, 고작 해봐야 13 -> 14 정도까지만 구할 수 있었다. 어떻게 해야하나 고민하다가 Set에서 visit으로 바꿔주었다. 어차..