본문 바로가기

알고리즘40

[백준 10610번 30] 오늘의 문제는 30이다.  처음엔 무조건 완전탐색! 문제를 읽고 N의 범위가 10만 자리 양수..? 를 보고 헉..! 했지만 이어 고민을 시작했다.30의 배수가 되려면 어떤 조건이 필요할까?30은 일단 3 * 10 이란 생각을 했다.그리고 학교를 다닐 때, 3의 배수 조건이 있었던 것을 기억해 냈다..!물론 그 내용은 검색해 보았다.. 너무 오래돼서 까먹었,, 크흠아무튼 3의 배수 조건은 모든 자리 수의 합이 3이 되면 3의 배수이다.그렇다면 N의 모든 자리를 한 번씩 확인하며, 각 자리가 어떤 수 인지 저장하고0이 1개 이상 있는지, 모든 자리 수의 합이 3의 배수인지만 확인하면 된다. 코드는 다음과 같다.( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )( 초기화는 "Ct.. 2025. 1. 6.
[백준 15996번 팩토리얼 나누기] 오늘의 문제는 팩토리얼 나누기이다.  처음엔 무조건 완전탐색!N의 범위가 int범위 끝이니 약 21억쯤으로 1부터 최대범위까지 탐색하며될 때마다 세준다면 필연적으로 시간초과가 날 것이다. 고민 끝에 알아낸 것은?모든 수를 확인할 필요 없이 A가 N까지 모든 수 중에몇 개가 포함되어 있나? 였다. 예를 들어, N = 10이라면2, 4, 6, 8, 10에 각각 1, 2, 1, 3, 1개씩 2가 들어있고,이는 N까지의 모든 2의 제곱수(문제의 A의 제곱수)로 N을 나누고그 수를 ans에 모두 더해주면 끝이다! 방금 얘기한 N = 10인 경우,10 / 2 = 510 / 4 = 210 / 8 = 1(나눈 값이 int자료형인 것에 유의하자!)합하면? 8! 예시를 한 가지 더해보자,N = 15, A = 3인 경우15.. 2025. 1. 5.
[백준 7696번 반복하지 않는 수] 오늘의 문제는 반복하지 않는 수이다.  처음엔 무조건 완전탐색! 처음엔 완전탐색으로 while문을 통해 모든 수를각 자릿수를 그때그때 따로 파악하여 출력을 해줬다.그 결과는 메모리 초과였다. 고민을 해본 결과 1부터 최대 n범위인 1백만까지 각 수에 해당하는n번째 반복 숫자 없는 수를 미리 구하고요구하는 수마다 해당하는 수를 출력해 주면 되는 것이었다. 코드는 다음과 같다.( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" ) import java.util.*;import java.io.*;public class Main{ static int [] ans = new int [1000010]; /.. 2024. 12. 31.
[백준 31589번 포도주 시음] 오늘의 문제는 포도주 시음이다.  처음엔 무조건 완전탐색!완전탐색으로 문제를 풀이한다면, N개의 포도주 중에 K개를 선택하여 모든 순서를고려하며 마셔본 맛을 하나하나 대소판별해 주면 답이 나온다! 하지만 입력의 범위를 보았을 때, 시간 초과가 나올 것이 확실하니 최적화를 고민해 보았다. 일단 가장 큰 결괏값이 나오려면 어떤 조건을 가져야 하는지 생각해 보았다.가장 맛있는(T가 가장 큰) 포도주를 먼저 마시고,가장 맛이 없는(T가 가장 작은) 포도주를 마시는 것을반복하는 방법이 맛의 합의 최댓값이 되는 방법이라 생각했다. K개를 선택해야 하는 부분은 전체 맛들을 정렬 해줌으로써 생략해도 되게 만들었다.그 결과 맞았습니다! 코드는 다음과 같다.( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 .. 2024. 12. 17.
[백준 1735번 분수 합] 오늘의 문제는 분수 합이다.   처음엔 무조건 완전탐색! 완전 탐색으로 문제를 풀이하면결과의 분자는 ( 분자 1 * 분모 2 ) + ( 분자 2 * 분모 1 )분모는 ( 분모1 * 분모 2 )로 계산하고 1 ~ 분모의 수에 도달할 때까지 나뉘는 수가 있다면 나누고, 없다면 끝내면 될 것이다. 이를 좀더 효과적으로, 결과의 분자와 분모는 똑같이 구하고최대공약수를 유클리드 호제법으로 구하여 각 분자와 분모를 나누어 최종 답안을 찾아주었다! 코드는 다음과 같다.( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )import java.util.*;import java.io.*;public class Mai.. 2024. 12. 4.
[백준 13241번 최소공배수] 오늘의 문제는 최소공배수이다.  처음엔 무조건 완전탐색! 완전 탐색이야 당연히 두 수 모두에게 나누어지는 수가 나올 때까지 1씩 더하는 방법이겠지만이를 최적화하기 위한 방법을 한번 고민해 보았다.나의 결론은 무작위 두 수 a, b의 곱 / (중복되는 수 = 최대공약수)라고 생각하였다. 그래서 두 수를 "유클리드 호제법"을 통하여 최대공약수를 구해주고(a * b) / 최대공약수 로 답을 도출해 보았다. 코드는 다음과 같다.( 코드가 너무 커보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )import java.util.*;import java.io.*;public class Main { public static .. 2024. 12. 4.
[백준 3190번 뱀] 오늘의 문제는  뱀이다.   처음엔 무조건 완전탐색! 시간제한과 입력의 범위를 보아하니 시간적으로는 문제가 없을 것 같았다.구현을 어떻게 하는가가 이번 문제의 관건!일단 사과의 자리를 표현해 줄 map [ ][ ]과 뱀의 존재유무를 따질 visited [ ][ ]를 생각했고,뱀의 꼬리자리좌표를 ed[ ], 머리좌표를 st [ ], 뱀이 지나간 곳을 담아줄 Queue q 정도 생각했다.또한 걸린 시간(답안)을 sec배열에 담아주었고 방향을 dr [ ], dc [ ], way(인덱스용)으로 파악해 주었다.뱀의 방향은 idx와 시간 arr, 방향 arr 이렇게 3가지로 파악 및 갱신해 주었다. 글을 읽고 구현을 시작했다!코드는 다음과 같다.( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보.. 2024. 11. 28.
[백준 10844번 쉬운 계단 수] 오늘의 문제는 " 쉬운 계단 수"이다.  #고민의 흐름처음엔 무조건 완전탐색! 어떤 규칙이 있을까 처음부터 고민을 하기 시작했다.메모장을 켜고 N = 1부터 3 정도까지 ,, 생각을 하다 보니 끝자리가 0, 9인 경우만 계단수가 (-1 || +1) 1개만 발생하고1 ~ 8까지는 (-1 && +1) 2개가 발생한다. 오랜만에 종합장을 펴고 이것저것 적어보다 결국 해법을 찾아내었다!그림과 함께 보자.  위 사진은 종합장에 내가 적어둔 숫자들이다.끝자리가 0 ~ 9까지인 수들이N =? 에 따라 몇 개씩 존재하는지 적어줬다.여기에서 규칙을 찾아볼 수 있다.예를 들어, N = 3인 경우 끝자리가 2인 수가 왜 3개냐면,어쩌면 당연하게도 N = 2일 때 끝자리가 1, 3인 수들의 총개수가 3개이기 때문이다. 그렇다.. 2024. 9. 13.
[백준 15486번 퇴사 2] 오늘의 문제는 " 퇴사 2"이다.  #고민의 흐름처음엔 무조건 완전탐색!  오늘의 DP문제 ~문제를 보아하니 150만까지의 날짜수를 했을 때, 안 했을 때를 나눠서 다계산해주면필연적으로 시간초과가 날수밖에 없다고 생각했다.결국 어떠한 규칙을 찾아 나날이 가장 최선의 값을 가지며,그게 뒷날짜에도 최선을 보장할 수 있도록 기록을 해나가야 하는 거 같은데 ,,, 일단, 시간초과지만 고민하다가 처음 생각해 냈던 방법은 다음과 같다. 1. 해당 날짜로부터 소요 날짜만큼 계산했을 때 상담 가능 / 불가능 체크한다.2-1 불가능시 무시 후 다음 날짜 1로.2-2 가능시 dp [해당 날짜] = dp[해당 날짜] + 해당 날의 금액3. dp [해당날짜 + 해당날의 상담시 소요날짜]와 2-2에서 갱신된 dp[해당 날짜]를.. 2024. 9. 11.