뮤츠의 프로그래밍 이야기

N과M 시리즈 그 세번째. 1번 문제를 중심으로 차이점을 설명하므로, 안보신 분들은 그것부터 보자. N과M (1) 15649. N과 M (1) (자바, Java) 백트래킹 알고리즘 첫걸음. 나중에 알았는데, 3대 뉴비절단기로 재귀, 백트래킹, 동적계획법이 있다고 한다. 나도 알고리즘 공부 첫 위기가 재귀 (별찍기+하노이의탑)에서 왔고, 거기를 극복하고 mewtwo.tistory.com 이번엔 중복을 허용해서, 브루트-포스에 가깝다. 세문제 중에는 가장 관대한 조건. 따라서 visit로 방문여부를 확인해줄 필요가 없다. 그냥 무식하게 추출하자. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTok..

N과M 시리즈 그 두번째. N과M 시리즈는 1번 문제를 중심으로 설명할 예정이므로, 안보신 분들은 그것부터 보자. N과M (1) 15649. N과 M (1) (자바, Java) 백트래킹 알고리즘 첫걸음. 나중에 알았는데, 3대 뉴비절단기로 재귀, 백트래킹, 동적계획법이 있다고 한다. 나도 알고리즘 공부 첫 위기가 재귀 (별찍기+하노이의탑)에서 왔고, 거기를 극복하고 mewtwo.tistory.com 앞선 문제와 다른점은, 수열이 오름차순이어서 뒷 수가 앞 수보다 높으면 안된다는 것. 앞 번호를 추가로 매개변수로 받아줬고, 반복문 시작점을 해당 매개변수로 지정해주었다. import java.io.BufferedReader; import java.io.InputStreamReader; import java...

백트래킹 알고리즘 첫걸음. 나중에 알았는데, 3대 뉴비절단기로 재귀, 백트래킹, 동적계획법이 있다고 한다. 나도 알고리즘 공부 첫 위기가 재귀 (별찍기+하노이의탑)에서 왔고, 거기를 극복하고 백트래킹에서 한차례 위기가 와서 잠깐 다른 문제 풀다 다시 도전했다. 백트래킹은 모든 경우의 수를 탐색하나, brute-force와는 달리, 뻔히 가망없어보이는 경우는 탐색을 생략하고 다음 단계의 탐색을 진행한다. 나의 경우, 설명을 듣고 끄덕끄덕하긴 했으나, 정작 문제를 보고 아무생각이 안나서 멘탈이 터졌던 기억이 있다. 첫 문제는 그냥 클론코딩으로 해결했고, 이후 n과m 시리즈를 해결하면서 깨달음을 얻은 케이스다. 혹여라도 나처럼 어려움을 겪은 분들이 있다면, 같은 방법을 추천드린다. 또한, 코드만으로는 그림이 ..

앞서 있던 진법변환 문제의 연속이다. 받는 값만 쓸데없이 많다. A진법으로 받은 수의 총합을 구해주고, 그걸 다시 B진법으로 반환하면 된다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br...

이전 문제와 반대 문제. 원리가 똑같아서 딱히 어려울건 없다. 오히려 무식하게 곱해주면 되서 더 쉬움. 단, 이전에는 숫자->문자 변환이라 배열로 받았는데, 이번엔 문자->숫자 변환이라 맵으로 받았다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader..

n진법에 대한 개념만 있으면 된다. n진법의 각 자릿수는 n진법의 거듭제곱과의 곱으로 이루어진다. 예를 들어 10진법 394는 3*10^2 + 9*10^1 + 4*10^0 으로 이루어진다. 마찬가지로 2진법 110 은 10진법으로 1*2^2 + 1*2^1 + 0*2^0 = 6이다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(Sy..

골드바흐의 추측 관련해서 기억이 안나서, 예전에 내가 푼 풀이를 참조했다. import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); for (int i=0; i

이 문제 꽤나 어렵게 느껴졌다. 일단 -2진수 자체가 너무 괴리감이 느껴짐. 결국 풀이를 참조함. 나머지가 -1인 경우, 1인경우를 각각 나누어 계산했다. import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); if (n==0) { S..

이전문제 와 반대문제다. 모르겠으면 링크 참조. 각 자릿수를 떼어 3자리의 2진수로 변환해준뒤, 하나씩 입력해주면 된다. 변환시 제일 앞자리 0은 없어진다는 점에 주의. import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); StringBuilder sb = new StringBuilder(); if (str.equals("0"..

n진수를 모르는 사람을 위한 짧은 강의. n진법의 각 자릿수의 n의 제곱꼴로 주어진다. 예를들어 우리가 쓰는 10진법의 394를 예로 들면, 3*10^2 + 9*10^1 + 4*10^0 의 꼴. 8 = 2^3 이므로, 2진법에서 세자리 = 8진법에서 1자리이므로 세자리씩 끊어 8진법으로 변환해주면 된다. import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str..