백준
-
[백준 2661] - [백트래킹] - 좋은 수열 (JAVA)알고리즘/백트래킹 2018. 12. 26. 16:13
문제링크 : https://www.acmicpc.net/problem/2661 이 문제는 아주 쉽게 백트래킹으로 접근 할 수 있다. 모든 경우의 수를 탐색하면서 조건에 성립되면 결과를 출력하면 된다. 이 문제에서 제시하는 조건은 다음과 같다.임의의 길이의 인접한 두 개의 부분 수열이 동일하지 않아야 한다. (나쁜 수열이면 안된다.)나올 수 있는 좋은 수열 중에서 가장 작은 수를 출력해야 한다. 첫번째 조건을 확인하는 함수 하나를 만들고 두번째 조건은 첫번째로 좋은 수열이 나온 좋은 수열이 제일 작은 수열이기 때문에 좋은 수열이 나오면 모든 탐색을 종료 시키면 되기 때문에 따로 조건을 확인하는 함수를 만들 필요는 없다. 좋은 수열인지 확인하는 함수는 아래와 같이 만들었다. public static bool..
-
[백준 1759] - [백트래킹] - 암호 만들기 (JAVA)알고리즘/백트래킹 2018. 12. 26. 15:19
문제 링크 : https://www.acmicpc.net/problem/1759 이 문제는 백트래킹으로 쉽게 접근 할 수 있다. 이전에 풀었던 백트래킹 문제들을 하나씩 풀어본다면 아주 쉽게 코드를 작성 할 수 있다. 모든 경우에 수를 전부 탐색하면서 문제에서 제시한 3가지 조건을 만족 시키는 경우 생성된 암호를 출력 해주고 다시 다른 경우의 수를 탐색하면 된다. 이전에 풀었던 백트래킹 문제를 기억해가면서 풀어보니 정말 쉽게 문제를 풀 수 있었다. 만약 기억이 안난다면 다른 백트래킹 문제를 풀어보면서 접근해보면 좋을듯 하다. 백트래킹 관련 글 2018/11/21 - [알고리즘/백트래킹] - [백준-9663]-[백트래킹] - N-Queen2018/11/23 - [알고리즘/백트래킹] - [백준-1987]-[D..
-
[백준 6603] - [백트래킹] - 로또 (JAVA)알고리즘/백트래킹 2018. 12. 26. 14:08
문제 링크 : https://www.acmicpc.net/problem/6603 이 문제는 백트래킹으로 접근 하면 되는 문제다. 백트래킹은 모든 경우의 수를 탐색을 진행 할때 탐색을 한 후에 다시 값을 탐색하기 이전으로 되돌리는 형태의 알고리즘 이다. 이 문제는 그럼 어떻게 접근을 해야 할까? 주어진 k 개의 원소 중에서 하나씩 뽑아서 로또 번호를 생성하면 된다. 한번 로또 번호에 사용된 원소는 다시 사용 될 수 없기 때문에 i 번째 원소가 로또 번호로 생성 됐다면 그 다음 로또번호는 i+1 부터 k-1 번 째 원소가 될 수 있다. 예를 들어 k 는 7 이고 원소들의 집합으로 {1, 2, 3, 4, 5, 6, 7} 을 입력 받은 상태에서 { 1, 2, 3} 까지 로또 번호를 생성 했다면 그 다음 로또 번..
-
[백준 5427] - [BFS 최단거리] - 불 (JAVA)알고리즘/BFS_DFS 2018. 12. 20. 13:57
문제링크 : https://www.acmicpc.net/problem/5427 이 문제는 BFS를 가지고 풀면 되는데 좌표정보를 갖는 queue를 2개를 사용해야 한다. queue1은 불의 좌표를 저장하는 queue로 사용하고queue2는 사람의 좌표를 저장하는 queue로 사용한다. 입력 값이 숫자가 아닌 # * . @ 형식의 char 타입 데이터 이기 떄문에 나는 이 char를 custom 해서 int 형의 값으로 변경했다. # --> -1* --> -2. --> 0@ --> 1 방문 정보를 저장할 visited 배열을 사용하기 싫어서 빈 공간은 0으로 두고 사람이 움직일때 좌표의 값이 0인 위치만 이동하게 소스를 작성했다. 복잡하다면 char형의 이차원 배열과 visited 배열을 두개 생성하고 문..
-
[백준 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..
-
[백준 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 -> ..
-
[백준 1780]-[분할정복]-종이의 개수 (JAVA)알고리즘/분할정복(Divide and conquer) 2018. 11. 28. 13:18
문제 링크 : https://www.acmicpc.net/problem/1780 이 문제는 분할정복으로 풀어야 한다. 입력받은 사이즈가 9 라면 총 9*9 개의 모든 좌표가 같아야 하나의 정사각형 종이가 완성된다. 그럼 9*9개의 수가 같지 않다면? 9등분을 한뒤에 다시 정사각형 종이가 나오는지 확인해야 된다.사이즈 9를 3으로 나눠 다시 확인하고 여기서도 정사각형 종이가 나오지 않는다면 3으로 다시 나눠서 확인해야한다. 이문제의 조건은 사이즈는 무조건 3의 배수로 입력 된다고 한다. 첫째 줄에 N(1≤N≤3^7, N은 3^k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. 3으로 나눠지지 않을 걱정은 안해도 되고 그럼 이 문제를 어떻게 푸는지 간단하게 정리하면 1) 사이즈만큼 하나..
-
[백준 4948]-[수학] - 베르트랑 공준알고리즘/수학 2018. 11. 27. 14:34
문제링크 : https://www.acmicpc.net/problem/4948 이 문제는 에라토스테네스의 체를 이용해서 푸는 좀 심화 문제라고 생각하면 된다. 2018/11/27 - [알고리즘/수학] - [백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java) 먼저 이문제를 풀기전에 입력수의 크기는 12345 라고 하고 베르트랑의 공준이 어떤 내용인지 설명해주고 있다. n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 배열의 범위를 123456 로만 하면 인덱스가 초과되서 런타임에러가 발생한다.최소 범위 123456 * 2 값인 246912 + 1 을 해야한다. 문제를 푸는 순서는 다음 순서를 따른다.1) 에라토스테네스의 체로 2부터..