5주차 내용정리 📌 백트래킹 백트래킹(Backtracking) 이란 ? 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다. 스무고개를 생각하면 쉽게 이해할 수 있음. ex ) 미로탐색 미로 탐색 문제같은 경우, 출발지부터 상,하,좌,우로 경우의 수를 dfs로 뻗어나가게 되는데, 더이상 진행할 수 없는 경우 다른 경우의 수로 해를 찾게된다. 📌 조합 nCr = n! / (n-r)! * r! 이 공식을 쓰지 않고 다음 공식을 쓴다. nCr = n-1Cr-1 + n-1Cr 위의 공식으로 예를들어 5명중에서 3명을 뽑는 경우의 수를 식으로 풀면 다음과 같다. 5C3 = 4C2 + 4C3 말로 풀어서 이야기 하면 5명중에서 3명을 뽑..

문제 링크 연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net ❗ 풀이 방법 문제가 복잡한 만큼 로직을 나눠서 생각한 뒤, 구현해주는 것이 좋다. 문제를 읽어보면 다음의 세가지 로직이 필요한 것을 깨달을 수 있다. 벽을 세워보는 로직 바이러스를 퍼트리는 로직 안전영역의 갯수를 세는 로직 이렇게 정리가 되었다면, 다음은 위 세가지 로직을 어떻게 구현할 지 생각해보아야 한다. 벽을 세워보는 로직 모든 조합수를 따져보아야 하니 백트래킹으로 벽을 세워보고 허물어보고 하는식으로 하는것이 적절하지 않을까? 따라서 벽을 3개까지 세..

문제 링크 순열 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static int count; static String answer; static char[] arr; static boolean[] visited; static boolean flag; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { St..

문제 링크 로또 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static int k; static int[] arr; static boolean[] visited; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true) { k ..

문제 링크 N과 M 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static StringBuilder sb = new StringBuilder(); static int n; static int m; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); solution(); Sy..

문제 링크 N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ❗ 풀이 방법 대표적인 백트래킹 문제이다. 처음에 퀸의 위치를 1차원 배열에 기록하면서 백트래킹하는 아이디어를 떠올리지 못하여 2차원 배열의 체스판을 만든 뒤 모든 칸에 대하여 퀸을 놓아본 다음 퀸을 놓은 위치와 공격할 수 있는 위치를 방문처리하고, 카운팅한 다음 방문처리를 풀어주는 굉장히 수고스러운 로직을 구현하였는데 다른 사람의 풀이를 보고 해당 아이디어를 베껴와서 다시 풀었더니 쉽게 풀렸다.. private static int[] arr; priv..

문제 링크 토마토 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static class Position { int x; int y; Position(int x, int y) { this.x = x; this.y = y; } } // BFS 탐색을 위한 queue 선언 static Queue queue = new LinkedList(); // 방향벡터 정의 static int[] dx = {1, 0, -1, 0}..

완전탐색, 재귀함수 기본 📌 완전탐색(Brute Force) ✅ 완전 탐색이란? 모든 경우의 수를 다 체크해서 정답을 찾는 방법 (무식하게 가능한 거 다 해보겠다는 방법을 의미함) 예를 들어, 숫자 4자리의 암호로 구성된 자물쇠를 완전탐색으로 풀어보려고 한다면? 무식하게 0000 ~ 9999 까지 모두 시도해보면 된다. 📌 재귀함수 개념(Recursive Function) ✅ 재귀함수란? 자기가 자기자신을 호출하는 함수라고 생각하면 된다. 기본적으로 스택프레임을 이용한다 !!!! ✅ 재귀함수 연습 재귀함수로 숫자 n을 입력받고 1부터 n까지 출력 재귀함수로 n부터 1까지 출력해보기 숫자 n을 입력받고 재귀함수로 n! 계산해서 출력해보기 📌 피보나치 문제 💡 피보나치 수는 0과 1로 시작한다. 0번째 피보..

📌 목차 알고리즘 공부 Tip 시간복잡도, Big-O 표기법 실전 코딩테스트 Tip 입/출력(Scanner VS BufferedReader) 코딩테스트에 자주나오는 기본유형 / 심화유형 소개 📌 알고리즘 공부 TIP 알고리즘 개념을 학습하였으면 관련 알고리즘 문제를 백준, 프로그래머스에서 풀기(개인적으로 1일 1문제 추천) 직장인일 경우 직장인 코딩테스트 준비 팁 참고 문제풀 때 옆에 연습장과 샤프, 지우개 필수 실제 코딩테스트 환경에서도 빈종이와 필기구 까지 허용해주는 경우가 많음. 또한 코드 흐름을 머릿속에서 생각하는 것보다 연습장에 그림으로 그려가면서 생각을 종이에 옮겨보는 연습을 해볼수록 실력 기하급수적 상승 IDE의 자동완성 도움받아서 코드작성 금지 실제 코딩테스트 환경에서는 자동완성을 사용할 ..