DFS
DFS로 미로 탈출하기
최단거리 알고리즘을 공부하면서 예전해 만들었었던 미로 찾기를 다시한번 해봤다. 초년생때 이런문제가 어려웠는데 다시해보니 크게 어렵지는 않은것 같다. DTO package dto; /** * Maze 블록의 정보를 보관하는 DTO * * @author rokki * */ public class MazeBlock { private int x; // x 좌표 private int y; // y 좌표 private int count; // 카운트 public MazeBlock(int x, int y, int count) { this.x = x; this.y = y; this.count = count; } public int getX() { return x; } public void setX(int x) { th..
백준 4936 - 섬의개수
결국은 순회하면서 하는 DFS를 했는데 다음번에는 DP 또는 그래프 문제를 좀 많이 풀어 보고 싶다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126import java.util.*; public class Main { public static void main(String[..
백준 알고리즘 2583 - 영역 구하기
백준 알고리즘 2583번 영역구하기 문제는 DFS를 사용해서 구현해봤다. 문제지를 보자마자 읽기 싫어졌지만 읽어보면 되게 단순하게 많이 접해봤던 문제인거 같다. https://www.acmicpc.net/problem/258312345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612..
재귀 문제점과 꼬리 재귀와의 함수 비교
재귀함수는 자기 자신을 호출하는 방식으로 다양하게 사용된다. 재귀함수에는 일반재귀와 꼬리 재귀가 있는데 나는 둘 다 사용해온것 같은데 정확한 명칭과 사용방법에 대해서는 제대로 알지 못하는 것 같아 정리하게 되었다. 코드도 짧고 간결한 장점이 있다. 하지만 결국에는 함수를 계속 호출하는 방식이기에 함수가 끝나고 돌아가야할 위치에 대해 스택에 기록된다. 계속 함수가 호출되어 스택 영역의 최대 이상의 크기를 넘어가게 되면 Stack over flow가 발생한다. 편리함을 찾다가 더 위험한 상황이 초래된다. 그리고 성능적으로도 문제가 있다. 피보나치 수열의 예시를 확인해보자.12345private static int factorial(int n) { if (n == 1) return n; return n * f..
백준 6603번 로또 문제 풀이
매주 진행중인 알고리즘 공부 중 오늘은 백준 6603번 DFS와 백트래킹 문제를 풀어보자. #문제 https://www.acmicpc.net/problem/6603#풀이과정사용자로 부터 로또번호를 생성할 번호의 개수 k를 입력받고 입력받은 k개의 숫자를 이용하여 로또를 오름차순으로 6개짜리 배열을 만들어 출력해야한다. 처음에 문제를 보자마자 재귀를 써야겠다는 생각은 하였지만 백트래킹을 써야하는지는 감이 오지 않아서 고민을 많이 했다. 시작점을 0번째 부터 로또를 딱 만들수 있는 크기인 k - 5번까지 사용하는 반복문을 만들어서 배열을 만든다. 그리고 findLottoNum 메소드에 현재 인덱스와 만들고 있는 String값을 전달해준다. 그럼 현재 인덱스 바로 앞에 위치할 숫자를 구해서 String에 붙혀..