알고리즘공부(Algorithm Study)78 백준 3036 - 링 JAVA 해당 문제는 엄청 쉬운 문제였다. 기약분수 -> 최대공약수 구하기 문제로 보면 편하다. 1. 첫 번 째 원을 한바퀴 돌리면 나머지 원도 첫 번째 원의 둘레만큼 돌아야 하는구나 2. 결국 기약분수로 표시하라는 것은 그냥 첫 번째 원 둘레 / 나머지 원 둘레겠구나 3. 기약분수는 최대공약수로 분자,분모를 나누면 되겠구나. 4. 유클리드 호제법으로 최대공약수 메서드 구현해야지! package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Boj_3036 { public static void main(.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 15. 백준 2981 - 검문 JAVA(feat. koosaga님) 해당문제는 한 15분 고민하다가 과감하게 구글링을 한 문제이다. 결국 유클리드 호제법을 사용하는 문제인데 그 전에 유도식이 존재한다. A와 B를 나눠서 나머지가 같다라는 말을 식으로 표현하자면 A = a*M + spare B = b*M + spare -> A - B = M * (a - b) 가 성립된다결국 M*(a-b)을 구하는 문제에 해당하므로 M*(a-b)의 약수들의 집합이 답이다. A, B, C가 있다면 A와 B의 M*(a-b)값과 B-C의 값인 M*(b-c)의 최대공약수(gcd)를 계속 구하여 그 최대공약수의 약수의 집합을 오름차순으로 나열하면 되는 문제이다. 유클리드 호제법의 경우 위키피디아를 보면 잘 나와 있으므로 참고하시라! https://ko.wikipedia.org/wiki/%EC%9C%.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 14. 백준 13305 - 주유소 JAVA package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Boj_13305 { public static void main(String[] args) throws NumberFormatException, IOException { //2 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 13. 백준 1541 - 잃어버린 괄호 JAVA 단계별로 풀기의 동적 계획법 1이 끝나고 맞이하는 그리디 알고리즘이다. 프로그래머스의 그리디 알고리즘 보면 난이도가 ㅎㄷㄷ하다. 그냥 뭔지 모를 때 거시기,, 그거 그거 있잖여 그리디 이거 그리디여라~라고 하면 다 그리디다 ㅠㅠ 해당 문제는 그리디라는 걸 이미 알고 풀어서 그런지 애초에 그리디하게 접근을 하였다. 문제 접하고 한 5분간 테케 1번이 왜 -35이지?라고 의문이 들었던 흑웁니다.. ㅜㅜ 1. 2, 3번 테케? 그럴 수 있지. 1번은 뭐지?? 2. 아! A-(B+C) 이런 식으로 괄호를 친거구나 3. 그렇다면 -가 나온 뒤에는 무조건 빼주면되지 않을까? 4. A-B+C+D-E+F = A-(B+C+D)-(E+F)가 되니까 그냥 -가 나온 뒤로는 빼준다고 생각하면 되겠다! 5. EZ해~ 6. 엌... 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 12. 백준 12865 - 평범한 배낭 JAVA 해당 문제는 DP의 대표적인 냅색(Knapsack-짐싸기)문제라고 한다. 하지만 본인은 1주일 동안 손을 대지 못하고 있었다. 왜냐하면 무게 W에 대해 중복된 가치를 가질 수 있는가에 대한 의문이 들었기 때문이다. 하지만 그건 기우였다. 중복된 가치가 되든 말든 상관이 없었다..! 드디어 동적 계획법 1까지 단계별로 풀기를 싹 밀었다! 하지만 5개월~6개월 전부터 시작해서 앞부분에 힘겹게 풀었던 것을 또 다시 풀라고 하면 풀 수 있을지는 의문이다. 내 머릿속의 지우개ㅜㅜ 이상한 소리 하지 않고 바로 문제 풀이/접근과정과 소스코드 공유하겠슴다. 1. 1 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 12. 백준 1912 - 연속합 JAVA 해당 문제는 손으로 끄적여가면서 풀다가 탁 깨달은 시점에서 술술 풀어나간 문제이다. 생각보다 매우 간단한 로직이지만 그동안 풀었던 문제들 + 단계별로 풀기 끝에 있다는 것을 감안해서 스스로 어려운 문제일 것이다라고 되뇌다가 시간이 오래 걸린 문제이다. -> "생각보다 쉬웠다"라는 뜻 1. n개의 정수, 1 1 + 2 가 최대고 -1,000일 때는 굳이 안 더해주는 게 나을지도? 3. 그렇다면 합한 수가 0보다 낮아지지 않는 시점까지는 연속합(누적합)을 해주다가 0보다 낮은 경우에는 그냥 연속합(누적합)에 넣는 것을 포기하고 다시 0보다 큰 수가 나오는 시점부터 합해주면 좋을 듯 하다. 4. 동시에 max값은 유지하면서 n번 째까지 다 돌았을 때의 max값이 답일 것이다. 일반적으로 입력을 받을 때 로직을.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 3. 백준 2565 - 전깃줄 JAVA 해당 문제를 처음 접했을 때는 점화식을 구하기 보다 구현으로 해결하려고 했었다. 그래서 아래와 같이 Comparator를 두 번이나 오버라이딩 해서 썼다. 하지만,,, 결과는 9퍼에서 틀림! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { // 전깃줄 .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 1. 백준 11054 - 가장 긴 바이토닉 부분 수열 - JAVA 바로 직전에 풀었던 백준 11053 문제의 응용편이다. 11053 풀땐 3시간이 걸렸지만 바로 응용해서 푸니 10분? 20분만에 푼 것 같다. 어쩐지 정답률이 높더라... 2022.03.31 - [알고리즘공부(AlgorithmStudy)/문제풀이(ProblemSolving)] - 백준 11053 - 가장 긴 증가하는 부분 수열 JAV 백준 11053 - 가장 긴 증가하는 부분 수열 JAV 쉬운 것 같아서 점화식 짜고 대충 구현해서 풀다가 3시간 만에 풀었던 DP문제다. 매 순간 긴장을 놓치면 안 된다는 것! 자만하면 안 된다는 것을 다시 한번 일깨워준 문제...! 시간 복잡도 계산 정 chaaany.tistory.com 1. 1부터 n까지는 오름차순인 증가하는 최장 수열 길이 찾아서 dp[n][0]에 할.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 31. 백준 11053 - 가장 긴 증가하는 부분 수열 JAV 쉬운 것 같아서 점화식 짜고 대충 구현해서 풀다가 3시간 만에 풀었던 DP문제다. 매 순간 긴장을 놓치면 안 된다는 것! 자만하면 안 된다는 것을 다시 한번 일깨워준 문제...! 시간 복잡도 계산 정확하게 안 하고 점화식은 몇 분만에 구하고 시간 복잡도 터질까봐 배제했던 코드가 답이었다!.. ㅜㅜ 2차원 배열 선언하고 Comparator 재정의해서 정렬하고... 별짓을 다했다 1. 1 n번쨰 까지의 최장 길이 수열 = n번째 수 > n-1 일 경우 n번째 수를 넣은 수열 or // 10 20 10 30 20 50 // O O X O X O // 8 6 9 1 4 6 7 4 3 7 4 7 2 5 2 10 1 // 1 1 2 1 2 3 4 2 2 4 3 4 2 4 2 5 1 // 8 // O // 8 6 /.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 31. 백준 2156 - 포도주 시식 JAVA 처음에 딱 보고??? 이거 계단 오르기 아닌가? 라고 생각 했지만 역시나 아니었다. 이유는 문제 풀이 과정에서! 1. 포도주 잔 선택 시 무조건 다 마셔야 함 2. 3잔 연속으로 놓여 있는 잔을 마실 순 없음 -> 연속 +1, +1은 불가 3. 1 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 29. 백준 10844 - 쉬운 계단 수 JAVA 해당 문제는 실버 1이었지만 단계별로 풀이 문제 중에 실버2, 3문제랑 비교해봤을 때 상대적으로 쉬웠던 문제로 보인다. 티어는 그저 거들뿐 .. !! 아닌가? DP + Padding + 모듈러연산을 사용한 것이니 응용버전인 것으로 보이긴 한다... 잡담은 그만하고 DP + Padding(딱 맞는 크기의 배열을 선언하기 보다 적절히 빈 배열을 만들어서 활용하는 기법)+ 모듈러 연산을 통해서 문제를 풀었다. 문제 푸는데 소요시간 : 대략 50분 문제 접근/풀이 과정 1. 계단 수란 인접한 모든 자리의 차이가 1인 경우 2. n번 째 m으로 시작하는 수의 경우의 수 = n-1번째 m-1로 시작하는 수의 경우의 수 or n-1번째 m+1로 시작하는 수의 경우의 수 3. 추가적으로 고려해야할 부분 = 맨 앞의 수.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 28. 백준 2579 - 계단 오르기 JAVA 해당 문제를 접근했을 때 머리가 굳어있어서 그런지 점화식을 찾고도 구현을 하지 못했다. 그래도 이 문제 덕에 DP에 좀 더 익숙해진 것 같다. 문제 접근 과정 1. 계단 갯수는 최대 300개, 점수는 10,000 이하 : 최대 3,000,000(연속으로 계단 올라간다는 조건 무시) -> int 선언 2. 한 번에 +1 or +2씩 계단 오를 수 있지만 연속된 세 계단 금지 3. 도착 계단은 반드시 밟기 4. 그렇다면 이미 목적 계단 가기 이전의 특정 계단을 밟는 순간 최댓값을 알 수 있지 않을까? 5. n번 째 계단까지의 max 합 = n번 째 계단의 점수 + max( (n-2번째까지의 max 합), (n-3번째 까지의 max + n-1번째 계단의 점수)) 6. 2번에서 연속된 세 계단을 오를 수 없다고.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 27. 이전 1 ··· 3 4 5 6 7 다음 728x90