BFS (너비 우선 탐색) BFS의 장점 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠름 너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다. 최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다해도 최단경로를 반드시 찾을 수 있다. BFS의 단점 재귀호출의 DFS와는 달리 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다. 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기에 비현실적이다. BFS 구현 Queue에 루트를 넣어주고, 아래의 순서를 반복하면 된다. Queue에서 하나의 노드를 꺼냅니다. 해당 노드의 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입합니다. /..
학습할 것 클래스 정의하는 방법 객체 만드는 방법 (new 키워드 이해하기) 메소드 정의하는 방법 생성자 정의하는 방법 this 키워드 이해하기 클래스의 개념 먼저 클래스의 개념에 대해서 짚고 넘어가야 할 것 같아서, 공부해 보았다. 클래스란 객체를 정의하는 틀 또는 설계도와 같은 의미로 사용됩니다. 자바에서는 이러한 설계도인 클래스를 가지고, 여러 객체를 생성하여 사용하게 됩니다. 클래스는 객체의 상태를 나타내는 필드와 객체의 행동을 나타내는 메소드로 구성이 됩니다. 객체(Object) 사전적 의미 : 물건 또는 대상 객체의 상태(state)와 행동(behavior)을 구체화하는 형태의 프로그래밍을 객체 지향 프로그래밍이라고 한다. 예를 들어서, "나는 과일장수에게 두 개의 사과를 구매했다"라는 문장을..
www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 분석 저번 N과 M(1) 에서 살짝 변형이 된 문제다. 예제를 먼저 살펴보면 자연수의 범위는 4이고, 2개씩 출력시키면 되는데, 같은 수가 중복되서 연속되면 안되고, 수열도 중복이 되면 안된다. (예를 들어, [1 2] 와 [2 1]은 같다고 본다.) 실행 과정 그림처럼, arr[0]에 for문으로 돌면서 i값을 넣어주고, 다음 arr[1]값은 재귀 호출을 돌면서 채우는 식으로 진행된다. 이 실행 과정을..
백트래킹 이란? 백트래킹은 모든 조합의 수를 살펴보지만, 조건이 만족할 때만 살펴보기 때문에 어떤 경우에 따라 훨씬 빠를수도 있다. 백트래킹 실행 순서 백트래킹은 DFS(깊이 우선 탐색)을 먼저 실행하면서 더 이상 탐색을 진행할 수 없는 상황이면 다시 되돌아 가서(백트래킹) 탐색을 진행한다. 관련 문제를 풀어보면 이해가 잘 될 것이다. www.acmicpc.net/step/34 백트래킹 단계 조금 더 복잡한 백트래킹 문제 1 www.acmicpc.net N과 M (1) 풀어보기 자연수 N이 주어지면 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력하면 된다. 예를 들어, N : 3 , M : 3 일때, 중복 없이 아래 처럼 출력시키면 된다. ---------------------------..
JUnit을 추가하는 방법을 모르신다면 [JUnit] - JUnit5 시작하기 를 참고 하시길 바랍니다. [JUnit] - JUnit5 시작하기 JUnit이란? 자바용 단위 테스트(Unit Test) 도구 장점 테스트를 하기 위해 일일히 System.out.prinlnt 로 찍어볼 필요가 없다. @Test 메소드가 호출될 때 마다 새로운 인스턴스가 생성되어 독립적인 테스트 iseunghan.tistory.com JUnit 기본 Annotation @BeforeAll 해당 annotation이 달린 메소드는 모든 메소드가 실행되기 전에 가장 먼저 실행된다. 반드시 static 으로 선언 되어야 한다. 이전의 @BeforeClass 와 동일 @BeforeAll static void before() { // ..
JUnit이란? 자바용 단위 테스트(Unit Test) 도구 장점 테스트를 하기 위해 일일히 System.out.prinlnt 로 찍어볼 필요가 없다. @Test 메소드가 호출될 때 마다 새로운 인스턴스가 생성되어 독립적인 테스트가 이루어진다. 단정(assert) 메소드로 테스트 케이스의 수행 결과를 판별할 수 있다. TDD(테스트 주도 개발)이 가능하다. 시작 하기 개발 환경 IntelliJ IDEA (2020.2.4) JDK 1.8 JUnit 5 Maven Dependency org.junit.jupiter junit-jupiter-api 5.7.0 test mvnrepository.com/search?q=junit Maven Repository: junit Module "junit-jupiter-a..
