https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net DFS로 풀었다가 시간초과가 나서 BFS로 변경해 풀었다. 달라진 것은 당연히 DFS는 재귀, BFS는 큐를 이용한다는 것이다. 최단 거리를 구할 땐 BFS를 쓰는게 최소값을 구하기 위해 비교하지 않아도 되고 편하다! visit 배열을 boolean에서 int 형으로 바꿔 뎁스를 표시 해줬는데, 이는 이전에 풀었던 백준 1697번 문제와 같은 방식이다. 그땐 그 풀이가 잘 이해되지 않았는데 이번 문제를 통해 BFS 최단거리 알고..

https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net BFS로도 풀 수 있지만 DFS로 풀었다. 한 묶음을 돌고 나서 또 어떻게 돌아야 하나 고민했는데 visit 체크를 하여 for문을 돌면 해결 됐다. 또 처음엔 DFS 함수에 'W'인지 'B'인지 넘겨주지 않았는데 그렇게 되면 무한 루프에 돌게 된다.. DFS 재귀를 이용하기 위해서는 재귀를 들어가는 if문을 잘 작성해야 한다! 혹은 재귀가 끝나는(return) if문을 ..

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 프로그래머스 여행 경로와 거의 비슷한 문제다. 단어의 1글자만 다른 것을 찾아서 DFS로 풀면 된다. 1글자를 찾기 위해서 처음엔 begin, target는 1차원 배열로 words는 2차원 배열로 변경하려 했으나 간단한 방법이 있음을 깨닫고 charAt 함수를 이용해 비교했다. 주석 처리 해둔 부분은 처음에 retur..

https://www.acmicpc.net/problem/2501 2501번: 약수 구하기 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. www.acmicpc.net 약수를 구하고 인덱스에 맞춰 불러오기만 하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class bj2501 { public static void main(String[] args) throws IOException {..

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 자바에는 PriorityQueue 가 있으므로 이를 이용하자. 직접 구현하려다 너무 복잡해서 찾아보니 자바 내에 이미 존재했다.. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Collections; import java.util..

개념 자료구조 힙(heap)은 완전 이진 트리(이진트리이면서 자식 노드가 빠짐없이 모두 달린 것). 우선순위 큐 자료구조를 위해 만들어진 자료형으로 최소, 최대 값을 빠르게 찾기 위함. 종류 종류는 최대힙, 최소힙 두가지가 있다. 최대힙 최소힙 부모노드가 가진 값이 자식노드가 가진 값보다 크거나 같음 부모노드가 가진 값이 자식노드가 가진 값보다 작거나 같음 형식 힙은 배열 형식으로 나타낼 수 있다. 배열의 0번은 사용하지 않으며 루트 노드가 1, 왼쪽 자식노드는 2, 오른쪽 자식노드는 3 ... 이렇게 쭉쭉 나아간다. 인덱스 계산 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1 부모 노드 인덱스 = 자식 노드 인덱스 / 2 삽입 방법 배열의..

https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 여행경로 문제에 대해서 DFS로 풀어보자. 모든 경로를 사용해야 하므로 tickets.length와 현재 뎁스 카운트가 같아지면 재귀를 탈출하게 짰다. 처음엔 간선이 주어졌다 생각하고 공항들을 숫자로 바꿔 해야 하나 했지만 복잡해 풀이를 찾아보니 간단하게 문자열로 나열, 덧붙이는 방법이 있었다. 이를 나중에 공백으로 쪼개어 배열..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 이용해 문제를 풀어보자. 처음엔 프로그래머스의 타겟넘버와 비슷한 문제인 줄 알고 DFS로 풀려고 하였으나, 가장 짧은 경로를 찾는 것이므로 각 뎁스를 따질 수 있는 BFS가 적절했다. 큐에 다음 숫자를 넣을 때 if 문에서 num + 1, num - 1, num * 2의 범위를 재줘야 한다. 그렇지 않으면 런타임에러가 날 수 있음! 처음엔 num + 1