분류 전체보기
-
[백준-1978]-[수학-소수]-소수 찾기 (java)알고리즘/수학 2018. 11. 27. 12:33
문제링크 : https://www.acmicpc.net/problem/1978 이 문제는 입력받은 수 중에서 소수가 몇개 존재하는지 출력하는 문제이다. 먼저 소수는 1을 제외하고 1과 본인으로만 나눠질 수 있는 수를 말한다. 2부터 입력받은 수 N-1 까지 반복을 돌면서 나눈 나머지 값이 한번이라도 0이 된다면 그 수는 소수가 아니라는 소스를 만들면 된다. 이 문제에서 해줘야 하는 예외 처리는 1은 소수가 아니기 때문에 1을 입력 받으면 소수가 아니라고 판단하면 되겠다. 소스 12345678910111213141516171819202122232425262728293031323334import java.io.BufferedReader;import java.io.IOException;import java.i..
-
[백준-2250]-[트리]-트리의 높이와 너비알고리즘/트리 2018. 11. 27. 12:10
문제링크 : https://www.acmicpc.net/problem/2250 이 문제는 중위 순회법으로 문제를 풀면 된다. 중위순회법으로 문제를 접근하는 이유는 노드의 위치를 알기위해선 본인 기준 왼쪽에 있는 모든 노드들의 수를 알아야 하기 때문이다. 그리고 이 문제에서 주의해야 할 점은 1이 무조건 루트가 아니라는거다. 1이 루트가 아니라는 힌트를 먼저 얻은 다음에 문제에 접근해서 어렵지 않게 문제를 풀었다. 먼저 Node 클래스를 하나 만들었다. 12345678910111213class Node{ int num; int left; int right; int parent; public Node(int num, int left, int right, int parent) { this.num = num; ..
-
[백준-9466]-[DFS]-텀 프로젝트(JAVA)알고리즘/BFS_DFS 2018. 11. 26. 17:14
문제링크 : https://www.acmicpc.net/problem/9466 이 문제는 백준_2668번 문제 와 비슷한 문제지만 절대 비슷하게 풀면 큰일 난다. 본인의 2668 번 문제대로 풀었더니 시간 초과가 발생했다. 이전글 보기 --> 2018/11/23 - [알고리즘/BFS_DFS] - [백준-2668]-[DFS]-숫자고르기 어떤 부분이 문제가 될까 확인을 해보니 사이클 조회를 한번 한 이후 초기화 하는 과정에서 시간을 오래 잡아 먹는것으로 파악 됐다. 먼저 시간 초과가 발생한 소스를 보면서 왜 문제가 있었는지 확인해보고 이 글을 읽는 다른 사람들은 시간초과의 늪에 빠지지 않았으면 좋겠다. 시간초과 소스 123456789101112131415161718192021222324252627282930..
-
[백준-2668]-[DFS]-숫자고르기알고리즘/BFS_DFS 2018. 11. 23. 13:06
문제링크 : https://www.acmicpc.net/problem/2668 이 문제는 사이클이 발생할 때 까지 DFS로 탐색을 진행하면 된다. 만약 사이클이 발생하지 않는다면 visited 정보를 초기화 해주고 사이클이 발생했다면 방문 정보는 초기화 하지 않아야 된다. 12 3 4 5 6 7 3 1 1 5 5 4 6 예제로 받은 데이터로 표를 만들면 위의 표와 같은데 여기서 1을 탐색하면 1의 값이 3 이고 인덱스 3의 값을 탐색한다. 인덱스 3의 값은 1이고 1과 3은 사이클을 돌게 된다. 사이클이 발생하면 visited는 초기화 하지 않는다. 12 3 4 5 6 7 3 1 1 5 5 4 6 2번 인덱스의 값은 1인데 1은 이미 방문 했으므로 사이클이 성립 안된다. 2의 visited는 초기화 해주..
-
[백준-1987]-[DFS-백트래킹]-알파벳알고리즘/백트래킹 2018. 11. 23. 02:38
문제링크 : https://www.acmicpc.net/problem/1987 이문제를 어떻게 접근할까 하다가 간단하겠지 하고 BFS로 풀었는데 절대 BFS풀면 안된다더라..그 이유는 동시에 같은 레벨의 다른 접점을 접근하기 때문에 만약 2레벨의 같은 알파벳이 있으면 방문 여부를 파악하기가 힘들다. 백트래킹으로 가능한 모든 방향을 접근하고 지나간 최대 칸수를 출력해주면 된다. 말이 쉽지 참 힘들었다. 예제는 항상 답이 나오는데 제출을 하면 항상 문제였다. 내가 푼 문제에 반례가 어떤게 있을까 하다가 스스로 예제를 만들어 보았다. 이것만 통과하면 제출해도 정답이 나올거 같다.. 내가 생각해낸 예제는 아래 표다. A B B C EC E D FG D H 만약 단순한 DFS만으로 결과를 도출해낸다면 최대 길이는..
-
[백준-1726]-[BFS]-로봇알고리즘/BFS_DFS 2018. 11. 23. 01:30
문제 링크 : https://www.acmicpc.net/problem/1726 이 문제를 풀려고 하는데 계속 틀렸다고 하는 분들에게 드리고 싶은 말은 문제 제대로 보셨나요?? 이다..수없이 문제를 수정하고 아.. 왜 안되지.. 잘되는데.. 했지만 문제를 제대로 읽지 않고 문제를 풀었기에 문제에서 큰 부분을 뺴놓고 문제를 풀었다. 명령 1. Go k - k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.명령 2. Turn dir - dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다. 명령 1 Go K 는 본인의 현재 방향으로 1 ~ 3을 움직인다. 나는 이 부분을 그냥 무조건 직진! 으로만 이해를 했다. 한번의 명령으로 최대 3칸만 움직일..
-
[백준-1963]-[BFS]-소수경로알고리즘/BFS_DFS 2018. 11. 23. 01:04
문제 경로 : https://www.acmicpc.net/problem/1963 이 문제는 까먹었던 소수에대해서 다시 기억하게 해준 고마운 문제다. 먼저 소수는 1 과 자신 이외에 나누어지지 않는 수를 소수라고 한다. 그럼 소수인지 아닌지 어떻게 확인할까?? N이라는 수가 있다면 2부터 N 전의 정수로 전부 나눠서 하나라도 나누어지는 값이 있다면 그것은 소수가 아니고 나누어지는 값이 없다면 그 값은 소수이다. 1은 소수가 아니다. 그래서 1은 예외처리를 해줘야 한다. 소수 판별하는 소스 12345678910111213 public static boolean isPrimeNum (int num) { boolean result = true; if(num == 1) return false; for(int i ..
-
[백준-9663]-[백트래킹] - N-Queen알고리즘/백트래킹 2018. 11. 21. 18:00
문제 링크 : https://www.acmicpc.net/problem/9663 이 문제는 백트래킹 알고리즘의 기본적인 예제라고 한다. 백트래킹 알고리즘은 그리디 알고리즘과 모든 가능성을 조회하고 조회 한 값으로 결과를 구한다는 비슷한 성질을 가진다. 차이점은 그리디 알고리즘은 정말 모든 가능성을 조회하지만 백 트래킹의 경우는 다음경우가 유효한 경우가 아니면 진행하지 않는다. 그런 개념을 이해할 수 있는 문제가 N-Queen 문제인거 같다. 이 문제는 퀸을 N x N 체스 판에 N 개만큼 위치 시킬 수 있는 경우의 수가 얼마만큼 있는지 구하는 문제이다. 예로 4 x 4 체스판에 (1, 2) 위치에 퀸이 놓여져 있다고 가정하면 (1번 인덱스가 제일 앞 인덱스라 할 때) Q 위의 빨간색인 부분에는 퀸을 놓을..