알고리즘
-
[백준 10845] - [큐] - 큐 (JAVA)알고리즘/큐(Queue) 2018. 12. 2. 14:02
문제 링크 : https://www.acmicpc.net/problem/10845 이 문제는 큐를 제대로 이해하고 있는지 파악하는 문제로 보인다. 근데 내가 기억하는 큐는 선입선출이고 탐색은 front 할 수 있다고 알고 있었는데 이 문제는 back도 탐색을 하라고 한다. 그래서 push로 큐에 삽입할때 back의 값을 변경하고 POP으로 큐에서 추출할때 추출한 이후에 큐가 비어 있으면 큐의 크기를 -1로 변경했다. 큐는 선입선출이니 딱 이 두 상태에서만 back의 값을 변경해주면 문제는 없다. 소스12345678910111213141516171819202122232425262728293031323334353637383940414243444546import java.io.BufferedReader;imp..
-
[백준 2504] - [스택] - 괄호의 값 (JAVA)알고리즘/스택(Stack) 2018. 11. 30. 15:53
문제 링크 : https://www.acmicpc.net/problem/2504 이문제는 백준 9012 번 문제의 업그레이드 문제이다. 본인의 풀이와 문제링크를 첨부한다. 백준 9012 문제 링크 2018/11/30 - [알고리즘/스택(Stack)] - [백준 9012] - [스택] - 괄호 (JAVA) 이전글에서 유효한 괄호 문자열을 만드는거에 괄호갖는 값 을 계산하는 문제이다. 여는 괄호가 나올때는 문제없이 스택에 PUSH 하면 되지만 닫는 괄호가 나올때가 문제이다. [ ( ) ] 의 괄호 문자열이 입력 됐다면 답은 6이 나온다.왜 그럴까? () 괄호가 갖는 값은 2 이고 []괄호가 갖는 값은 3X가 정수일때 (X)는 X*2 이고 [X] 는 X*3이라고 하니깐 [ ( ) ] 는 [2] 로 되고 6이 ..
-
[백준 9012] - [스택] - 괄호 (JAVA)알고리즘/스택(Stack) 2018. 11. 30. 14:25
문제 링크 : https://www.acmicpc.net/problem/9012 이문제는 괄호 문제중에서 제일 쉬운 문제이다. 다른 괄호문제는 소괄호 중괄호 대괄호가 나오는데 이 문제는 소괄호 하나로 유효한 괄호 문자열인지 확인하는 문제이다. 쉽게 따지면 그냥 여는 괄호가 나오면 스택에 PUSH 하고 닫는 괄호가 나오면 POP 하면 된다. 유효하지 않은 문자열을 판단하는 기준은 두가지가 있다. POP연산을 하려고 하는데 Stack 이 비어 있다면 이번 순서에는 여는 괄호가 입력 돼야하는데 닫는괄호가 입력 됐다는 말이므로 유효하지 않다고 할 수 있다. 두번째는 모든 연산을 다 끝냈는데 불구하고 스택에 아직도 괄호가 남아 있다면 여는 괄호가 닫는괄호보다 많이 들어왔다는 거고 이 또한 유효하지 않은 괄호 문자..
-
[백준 1874] - [스택] - 스택 수열 (JAVA)알고리즘/스택(Stack) 2018. 11. 30. 13:57
문제 링크 : https://www.acmicpc.net/problem/1874 이문제는 스택의 활용 문제로 보인다. 스택을 이해하면 풀수 있다! 하는거 같다. 근데 정답률이 좀 낮은 편이다. 그 이유는 문제가 변태적이기 때문이다. 솔직히 내가 느끼기에는 변태적이었다. 일단 이문제를 접근하는 방법은 의외로 간단했다. 12345 public static int N; // 입력받을 수열의 크기 public static int num = 1; // 수열을 만들기 위해 1 ~ N가 되는 수 public static int[] arr; // 입력받을 수열이 저장될 배열 public static Stack stack; // 수열을 만들기 위해 1 ~ N 까지의 수가 저장될 스택cs 이문제를 풀기위해 변수는 4개 사..
-
[백준 10828] - [스택] - 스택 (JAVA)알고리즘/스택(Stack) 2018. 11. 30. 12:30
문제 링크 : https://www.acmicpc.net/problem/10828 이 문제는 별로 쓸 글은 없다.단순히 스택이 어떻게 돌아가는지 이해하는 문제여서 소스만 이쁘게 작성하면 된다. 소스 123456789101112131415161718192021222324252627282930313233343536373839import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Stack;import java.util.StringTokenizer; public class Main { public static int size; public static Stack stack; ..
-
[백준 1074] - [분할정복] - Z (JAVA)알고리즘/분할정복(Divide and conquer) 2018. 11. 30. 12:04
문제 링크 : https://www.acmicpc.net/problem/1074 이 문제는 분할정복으로 쉽게 풀 수 있는 문제이다. 그리고 배열을 만들필요가 없다. 굳이 만들겠다면 확인해 보자 heap 메모리가 부족하다고 에러가 발생할것이다. 입력값이 최대 값이 15 이다 이 15가 15 X 15 가 아니라 2의 15승이다 2의 15승은 32,768이다. 그럼 32,768 * 32,768 = 1,073,741,824 10억개 정도 나온다. 그럼 이것또한 무식하게 재귀로 풀것인가?? 그것또한 미친짓이다. 이 문제의 정답 비율은 굉장히 높다.그럼 쉽게 접근 할 수 있다는것이다. 배열의 크기를 최소 사이즈인 2가 될때까지 계속 4등분을 하면서 입력받은 좌표가 범위 안에 있는 것들만 계산을 했다. 8*8 배열에..
-
[백준 2309] - [분할정복] 일곱 난쟁이 - JAVA알고리즘/분할정복(Divide and conquer) 2018. 11. 30. 10:56
문제 링크 : https://www.acmicpc.net/problem/2309 이문제는 의도하는바만 잘 파악하면 어렵지 않게 문제를 풀 수 있다. 입력은 무조건 9명의 난쟁이애 대한 키 정보이고 두명을 제외한 나머지의 키의 합이 무조건 100이 된다고 한다. 가능한 답이 여러가지일 경우 아무거나 출력하면 된다고하는데 이럴때는 100이 이루어지면 바로 종료시키고 출력시키면 된다. 문제를 푸는 방법은 두 난쟁이의 키를 전체 아홉 난쟁이 키의 총합에서 뺀 값이 100이면 두 난쟁이의 값을 최소 값으로 변경 시킨 후 정렬하고 출력시키면 된다. 일곱 난장이들의 키를 합하는 것보다 전체 합에서 두명의 키만 뺴는것이 더 바람직할것이기떄문에 두 난쟁이의 키만 빼면 된다. 소스12345678910111213141516..
-
[백준 2263] - [분할정복] - 트리의 순회(java)알고리즘/분할정복(Divide and conquer) 2018. 11. 29. 15:38
문제 링크 : https://www.acmicpc.net/problem/2263 이 문제는 좀 변태적인 문제라 확신한다. 중위 순회(In-order) 가 주어지고 후위 순회(Post-order)가 주어졌을때 전위순회(Pre-order)를 구하라는 문제이다. 예제 입 출력은 아래와 같다. 입력3 1 2 3 1 3 2출력2 1 3 하지만 예제 입출력에는 노드가 3개여서 예제 입출력을 기준으로 풀면 구하기 힘들다.그래서 예제로 트리하나를 만들었고 전위, 중위, 후위 순회의 값을 먼저 구한뒤 이 값이 나오도록 유도해봤다. 위의 트리를 만들어 보았고 각각 전위, 중위, 후위 순회를 구해봤다. 전위 순회 : 1 -> 2 -> 4 -> 7 -> 8 -> 5 -> 3 -> 6 -> 9 중위 순회 : 7 -> 4 -> ..