반응형 백준 알고리즘8 백준 7576 토마토 알고리즘 문제 자바 JAVA CODE 백준 7576 토마토 문제는 토마토가 들어있는 1의 칸에서 시작해서 전체 토마토가 익어가는 기간을 구하는 문제다. 복잡해보이지만 결국 BFS 알고리즘으로 해결할 수 있는 문제다. 첫번째 노드에서 상하좌우로 접하고 있는 노드를 찾아서 counter를 통해 1씩 증가해가면서 마지막 노드까지 가는 최단거리를 구하는 문제와 일맥상통하다. DFS + BFS 알고리즘 이해하기 백준 1012 유기농 배추 알고리즘 자바 JAVA 백준 1012 유기농 배추 알고리즘 자바 JAVA 문제 백준 1012 유기농 배추 문제는 DFS/BFS 알고리즘을 사용해서 풀어보는 문제다. 기존 문제와 다른 점은 주어진 배열이 정사각형이 아닌 직사각형이라는 incomeplus.tistory.com 백준 2178 미로 탐색 알고리즘 자바 JA.. 2022. 3. 11. 백준 2178 미로 탐색 알고리즘 자바 JAVA 풀이 백준 2178 미로 탐색 BFS 알고리즘 JAVA 자바 백준 2178 미로 탐색 알고리즘은 완전탐색인 BFS 알고리즘으로 풀어야 하는 문제다. 상하좌우로 움직일 수 있고, 입력단에서 주어지는 N,M 좌표까지 가장 최단거리로 움직이는 수를 구하는 문제다. 최초 시작점인 (0,0) 좌표와 마지막 도착위치도 카운팅에 포함한다. 대표적인 탐색알고리즘은 DFS와 BFS를 동시에 살펴본다. DFS는 루트노드에서 단말노드까지 한번에 진입하여 탐색하는 스택 기반 알고리즘이다. 즉 최단거리를 구하는 알고리즘으로 적합하지 않다. DFS로 탐색을 시도하면 가능한 모든 경로를 탐색하기 때문에 최단거리가 나오지 않는다. BFS 알고리즘을 사용해서 문제를 풀기 위해서는 탐색된 노드의 순서를 기록하는 2차 배열이 필요하다. 완전탐.. 2022. 3. 8. 백준 1260 DFS와 BFS 알고리즘 자바 JAVA 백준 1260번 문제는 DFS(깊이우선탐색)과 BFS(넓이우선탐색) 알고리즘을 이해하는 문제다. 비선형 자료구조인 트리구조에서 탐색을 하기 위해서는 노드(node)와 브랜치(branch)를 이동하면서 각각의 노드값을 기록해야 한다. DFS(Depth First Search, 깊이우선탐색) 깊이우선 탐색은 노드의 깊이가 깊은 순서를 먼저 탐색하는 알고리즘이다. 노드의 시작은 1부터 시작하고, 가장 깊은 곳의 노드까지 방문을 마치면 다음 자식노드로 이동해서 노드의 끝가지 이동하게 된다. DFS 알고리즘은 인접행렬 자료구조와 재귀 알고리즘을 사용해서 구현 가능하다. DFS를 구현하기 위해 사용되는 인접행렬은 대칭행렬의 모습을 가지고 있다. 백준 1260번에서 처음 입력값을 유한 그래프로 표시하면 아래와 같다... 2022. 3. 3. 백준 1780 종이의 개수 알고리즘 자바 JAVA 백준 1780 종이의 개수 알고리즘 문제 백준 1780 종이의 개수 문제는 분할정복 알고리즘 방법으로 풀수 있는 문제다. 주어진 숫자들을 비교해서 -1,0,1 세 가지 경우의 수를 판별해서 종이의 개수를 카운팅 하는 문제다. 기본적인 논리는 백준 1992번 쿼드트리 문제와 동일하다. 다만 다른점은 색종이의 갯수가 N/3 단위로 쪼개진다는 것이다. 입력값 맨 처음 주어지는 숫자 N은 3의 지수승으로 만들어진 숫자다. N(1 ≤ N ≤ 37, N은 3k) 동일한 알고리즘으로 구현하되, 색종이를 쪼개는 분기를 9번씩 돌아가면서 진행해야 한다는 점이 유일한 차이점이다. 백준 1992번 쿼드트리 분할정복 알고리즘 JAVA 자바 백준 1992번 쿼드트리 알고리즘은 분할정복 알고리즘 시리즈다. 전체의 문제를 작은 단.. 2022. 3. 2. 백준 1992번 쿼드트리 분할정복 알고리즘 JAVA 자바 백준 1992번 쿼드트리 알고리즘은 분할정복 알고리즘 시리즈다. 전체의 문제를 작은 단위로 쪼개는 작업이 첫번째로 고려되어야 한다. 백준 1992번에서 제시된 쿼드트리는 압축 알고리즘으로 사용되는 방법 중 하나다. 동일한 점들이 모여있는 곳을 압축해서 간단하게 표현하는 방법이다. 쿼드 트리는 4개의 자식노드를 가진 트리구조다. 주어진 문제에서 흑과 백으로 이루어진 N*N 정사각형이 있다고 하면, 동일한 값으로만 이뤄진 N*N 정사각형으로 분해를 하는 것이다. 만약 값이 다른 정사각형이 발견되면 4등분을 하게 되고 분할된 정사각형에서 동일한 작업을 이어가게 되는 것이다. 위에서 흑과 백이 동시에 존재하는 정사각형을 4등분하게 되면 왼쪽 위부터 1사분면, 오른쪽 위를 2사분면, 왼쪽 아래를 3사분면, 오른쪽.. 2022. 3. 1. 백준 알고리즘 7615번 해싱 탐색 자바 JAVA 메모리 초과 문제 백준 알고리즘 7615번은 해싱탐색 알고리즘으로 풀어보는 문제다. t,a,b,x,n,c,d,m 총 8개의 입력값이 주어지는데, t번 순회를 돌면서 a부터 m까지 입력된 변수들을 토대로 해싱함수를 정의하게 된다. 해시탐색(Hash Search) 해싱함수를 사용해서 데이터를 검색하는 방법이다. 기존의 탐색법과는 다르게 데이터의 내용과 인덱스를 미리 연결해서 짧은 시간안에 탐색이 가능한 알고리즘이다. 적절한 해싱 함수를 이용해서 데이터의 저장 위치를 결정한다. 결정된 저장 위치가 중복 혹은 충돌 되는 경우 다른 조치를 필요로 한다. 해시탐색 알고리즘의 시간복잡도는 n(1)이다. 입력값에 따라 연산의 횟수가 증가하지 않고 일정하다. 해싱함수는 6가지 종류로 나뉜다. 제산법(Division) : 키를 특정 값으로.. 2022. 2. 24. 이전 1 2 다음 반응형
