목록백준 (6)

혼자 공부하는 공간

[JAVA] 백준 5397. 키로거(시뮬레이션, ListIterator) :: 로직/코드 - GODZ

안녕하세요 GODZ입니다. 오늘은 시뮬레이션을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 문제를 접하는 순간 문자열을 순회하면서 '', '-' 인 경우 따로 처리하고, 이 외의 경우에는 문자를 추가하는 방식으로 풀려고 했습니다. 하지만 LinkedList.add()나 remove() 메소드의 시간 복잡도가 문제가 되었습니다. 길이가 1,000,000이 되는 문자열의 각 문자를 add/remove하기엔 시간이 너무나도 오래 걸렸습니다. 때문에 Stack을 사용해도 되지만 저는 ListIterator 인터페이스를 사용하여 시간을 단축했습니다. ListIterator 인터페이스 ListIterator 인터페이스는 Iterator인터페이스를 상속받아 여러 기능을 추가한 List에서..
알고리즘/Simulation 2020. 7. 9. 14:24
[JAVA] 백준 6603. 로또(DFS) :: 로직/코드 - GODZ

안녕하세요 GODZ입니다. 오늘은 DFS를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 쉽게 말하면 로또 번호 1부터 49까지의 수 중에서 k개 (6 < k < 13)를 뽑아 집합 S라고 가정하고 이후 집합 S에서 6개를 뽑았을 때, 나올 수 있는 모든 수를 출력하는 문제입니다. 전형적인 "조합(Combination)" 문제라고 할 수 있습니다. 조합에서도 요소의 중복 가능 여부에 따라 DFS 반복문 코드가 달라지니 유의합시다. -- Tip -- 뽑은 6개의 숫자들이 다른 연산에 필요하다면 List에 저장해서 활용합시다. 하지만 이 문제처럼 출력만 할 뿐이라면 StringBuilder를 통해 출력하는 것이 List를 쓴 것보다 빠릅니다. 4. 로직 (조합) 이후에 조합과 순열..
알고리즘/DFS 2020. 7. 1. 01:30
[JAVA] 백준 11724. 연결 요소의 개수(BFS) :: 로직/코드 - GODZ

안녕하세요 GODZ입니다. 오늘은 BFS를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 2020/06/24 - [알고리즘/BFS] - [JAVA] 백준 2667. 단지번호붙이기 (BFS) :: 로직/코드 - GODZ [JAVA] 백준 2667. 단지번호붙이기 (BFS) :: 로직/코드 - GODZ 안녕하세요 GODZ입니다. 오늘은 BFS을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 단지의 탐색의 종료와 새 단지의 탐색의 시작 사이에 단지 수를 +1 합니다. 각 단지의 집 수� godzz.tistory.com 위의 문제 기억하시나요? 인접한 칸들을 한 단지로 보고 단지의 갯수를 카운트하는 문제였습니다. 이 문제도 무방향 그래프에서 연결된 정점들을 ..
알고리즘/BFS 2020. 6. 26. 21:57
[JAVA] 백준 1697. 숨바꼭질 (BFS) :: 로직/코드 - GODZ

안녕하세요 GODZ입니다. 오늘은 BFS를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 각 위치를 하나의 노드라고 생각하고, 이동할 수 있는 위치(+1, -1, *2)에 대해 각각을 다음에 탐색할 노드라고 생각하면 BFS로 풀 수 있습니다. 이전 BFS 문제들과는 달리 각 노드에 대한 연결관계를 설정하지 않아도 되기에 더 간단하게 풀 수 있습니다. 4. 로직 플로우 차트를 통해 보여드리겠습니다. 다음엔 더 깔끔한 플로우 차트를 만들겠습니다. 만들고 나니 깔끔하지는 않네요. 여기서 방문체크 및 이동 횟수를 저장할 자료구조를 배열과 해시맵을 통해 각각 구현을 해보았습니다. 다음 위치 N'를 Key로, 이동 횟수를 Value를 가지는 HashMap 다음 위치 N'를 Index로, ..
알고리즘/BFS 2020. 6. 26. 14:48
[JAVA] 백준 2667. 단지번호붙이기 (BFS) :: 로직/코드 - GODZ

안녕하세요 GODZ입니다. 오늘은 BFS을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 단지의 탐색의 종료와 새 단지의 탐색의 시작 사이에 단지 수를 +1 합니다. 각 단지의 집 수를 오름차순으로 정렬해야하기 때문에 해당 정보를 위한 자료구조를 만듭니다. 2에서 나눈 단지 번호와 집의 수가 맵핑되지 않아도 되기 때문에 Map구조가 아닌 List나 배열을 사용하셔도 좋습니다. (저는 처음에 문제를 제대로 안읽어서 HashMap을 사용했습니다.) 4. 로직 2차원 배열을 순회하며 값이 1이고, 해당 좌표가 방문한 적이 없는 곳인 경우 단지 카운트를 증가, 방문 값을 true로 바꾸고 현재 좌표를 큐에 넣습니다. 큐 poll()로 값을 추출하고, 해당 단지의 집 갯수를 위해 집 카..
알고리즘/BFS 2020. 6. 24. 20:55
[JAVA] 백준 2178. 미로 탐색 (BFS) :: 로직/코드 - GODZ

안녕하세요 GODZ입니다. 오늘은 BFS를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 지도 정보를 담을 2차원 배열 생성합니다. 시작이 (0,0) 이 아닌 (1,1) 이기 때문에 개인적으로 인덱스에 대한 혼동이 오지 않도록 (N+1) x (M+1) 크기로 만들었습니다. 좌표를 큐에 저장할 때는 클래스로 만드는 게 편리합니다. 상/하/좌/우 인접한 좌표로 이동할 수 있기 때문에 해당 좌표가 방문했던 곳인지 아닌지를 판단하기 위해 같은 크기의 2차원 배열이 필요합니다. 상/하/좌/우에 대해 검사할 때는 dx(상하좌우 각각에 대한 x좌표 변경값), dy(상하좌우 각각에 대한 y좌표 변경값)의 배열을 만들어 반복문을 통해 체크합니다. 5번의 경우 dx, dy 배열을 만드는 이유는 ..
알고리즘/BFS 2020. 6. 24. 02:13
Prev 1 Next