코테
-
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) 숨바꼭질알고리즘/백준 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%에서 틀렸다. 결론은, 로직 자제가 틀렸던 것이다. 더불어, 우선순위 큐가 필요가 없던 것이다. 우선순위를 체크안해도 된..
-
BOJ) 요세푸스 문제알고리즘/백준 2020. 6. 25. 17:14
요세푸스 문제 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 쉽게 봤던 문제였는데, 푸는데 약간의 시간이 들었다. 이미 테이블에서 빼낸 사람을 건너 뛰면서 k번 째 사람을 빼내야 하는 문제에서, 여러 명이 빠져있는 경우에 새롭게 빼내야하는 사람을 어떻게 구해야하는지 생각하는데 시간이 조금 걸렸다. 그래서 결국, k번 째 까지 갈 때, 이미 빠져있는 사람이 있으면 총 가야하는 횟수에 +1을 증가시키면서 자리를 탐색했다. 맞기는 했지만, 배열을 이용해서 하니까 탐색 시간이 너무 많이 걸렸다. 그래서 List로 바꿔서 풀어보기로 했다. List에서 k번 째 있는 사람을 빼내는 동시에 list에서 제..
-
BOJ) 손익분기점알고리즘/백준 2020. 6. 25. 17:09
손익분기점 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net 풀이 최근 제출된 문제에 많이 떠서, 문제를 몇 번 대충 봤는데 단순한 수식문제라 안풀려고 했다. 하지만, 오늘 정답 비율을 봤는데 23% 정도밖에 되지 않아서 뭔가 다른 생각해야하는 점이 있지 않을까 싶어서 풀어봤다. 손익분기점을 구하는 수식은 Price*N > 고정 비용 + 가변 비용 *N 이라는 식이 나온다. Price*N = 고정비용 + 가변비용*N 으로 부터 나온 N에 +1을 해주면 답이 된다는 말이다. 답을 구해야하는 N에 대해 모두 이항시키면,..
-
BOJ) 01타일알고리즘/백준 2020. 6. 25. 17:04
01타일 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 풀이 처음 문제를 봤을 때는 순서를 모두 구해주어야 한다고 생각했다. 그래서 처음 로직은 for문을 돌리면서 0타일이 n이하까지 2개씩 증가시키면서, 1타일은 n-0타일의 수 를 통해 각각 타일의 수를 구해주었다. 그리고 0타일은 2개를 1개로 인식해야하기 때문에, /2를 해주었다. 0타일의 갯수 : ZERO 1타일의 갯수 : ONE total = ZERO + ONE 위의 변수를 가지고 따지면, total! / ZERO! / ONE! ( ! = 팩토리얼)..
-
BOJ) 소수 구하기알고리즘/백준 2020. 6. 24. 17:08
소수 구하기 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 소수를 구하는 문제를 풀어본지 오래돼서 에라토네스의 채 자체를 망각하고 있었다. 그래서 GCD를 통해 풀어야하나 생각하다가, 소수를 구하는 알고리즘이 있나 찾아봤다. 에라토네스의 채를 보고 존재가 다시 떠올랐다. 구현하는 방법은 까먹어서 방법을 익히기로했다. 1은 소수에 포함되지 않기 떄문에 2부터 시작하고, j에 해당하는 부분은 자신의 배수에 대해 표시를 해주는 것이다. 이후에, for문을 돌면서 소수를 찾아 출력해줬다. 하지만, for문을 다시 도는 부분이 불필요하다고 느..
-
BOJ) 카드알고리즘/백준 2020. 6. 24. 16:57
카드 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 풀이 문제를 보고 바로 떠오른 방법은 Map을 이용해서 푸는 방법이었다. Map을 통해 해당 카드가 몇 번 나왔는지 카운트 한 다음, value를 통해 key를 정렬하는 방법이다. 문제의 조건에 따라, 나온 횟수가 같은 경우에는 카드의 숫자가 최소인 것부터 정렬해서 리스트의 가장 앞 부분에 있는 값을 리턴했다. 바로 맞기는 했지만, 효율이 너무 좋지 않았다. 메모리와 속도 측면도 그렇고, Map을 사용하지만 어차피 Key값을 저장하기 위해서 List를 ..