알고리즘
-
BOJ) 욱제는 결정장애야!!알고리즘/백준 2020. 6. 18. 18:17
욱제는 결정장애야!! 14646번: 욱제는 결정장애야!! 욱제는 매일 세계사에 한 획을 그을만한 심각한 비결정론적 문제에 직면한다. 그렇다. 바로 저녁메뉴를 고르는 것이다. 매일 반복되는 중대한 선택에 지친 욱제는 N일 동안의 저녁메뉴를 미리 �� www.acmicpc.net 풀이 처음으로 시도했던 방법은 반환될 정답을 N으로 초기화하고, ArrayList에 메뉴를 넣으면서, 이미 들어가 있는 메뉴인지 아닌지 판단해서 정답을 1씩 빼주는 것이었다. 하지만, 시간초과가 뜨면서 ArrayList의 contains를 사용하기에는 비효율적이라는 것을 알게되었다. 그래서 배열로 선언해서 메뉴가 나온 횟수를 늘려가기로 했다. 돌림판을 돌릴 때마다, 메뉴에 해당하는 인덱스를 1 증가시켜주었고, 1인 경우 스티커가 붙..
-
BOJ) 대출 요청알고리즘/백준 2020. 6. 18. 18:12
대출 요청 16497번: 대출 요청 도서관에서 어떤 책을 K권 보유하고 있고, 이 책에 대한 대출 관리를 담당하고 있는 관리인이 있다. 이 관리인은 월 별로 한 번씩 대출 요청 건들을 취합하여 처리한다. 한 예약 요청은 대출 날짜 www.acmicpc.net 풀이 쉽게 풀 수 있는 문제였지만, 범위 설정에서 실수를 해줘서 수정을 했다.. ㅠ 일단, 주어진 날짜의 범위가 1~31일 사이이고 N과 K가 1~100 사이의 숫자기 때문에 날짜 배열을 통해 풀어주었다. (가장 숫자가 적기도 하고, 날짜에 따른 대출 여부기 때문에, 적절하다고 생각한다.) 특정 날짜 인덱스에 최대한으로 필요한 책의 권수를 구하고, K 이하라면 대출 가능, 아니라면 불가능하다는 식으로 풀었다. 1일부터 31일까지 담을 수 있는 dat..
-
BOJ) 대회 개최알고리즘/백준 2020. 6. 18. 18:04
대회 개최 12915번: 대회 개최 첫째 줄에 E, EM, M, MH, H가 주어진다. (0 ≤ E, EM, M, MH, H ≤ 100,000) www.acmicpc.net 풀이 한 번의 로직 수정 후에 통과했다. 처음에는 단순하게, E,M,H를 모두 더한 평균 값을 구해서 EM과 MH에서 나눠주면 쉽게 구하지 않을까 생각했다. 하지만, 반례가 있음을 확인했고 아래 코드와 같이 수정했다. 주먹 구구식 코드를 싫어하지만, 달리 방법이 떠오르지 않았다. 그래서, E M H에서 각각 하나씩 제거하면서 가능하면 count를 세주고, 만약 불가능한 경우 E -> EM에서, M -> EM, MH 에서, H -> MH 에서 하나씩 제거 가능한지 여부를 확인해주었다. 가능하면 count를 세주고 아니면 반복문을 종료...
-
BOJ) 방법을 출력하지 않는 숫자 맞추기알고리즘/백준 2020. 6. 18. 15:25
방법을 출력하지 않는 숫자 맞추기 13392번: 방법을 출력하지 않는 숫자 맞추기 아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10� www.acmicpc.net 풀이 매우 어려웠던 문제였다. DP를 이용하는 문제이고, left와 right를 각각 저장하면서 진행해야한다는 것까지는 눈치를 챘다. 하지만, 계속되는 오답과 시간초과에 멘붕이 왔다. 다른 분들의 풀이를 참고하기로 했다. 저장하는 DP를 이동 뿐만 아니라, 큐브의 숫자인 0~9에 대해 저장해주는 것이었다. 이에 대해 이해하기는 했지만, 가까운 미래까지는 이 생각에 도달하지는 못할 것 같았다. 그래서, 이..
-
-
BOJ) 자동차경주대회알고리즘/백준 2020. 6. 18. 15:05
자동차경주대회 2651번: 자동차경주대회 첫째 줄에 정비소에서 정비하는데 걸리는 총 정비 시간을 출력한다. 둘째 줄에 방문하는 정비소의 개수를 출력한다. 셋째 줄에는 방문하는 정비소의 번호를 한 줄에 차례로 출력하며 정비소 번� www.acmicpc.net 풀이 이 문제는 DP를 활용해서 풀었다. 정비소의 위치와 걸리는 시간을 담을 배열을 각각 선언해서 값을 저장해줬다. 이 때, 출발 지점인 0과 도착 지점인 마지막 위치도 같은 배열에 저장해서 도로의 출발점과 도착점까지 탐색하도록 설정했다. 각 정비소를 들르면서, 이전까지 최대 이동거리인 maxDist안에 있는 정비소를 찾아 걸리는 시간의 최소값을 구했다. 해당 정비소가 최소 시간을 만족하기 때문에, 걸리는 시간을 더해주면서 마지막 도착지점까지 시간이 ..
-
BOJ) 다음수알고리즘/백준 2020. 6. 13. 20:28
다음수 4880번: 다음수 문제 등차수열(AP)은 인접한 두 수의 차이(공차)가 일정한 수열이다. 예를 들어, 3, 5, 7, 9, 11, 13, ...은 차이가 2로 일정한 등차수열이다. 이 문제에서 등차수열의 공차는 항상 0이 아닌 정수이다. 등 www.acmicpc.net 풀이 이 문제도 복잡하게 생각할 것 없이 간단하게 풀었다. 주어진 숫자들이 등차수열인지 등비수열인지 판별하고, 그 다음 수를 AP num 또는 GP num으로 출력을 해주는 것이기 때문에 판별 메소드를 구해야하나 생각했었다. 하지만, 주어진 숫자의 범위가 |numbers| < 10000 로 매우 협소하고, 다음 숫자를 구해야 하기 때문에 그냥 둘 다 돌리기로 선택했다. 등차수열인지 판별하고 맞다면 다음 수를 담아서 출력하는 isA..
-
BOJ) 빗물알고리즘/백준 2020. 6. 13. 20:22
빗물 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치� www.acmicpc.net 풀이 문제를 처음 맞이했을 때 생각한 것 보다는 꽤나 신경을 써야하는 문제였다. 먼저, 배열을 사용하지 않고 입력받은 값에 대해 구간의 max값을 구해줘서 답을 내주려고 했었다. 0으로 시작하는 구간이나 마지막 값이 0이면 빗물이 생성되지 않는다는 조건 때문에 포기했다. 그래서 배열을 만들고 위의 로직을 시도해볼까 했는데, 너무 복잡해지는 것 같아서 포기했다. 마지막으로 떠올린 것은, 한 구간에 대해 양 옆에 제일 높은 기둥 두개를 찾는 ..