알고리즘

[백준] 1로 만들기 (1463)

최종정리 TL;DR 문제의 조건에 따라 각 조건에서 반복되는 부분을 찾고, 해당 부분을 일반화하여 점화식 설계 및 for문을 이용한 구현을 하는 동적 프로그래밍 문제 시행착오 https://devwaffle.notion.site/1-e301a645e8794586a2e04eea233a2858 유의사항 DP라고 해서 모든 문제가 피보나치 수열은 아니다 이전 연산값을 활용할 수 있는 문제는 많다. 최종코드 풀이코드 package main.practice.dynamicProgramming; import java.util.Scanner; public class acmicpc1463 { public static final int CASE_MAX = 100000; public static void main(Strin..

[백준] -2진수 (2089)

최종정리 TL;DR 기존 n진법 계산방식을 활용한 정수진법 연산문제. 언어별 소수의 정수형변환 처리방식을 정확히 알아야 풀이코드 구현과정에 용이함. 시행착오 https://devwaffle.notion.site/2-63a24d24a7e649ac93fac3ecfcd62c66 유의사항 C와 Java는 버림방식을, python은 내림방식을 사용함을 알아둘 것 버림방식: 음수와의 나눗셈에서 소수보다 큰 수로 정수화하는 것 내림방식: (음수와의 나눗셈에서 소수보다 작은 수로 정수화하는 것 모든 진법간 변환은 2진법으로 변환하는 기본틀에서 벗어나지 않음을 명심할 것 참고기술 X 최종코드 풀이코드 package main.practice.math1Practice; import java.util.Scanner; publ..

[백준] 2진수 8진수 (1373)

최종정리 TL;DR 문자열상태에서 빠르게 특정 문자로 접근하여 연산하는 방법을 찾는 문제 시행착오 https://devwaffle.notion.site/2-8-6d6d38a97571497e93bba349abd35e36 유의사항 너무 깊은 방법으로 문제를 풀려고 하지 말자. 그러다가 오히려 풀이시간과 메모리만 늘어난다 문자열 특정위치에 있는 문자를 볼때는 charAt() 메서드를 사용하면 된다. 참고기술 최종코드 풀이코드 package main.practice.math1Practice; import java.util.*; public class acmicpc1373 { public static void main(String[] args) { Scanner scanner = new Scanner( Syste..

[백준] 숨바꼭질 6 (17087)

최종정리 TL;DR 문제에서 정확히 어떤 것을 원하는지 분석하여, 원하는 부분만 빠르고 정확하게 풀어내는 방법을 찾아야 하는 문제로서, 유클리드 호제법을 활용하여 여러 수의 최대공약수를 가능한 빠르게 구하는 문제 시행착오 https://www.notion.so/devwaffle/6-436b7de574694d8191aed7997a265d64 유의사항 수의 절대값이 필요할 때에는 Math.abs() 메서드를 사용하면 된다 최대공약수를 구하기 위해 while문 대신 재귀를 사용하여 구하는 것도 가능하다. (구현된 코드 보고 익혀두기!) 참고기술 유클리드 호제법 배열의 정렬 최종코드 풀이코드 package main.practice.math1Practice; import java.util.Arrays; impor..

[백준] GCD 합 (9613)

최종정리 TL;DR 최대공약수를 빠르게 연산하여 가능한 모든 경우의 수에 대한 결과값의 합을 구하는 문제. 제발 정수범위 생각하면서 문제풀자. 시행착오 https://www.notion.so/devwaffle/GCD-6f4dfd6922c14d4e804c5890181d26d9 유의사항 제발 정수범위 보면서 문제를 풀것 항상 유클리드 호제법이 메모리나 시간측면에서 이득을 보는 것 같진 않음. 유동적으로 변환하면서 문제를 풀어나갈 것 참고기술 유클리드 호제법 최종코드 1) 유클리드 호제법을 사용하여 gcd를 구하는 방법 package main.practice.math1; import java.io.BufferedWriter; import java.io.IOException; import java.io.Outp..