전공공부

설명 중복 제거를 줄이기 위해 처음에는 그냥 알파벳의 index 위치로 탐색했다가 메모리 초과가 나서 다시 생각해서 풀어보았다. 아래와 같이 알파벳의 갯수에 대해서 카운트 하면 a -> a -> b 와 같은 것이 한 번 더 나올 수가 없다. 뒤로 돌아갔을때 만일 index 위치로 탐색하면 처음 나온 a와 뒤에 나온 a 값이 다른 것인데 알파벳의 count 값으로 방문 선정을 해버리면 처음에 나온 a와 뒤에 나온 a는 모두 같은 경우이다. (for문 내부에서 넘어가는 i 값이 달라져 버리니... 다음번에 선택을 할 수 밖에 없다.) 코드 package backtracking; import java.util.*; import java.io.*; public class BOJ_6443 { static char..

설명 백트래킹 구현이 쉽다면 굉장히 쉬운 문제다. 사고력을 필요로 하지 않아서 시키는대로만 구현하면 만들 수 있었다. 코드 package backtracking; import java.util.*; import java.io.*; public class BOJ_3980 { static int T; static int arr[][]; static boolean visited[]; static int ans = 0; public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); T = Integer.parseInt(in.readLine(..

설명 줄어드는 수를 구해놓고 거기서 선택을 하면서 나간다... 이 컨셉을 생각하지 못하면 생각이 나지가 않는다. 먼저 9876543210의 형태가 최고 줄어드는 수이고 이때 앞에서 부터 수를 선택해서 나가면 여기서 앞으로는 무조건 줄어드는 수이니... 앞으로 가면된다. 그 후에는 뽑을때 순서를 지켜서 오름차순의 순서로 뽑혀야 하니 sort를 하여 꺼내게 된다. 처음 접근 법을 제대로 접근을 못해서 시간을 많이 잡아 먹은 문제 코드 package backtracking; import java.util.*; import java.io.*; public class BOJ_1174 { static int N; static String[] num = { "9", "8", "7", "6", "5", "4", "3"..

설명 결국 2*2 사각형을 만들지 않으면 되는 것이므로 반대로 생각하면 되었다... 처음 접근만 잘한다면 쉽게 풀 수 있는 문제였다. 코드 package backtracking; import java.io.*; import java.util.*; public class BOJ_14712 { static int N; static int M,ans; static boolean map[][]; public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tk = new StringTokenizer(in.rea..

설명 canBreak 부분이 추가가 되면서 맞았는데 조건 중 아래 조건을 간과하였다. 가장 왼쪽의 계란을 든다. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다. 제대로 읽고 문제 푸는 연습이 필요하다. 코드 package backtracking; import java.io.BufferedReader; import java.io.InputStreamReader; ..

설명 연산자 끼워 넣기 연산자의 위치는 그대로고 각각의 기호를 뽑아서 쓴다는 느낌으로 접근했다. 사실 로직 구현 자체는 쉬웠지만 음수 값이 나온다는 것을 간과하여 max의 초기 값을 = 0 으로 잡아서 어디서 틀린지 확인을 많이 했다. 코드 package Backtracking; import java.util.*; import java.io.*; public class BOJ_14888 { static int arr[]; static long max; static long min; static int N; public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStream..

설명 순열의 형태로 나아갔는데 사실 이런 것을 생각하고 코드를 짜지는 않았다. 솔직히 파악이 힘들어서 다른 블로그의 코드를 1차로 본 후 다시 풀어보았다. 코드에 대한 설명은 아래와 같다. 방문 여부 체크는 다시 되돌아가지 않는다는 조건이 있었기 때문에 사용하였고, 최초 출발점인 0로 부터 시작하여 go 함수 내부 for문의 1부터 시작하여 순회를 돌며 갈 수 있는 포인트를 모두 탐색을 진행한다. 그리고, 1(이미 처음 부터 출발지 하나 선택 완료 됌) 부터 카운팅하여 N 개 까지 탐색 했다는 것은 이미 모두 돌았다는 말이니 여기서 부터 돌아갈 수 있는 포인트로 처음 시작 점으로의 가는 비용 더하고 종료하였다. 코드 package backtracking; import java.io.BufferedRead..

설명 등차수열 사실 {n/(n+1)}/ 2 이것을 외우고 있었기 때문에 풀 수 있었던 문제였다. 1~100 까지 모두 더 한 값이 5050이다. 이것을 생각 했을 때 등차 수열의 형태로 모두 지나가는 자연수를 더하면서 가면 최대로 서로 다른 수를 사용하면서 자연수 N을 만들 수 있을 것이라고 생각했다. (1,2,3,4,3 = 서로 다른 수를 최대로 사용하면서 13을 만들기 위한 값들) 등차수열을 최대로 활용하고 나머지 하나를 빼면 된다. 그렇기 때문에 아래와 같은 식이 나왔다. 코드 package Math; import java.io.*; public class BOJ_1789 { public static void main(String[] args) throws Exception{ BufferedRead..