알고리즘
-
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으로 바꿔주었다. 어차..
-
BOJ) 숨바꼭질알고리즘/백준 2020. 6. 26. 15:45
숨바꼭질 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 풀이 가장 빠른 step에서 위치를 찾아야하기 때문에, step에 따라 우선순위 큐를 이용해야한다고 생각했다. 그래서 class spot을 만들어서 Comaparable을 implement해서 사용했었는데, 63%에서 계속 틀렸다. 설마 step에 따라서가 아닌가 싶어서 Queue로 바꿔서 제출해봤는데 63%에서 틀렸다. 결론은, 로직 자제가 틀렸던 것이다. 더불어, 우선순위 큐가 필요가 없던 것이다. 우선순위를 체크안해도 된..