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

4주차 내용정리 📌 DFS (Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문처리. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄. 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복 다음의 그래프를 DFS로 탐색해본다고 가정하자.(방문 순서는 1번부터 시작하여 인접한 노드중 번호가 낮은 노드를 방문) 탐색 순서 : 1→ 2 → 7 → 6 → 8 → 3 → 4 → 5 위의 과정을 ..

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

문자열, 배열, 자료구조 📌 코딩테스트 문자열 메소드 startsWith(str) : 문자열이 특정 문자로 시작되는지 판별 endsWith(str) : 문자열이 특정 문자로 끝나는지 판별 equal(str) : String 문자열 값 비교 indexOf(str) : 특정 문자열이 대상 문자열의 몇 번째 인덱스에 위치하는지 반환 특정 문자열이 없을 경우에는 -1을 리턴 substring : 지정한 범위에 속하는 문자열 반환 substring(index): index 위치를 포함하여 이후의 모든 문자열을 리턴 substring(beginIndex, endIndex) : beginIndex에서 endIndex-1까지의 부분 문자열을 반환 replace(beforeStr, afterStr) : 특정 문자열을 새..

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