알고리즘공부(Algorithm Study)83

백준 1780 java - 종이의 개수 해당 문제는 전형적인 분할정복 문제이다. 크게 어려운 부분은 없었던 것 같다. for문에서 for문 변수로 안 돌려서 삽질한 부분 빼고;;; 1. N x N 크기 행렬 / 1 n/3씩 자르기 package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Boj_1780 { static int N, arr[][], count[]; public static void main(String[] args) throws NumberFormatException, IOException { // N x N 크기 .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 20.

백준 5430 java - AC 타이머, 스톱워치, 시계가 필요할 땐 https://alittlekitten.github.io/SsocoTimer/ SsocoTimer 타이머/스톱워치 애플리케이션 SsocoTimers 입니다 :) 많이 사랑해주세요!! alittlekitten.github.io 배열로도 풀 수 있고 덱으로도 풀 수 있는 문제이다. 제일 먼저 배열로 풀까 했다가 단계별로 풀어보기 큐/덱이어서 덱으로 풀어보았다. 배열로 푸는 경우에는 투포인터로 start, end 부분을 조정해서 풀면 결국 덱과 같아진다. 1. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수 2. 함수 D는 첫 번째 수를 버리는 함수 - 배열이 비어있는데 D를 사용한 경우에는 에러 발생 3. 함수는 조합해서 한 번에 사용 4. T 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 19.

백준 1021- 회전하는 큐 JAVA 전형적으로 deque을 이용한 큐 돌리기 문제였다. 처음에는 문제를 잘못 읽어서 테스트케이스 2번이 어떻게 되나 했는데 그냥 시계방향, 반시계방향 돌리면서 해당 원소가 나올 때의 최솟값들을 합하면 된다는 것을 알았다. 1. 덱을 활용한 원형큐 느낌이 들었음 2. 시계방향, 반시계방향으로 움직이며 원소들을 일일이 확인하고 두 방향 중 최솟값을 answer에 더하면 끝 +참고: 덱은 front, tail부분에 삽입, 삭제, 조회가 가능한 자료구조이다. package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import jav.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 18.

백준 18258 - 큐 2 JAVA 해당 문제는 큐를 구현해보라는 문제다. 배열을 쓸지 리스트를 쓸지 고민하다가 이번엔 리스트를 써보았다. 1. 큐 클래스를 정의 2. 적절한 자료 구조 선택(배열/리스트 등) 3. 구현 4. 이항연산자 활용 해당 문제는 큐 구현 문제이다. 따라서 큐의 메소드가 뭐가 있는지 파악해두는 워밍업이라고 생각하면 좋을 것 같다. package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Boj_18258 { sta.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 17.

백준 2004 - 조합 0의 개수 JAVA 해당 문제는 아이디어가 생각날 듯 말 듯해서 누워서 생각하다가 한 10분 잠들었다가 일어났더니 생각나서 풀어버린 문제이다. 가끔 누워서 아이디어를 떠올리다 보면 풀리는 문제가 있다. 1. nCm = n! / ((n-m)! * m!)이다. 2. 끝자리 0의 갯수는 10이 얼마나 있느냐 = 2 * 5 쌍의 개수 3. 그냥 5의 배수 나열해 보기 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125... 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3 -> 5의 개수는 결국 특정 n에서의 5로 나눈 몫 + 5^2(25)로 나눈 몫... + 5^n으로 나눈 몫 고로 n! 이 포함하는.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 17.

백준 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.

이전 1 ··· 3 4 5 6 7 다음

728x90

티스토리툴바