오늘은 재귀에 대해서 정리해보려고 한다. 재귀는 코테에서 가장 많이 나오는 DFS, BFS를 이해하기 위해서 반드시 알아야 하는 내용이기 때문에 정리한 후에도 계속 여러 예제들을 풀어보면서 습득해야될 것 같다. 재귀는 쉽게 말해서 자기 자신을 호출하는 함수이다. 예를 들어, 1부터 10까지 더하여 출력하도록 작업한다면 아래와 같이 for문을 이용하여 출력하는게 먼저 떠오를 것이다. public class Main { public static void main(String[] args) { System.out.println(loop()); } public static int loop() { int n = 0; for (int i = 1; i
링크 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제 설명 풀이 과정 해당 문제는 브루트 포스를 이용하여 풀어야 한다. 그 전에 브루트 포스가 무엇인지 설명해보려고 한다. 브루트 포스란? 쉽게 말해서 모든 경우의 수를 탐색하여 요구조건에 해당하는 결과를 가져오는 것이다. 이 의미는 구현하기 쉽지만 모든 경우의 수를 탐색하기 때문에 결국 실행 시간이 오래 걸린다는 치명적인 단점이 있다. 핸드폰 잠금 방식 중에 4자리나 6자리 숫자로 된 핀번호를 입력..
링크 https://www.acmicpc.net/problem/1547 1547번: 공 첫째 줄에 컵의 위치를 바꾼 횟수 M이 주어지며, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 컵의 위치를 바꾼 방법 X와 Y가 주어지며, X번 컵과 Y번 컵의 위치를 서로 바꾸는 것 www.acmicpc.net 문제 설명 풀이 과정 두 가지 방법이 떠올랐는데, 공 위치를 담는 변수 A를 두고 if 문으로 그 때 그 때, A에 컵번호를 넣는 방법이 있고 arrayList와 Collections.swap 메소드를 이용하여 푸는 방법이 생각났다. 두 가지 방법이 메모리나 시간을 얼마나 소요하는지 확인해보고 싶어서 두 가지 모두 제출해봤다. 1) arrayList, Collections.swap() 메..
링크 https://www.acmicpc.net/problem/2490 2490번: 윷놀이 우리나라 고유의 윷놀이는 네 개의 윷짝을 던져서 배(0)와 등(1)이 나오는 숫자를 세어 도, 개, 걸, 윷, 모를 결정한다. 네 개 윷짝을 던져서 나온 각 윷짝의 배 혹은 등 정보가 주어질 때 도(배 한 www.acmicpc.net 문제 설명 풀이 과정 배 = 0, 등 = 1 이므로 도 = 3 ( 0+1+1+1), 개 = 2 (0+0+1+1), 걸 = 1 (0+0+0+1), 윷 = 0 (0+0+0+0), 모 = 4 (1+1+1+1) 가 된다. 입력 조건을 확인해보니 "네 개의 정수(0 또는 1)가 주어진다" 라는 조건이 있어서 0,1 외에 다른 입력 값은 없으므로 예외 조건을 생각 안해도 될 것 같았다. 그래서..
링크 https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열 www.acmicpc.net 문제 설명 풀이 과정 처음 문제를 봤을 때, split이 떠올라서 split으로 공백 기준으로 단어를 잘라서 해당 배열의 갯수를 출력하도록 아래와 같은 코드를 작성했다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in)..
