HOONDOC

1260번: DFS와 BFS 🌱풀이 알고리즘 BFS, DFS를 각각 구현하면되는 문제다. DFS는 Stack 자료 구조의 형태를 차용하며, 이는 재귀 함수로 구현되었다. BFS는 Queue 자료 구조의 형태를 차용하며, Queue를 사용했다. 그래프는 인접 리스트의 형태로 선언하였다. 문제 조건 중 하나가 동일 에지에 연결된 다른 에지들은 크기순으로 탐색되어야 하므로, Collections.sort()를 통해 간단하게 정렬을 했다. DFS가 끝난 뒤에는 BFS를 위해 방문 배열을 초기화해야한다. 기본 DFS, BFS이므로 구현이 안되면 다시 공부해보자. 메모리 : 34668KB, 시간 : 420ms package book_algoTEst; import java.util.ArrayList; import j..

13023번: ABCDE 🌱풀이 알고리즘 각 사람을 기준으로 DFS를 돌며, 깊이가 5에 도달하는 경우가 있는지를 확인한다. 확인을 위해 arrive라는 boolean형 변수를 선언하여 종료 조건에서 true로 바꾼다. 인접 리스트를 선언하여 무방향 그래프를 표현한다. 특이하게도 visited 배열을 true로 바꿨다가 해당 에지의 탐색이 종료되면 false로 초기화한다. 이는 0번 사람을 기준으로는 깊이 5가 나오지 않을지라도 4번 사람을 기준으로는 깊이 5가 나올 수 있기 때문이다. 예제 2번에서 확인할 수 있다. 단순하게 에지를 한번씩 탐색하는게 목적이라면 false로 바꿔주지 않아도 된다. 하지만 이번 문제처럼 각 에지별 깊이를 알고 싶거나 하는 등의 더 많은 방문을 필요로 하는 경우에는 초기화 ..

2023번: 신기한 소수 🌱풀이 알고리즘 백트래킹이 핵심이다. 백트래킹의 조건은 아래와 같다. DFS(a, b) 중 a는 자릿수의 숫자, b는 자리수다. DFS(2,1)은 일의 자리가 2일때다. 한 자리 수에서 존재하는 소수는 2,3,5,7 뿐이다. 첫째 자리 수가 2,3,5,7일 때 자리수를 높여가며 DFS 탐색을 코드를 작성하면 된다. DFS 메소드의 첫 줄에는 종료 조건을 작성한다. 목표 자리수에 도달했을 때의 숫자가 소수이면 모든 조건을 만족했으므로 출력 한다. 아래 1부터 9까의 반복문은 모듈러 연산을 통해 소수를 판단한다. 소수가 아니면 넘기고, 소수로 판명되면 자릿수를 높여 DFS 메소드를 호출해 재귀 함수를 만든다. 이 때 소수 판명은 메소드를 따로 작성해주는게 깔끔하다. 메모리 : 115..

11724번: 연결 요소의 개수 🌱풀이 알고리즘 연결 요소의 개수가 무엇인지 알아야 풀 수 있다. 서로 연결된 에지들은 하나로 취급한다. 즉 연결되지 않은 독립된 에지 그룹이 몇 개인지 묻는 문제다. 재귀 함수 구조를 이용한 깊이 우선 탐색 DFS를 구현했다. 그래프 구현에는 3가지 방법이 있다. 에지 리스트, 인접 행렬, 인접 리스트. 이 중 인접 리스트는 구현이 가장 까다롭지만, 성능이 가장 뛰어나다. 그래서 인접 리스트를 적용했다. 인접 리스트는 ArrayList 배열을 선언하여 그래프를 표현한다. 선언 과정을 유심히 보면 좋다. 한 번 탐색한 곳은 탐색하지 않으므로 boolean형 visited[] 을 선언하여 조건문에 활용한다. 가장 기본적인 형태의 재귀함수 이므로 이해하고 외워두기. 메모리 :..

10989번: 수 정렬하기 3 🌱풀이 알고리즘 기수 정렬을 이용한 알고리즘이다. radixSort(A,5)에서 radixSort는 기수 정렬을 의미하고, A는 배열, 5는 최대 자릿수다. 이해 안됨.. 쉬었다하자. 메모리 : 336892KB, 시간 : 2732ms import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { static int[] A; static long result; public static void main(String[] ar..

1517번: 버블 소트 🌱풀이 알고리즘 버블 소트로 체크하면 시간 초과 날 것이다. 이전에 병합 정렬에 대해 배웠고, 병합 정렬에서도 swap은 일어나므로 여기서 체크해보자. 일반적인 병합 정렬의 코드에서 카운트 해 줄 변수 result를 선언하고, 얘를 갱신해나가자. result가 갱신되는 위치는 우측 집합이 좌측 집합보다 작아서 수 교환이 일어날 때다. 그냥 result++하면 안되냐고 할 수 있다. 나도 그렇게 했다가 틀렸다. 버블 정렬에서의 swap은 인근의 숫자와 바꾸기 때문에 그렇다. 아래 병합 정렬 코드에서 일어난 swap을 버블 정렬에서 구현하려면 두 숫자의 인덱스 차이만큼 swap이 발생해야 한다. 그래서 바꿀 숫자들의 인덱스의 차를 더해주는 것이다. 메모리 : 95556KB, 시간 : ..

2751번: 수 정렬하기 2 🌱풀이 알고리즘 병합 정렬을 사용했다. mergeSort의 s는 시작 인덱스, e는 종료 인덱스다. 다르게 말하면 s는 우측 인덱스, e는 좌측 인덱스다. 투 포인터 마냥 pivot 인덱스를 향해 다가온다. e-s < 1 일 때 return 하는 건, 두 인덱스가 같거나 시작 인덱스가 종료 인덱스보다 큰 경우다. m은 pivot 인덱스다. 시작과 종료 인덱스의 중간으로 하는게 일반적이다. mergeSort(s,m) 과 mergeSort(m+1,e)를 호출한다. 이로서 m번 인덱스를 기준으로 좌측, 우측으로 범위가 절반씩 쪼개지는 재귀 함수가 호출된다. for(int i = s; i

11399번: ATM 🌱풀이 알고리즘 삽입 정렬을 사용하든, 버블 정렬을 사용하든 상관없다. 연습삼아 삽입정렬로 했다. 최초 반복문의 i는 검사하고자 하는 값의 인덱스다. 인덱스와 값은 따로 빼둔다. 내부 반복문에서 j는 검사하고자 하는 인덱스보다 낮은 인덱스들이다. 즉, 검사하고자 하는 인덱스의 번호는 갈수록 커지고 검사 범위의 인덱스는 검사 인덱스보다 1 낮은 상태에서 0까지 감소하며 진행된다. 검사 중 만약 검사 인덱스보다 작은 값이 있다면, 해당 인덱스를 저장하여 기억해둔다. 나보다 작은 값이 없다면 내가 가장 작은 값이므로 j == 0 일 때도 기억해둔다. 검사 인덱스와 기억해둔 인덱스 사이를 돌며 배열 값을 하나씩 뒤로 미룬다. 마지막에는 기억해둔 인덱스의 값을 입력한다. 메모리 : KB, 시..