분류 전체보기
-
[백준-2573]-[DFS-BFS]-빙산알고리즘/BFS_DFS 2018. 11. 21. 14:17
문제링크 : https://www.acmicpc.net/problem/2573 이 문제는 낮은 합격률에 겁을 먹고 문제를 잘못 이해해서 시간을 엄청 뺏긴 문제이다. 1년이 지나면 높이가 1이 낮아진다 하고 푸니 정말 쉽게 풀었다. 하지만 계속해서 결과가 틀렸다 나오길래 멘붕이 왔다. 다시한번 문제를 읽어보면서 문제를 제대로 읽지 않고 코딩을 한 과거의 내가 원망스러웠다. 이문제에서 중요하게 봐야할 문구가 두개 있다. 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다. (i, j..
-
[백준-2667]-[BFS]-단지번호 붙이기알고리즘/BFS_DFS 2018. 11. 20. 15:56
문제 링크 : https://www.acmicpc.net/problem/2667 이 문제는 처음에는 접근법이 감이 안올 수 있다. 입력받은 이차원 배열을 하나씩 접근해 나가면서 0 이면 무시하고 1이고 BFS로 접근 이력이 없으면 그 좌표를 기준으로 BFS를 돌리면 된다. 예제를 기준으로 그림으로 보면 이해가 빨리 된다.7 0110100 0110101 1110101 0000111 0100000 0111110 0111000 위의 예제 입력으로 표를 만들면 아래 처럼 나온다. 01 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 좌표 (0, 0) 부터 조회를 한다. (0,0) 은 0 이므로..
-
[백준-2606]-[BFS]-바이러스알고리즘/BFS_DFS 2018. 11. 20. 15:14
문제 링크 : https://www.acmicpc.net/problem/2606 이문제는 시작점부터 BFS를 돌고 본인을 제외하고 접근한 노드들의 수를 세면 끝나는 문제이다. 입력받은 모든 노드들이 연결 돼 있다면 모든 노드들을 접근하겠고연결이 안된 노드들은 BFS로 접근이 안된다. 정답률이 높은데 그만큼 쉬운 문제이다. 소스 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import ja..
-
[백준-2178]-[BFS]-미로탐색알고리즘/BFS_DFS 2018. 11. 20. 14:19
문제 링크 : https://www.acmicpc.net/problem/2178 이문제는 BFS DFS 모두 풀 수 있다.하지만 본인은 BFS로 풀었다. 굳이 DFS로 풀지 않은 이유는 BFS가 더 땡기고 아직은 재귀적 생각이 짧아서 효율적인 재귀 함수를 구현을 잘 못하겠어서도 있다.좀 더 공부를 하면서 시간을 단축하는 DFS를 작성할 수 있었으면 좋겠다. 이문제는 앞서 있는 다른 BFS 문제에 비해 매우 쉬운 난이도이다. 각 칸을 BFS로 접근하면서 칸 수만 세면 끝나기 때문이다. 벽에 도달하면 패스하고 방문한 이력이 있으면 패스하면 된다. 한번이라도 방문을 했으면 무조건 적으로 먼저 방문했을때의 값이 작다. BFS는 Queue에 쌓아 하나씩 선입선출로 꺼내 사용하기 때문에 level 단위로 처리된다...
-
[백준-7569]-[BFS]-토마토알고리즘/BFS_DFS 2018. 11. 20. 13:06
문제링크 : https://www.acmicpc.net/problem/7569 이 문제는 7576 문제의 확장형이다.문제를 접근 하는 방법은 단 1의 차이점도 없고 다만 2차원 배열에서 3차원 배열로 변한거 뿐이다. 7576번에서는 (row -1, col), (row + 1, col) , (row, col - 1), (row, col + 1) 4개 위치에 있는 토마토만 익히면 됐지만 이번 문제에서는 참조할 좌표가 두개가 더 추가된것 뿐이다. 참조할 좌표 height + 1, row, col height - 1, row, col height, row - 1, col height, row + 1, col height, row, col -1height, row, col +1 문제를 접근하는 방법은 7576번 ..
-
[백준-7576]-[BFS]-토마토알고리즘/BFS_DFS 2018. 11. 20. 12:09
문제 링크 : https://www.acmicpc.net/problem/7576 이 문제는 당연히 BFS 로 풀어야 하는 문제다. 하지만 생각을 제대로 하지 못하면 어리석은 소스로 시간 초과에 걸리는 상황을 만들 수 있다. 먼저 어리석은 생각으로 한 코딩을 올리면서 한번의 반성을 하고 시간 초과를 해결한 소스를 올리면서 다시 반성해야겠다. 일단 아주 쉽게 아 BFS로 안익은 토마토 카운트가 0일 될때까지 BFS를 돌리면서 한칸씩 익히면 되겠구나! 이 생각을 아주 엇나가게 했다. 내가 한 잘못된 생각은 이렇다. 시간초과 소스1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556..
-
자바로 정리한 우선순위큐(PriorityQueue)알고리즘 2018. 11. 16. 13:40
큐는 자료구조 형식이 선입선출(FIFO) 이다.말 그대로 먼저 입력된 자료가 먼저 출력된다.큐를 이해하는 방법은 줄서기를 생각하면 된다.먼저 줄을 기다린 사람이 표를 끊거나 개인 용무를 볼 수 있다.나중에 온 사람은 당연히 자기 순번까지 기다려야 하는게 인지상정. 하지만 우선순위 큐(Priority Queue)는 다른다. 들어온 순서에 상관 없이 우선순위가 높은 데이터가 먼저 출력이 된다는 말이다. 고양시에서 강남까지 가는 방법 (대중교통, 자가용, 도보, 자전거) 의 방식이 있다.대중교통은 1시간 10분 정도 걸리고자가용은 45분도보는 6시간 40분 자전거는 2시간 5분 걸린다.여기서 시간이 제일 적게 걸리는 순서로 정렬해보면 자가용, 대중교통, 자전거, 도보 순이다.우선순위큐에 저장한뒤 하나씩 데이터..
-
[백준-4307]-[그리디알고리즘]-개미알고리즘/그리디알고리즘(Greedy Algorithm) 2018. 11. 15. 19:08
문제링크 : https://www.acmicpc.net/problem/4307 이문제는 그림으로 보면서 풀면 이해가 제일 쉬울거 같다. 길이 10의 막대기가 있고 개미 3마리가 있다.개미들의 위치는 2, 6, 7에 있다. 개미1 개미2 개미3 1(지나면 끝) 2 3 4 5 6 7 8 9 10 (닿으면 끝) 여기서 무시해야될 조건이 있다. 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다. 위의 조건은 무시하고 각 개미가 떨어지는 시간의 최소와 최대를 구해보면 최소 최대 개미12 8 개미24 6 개미33 7 각 개미의 최소 시간중 제일 큰 값은 4, 최대 시간의 제일 큰 값은 8 주어진 예제의 원하는 값과 같다.각 개미들이 만나는 상황은 신경 쓸 이유가 없다는 뜻이다. 즉 이문제를 푸는 방법은..