본문 바로가기

분류 전체보기854

재귀 함수 (3) 미로찾기 현재 위치에서 출구까지 가는 경로가 있으려면 현재 위치가 출구이거나 혹은 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나 boolean findPath(x,y) if(x,y) is the exit return true; else for each neighbouring cell (x', y') of (x,y) do if(x',y') is on the pathway if(findPath(x',y') return true; return false 미로찾기는 답이 Yes or No인 문제이다. boolean findPath(x,y) if(x,y) is either on the wall or a visited cell return false; else if (x,y) as .. 2021. 11. 11.
재귀함수 (2) 순환 알고리즘 설계 적어도 하나의 basecase, 즉 순환되지 않고 종료되는 case가 있어야 한다. 모든 case는 결국 base case로 수렴해야 한다. 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라. 순차탐색 int search(int[] data, int n, int target){ for(int i=0; i end) return -1; else if (target == data[begin]) return begin; else return search(data, begin+1, end, target); } 이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색 구간의 시작점을 명시적(explicit)으로 지정한.. 2021. 11. 10.
재귀함수 (1) 자기 자신을 호출하는 함수 void func(...){ ... func(...); ... } recursion이 항상 무한루프에 빠지는 것은 아니고 종료 조건을 알맞게 설정해주면 원하는 만큼 함수 호출이 가능하다. 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. → 종료 조건 recursion을 반복하다면 결국 종료조건으로 수렴해야 한다. 1~N까지의 합 public static int func(int n){ if(n == 0) return 0; else return n + func(n-1); } 팩토리얼 0! = 1 n! = n x (n-1) ! (n>0) public static int factorial(int n){ if(n == 0) return 1; else n * fact.. 2021. 11. 9.
백준 1260 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main1260 { public static ArrayList[] graph; public static int N; public static boolean[] visited; //방문 //dfs public static void dfs(int V){ //현재 노드.. 2021. 11. 7.
DFS/BFS 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DBS와 BFS를 꼽을 수 있는데, 이 두 알고리즘의 원리를 제대로 이해해야 코딩 테스트의 탐색 문제 유형을 풀 수 있다. 그런데 DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다. 자료구조는 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. 그 중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다. 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : 데이터를 삭제한다. 물론 실제로 스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로와 .. 2021. 11. 6.
백준 2798 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main2798 { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); // 카드의 개수 int M.. 2021. 11. 5.

티스토리툴바