빙응의 공부 블로그

재귀란 자신을 정의할 때, 자신을 참조하는 것을 의미한다. 재귀함수란 함수 내부에서 자기 자신을 호출하는 함수를 말한다.📝재귀 함수그렇다면 사용하는 이유는 뭘까?변수의 사용을 줄여, 프로그램을 더 간결하고 이해하기 쉽게 만들 수 있다. 📌 작성 시 주의점무한 루프에 빠지지 않도록 종료 조건을 잘 성정하는 것이 중요하다.함수의 파라미터 및 인자 설정에 유의해야한다. DFS, BFS, 그리디에 자주 사용되므로 잘 알아두자.. 📝정렬정렬이 필요한 이유가 무엇일까?오름차순 및 내림차순으로 정렬되어 있다면 특정 원소를 좀 더 효율적으로 찾을 수 있다. 정렬은 여러가지가 있지만 특정 정렬이 빠르다고 항상 좋은 것이 아니다.데이터의 특성과 크기에 따라 적절한 정렬 방법이 필요하다.

대표적인 문자열 유형인 회문과 가로열에 대해 알아보자...📝 회문앞 뒤 방향으로 볼 때, 같은 순서의 문자로 구성된 문자열을 의미한다.쉽게 좌우 대칭이라 보면 된다.  public static boolean isPalindrome(String str) { int left = 0; int right = str.length() - 1; while (left  📝 올바른 괄호 문자열올바른 괄호 문자열이란 모든 괄호가 적절히 짝을 이루고 잇는 문자열을 의미한다.예를 들어 (), {}, [] 모두 올바른 괄호 문자열이다. 보통 스택을 통해 검증한다.  public static boolean isValidParentheses(String str) { ..

소수란 1과 자기 자신으로만 나누어지는 수를 의미한다.즉 약수가 2개이다.📝 소수 판별법사실 소수 판별법도 유클리드 호제법과 비슷하다 그 이유는 소수 판별법도 약수의 개념을 사용하기 때문이다.N의 약수의 개수를 세는 방법에는 크게 두가지가 있다.1부터 N까지의 수로 N을 나눔 O(N)1부터 루트N까지의 수로 N을 나눔 O(루트N) 위의 방법은 모두 특정 숫자 1개를 구하는 방법이다.그렇다면 특정 구간까지 모두 구한다면 어떻게 될까?기존 시간 복잡도에 x N을 해야할 것이다.더 좋은 방법을 찾아야 하는 셈이다. 📌 에라토스테네스의 체소수를 걸러내는 방법이다.동작 순서2부터 N가지 모든 정수를 적는다.아직 지우지 않은 소수 중 가장 작은 소수를 찾는다. 이 수를 P라고 한다.아직 지우지 않는 수들 중, ..

📝 유클리드 호제법(GCD)유클리드 호제법이란? 사실 어렵게 보이지만최대공약수를 구하는 것에 사용되는 것을 말한다.📌 약수 어떤 수를 나누어떨어지게 하는 수나머지가 0이되는 것을 말함N의 약수의 개수를 구하는 방법1부터 N이하의 정수를 n으로 나누어서, 나머지가 0이 되는 수의 개수를 찾는다.시간 복잡도 : O(N)1부터 루트 N 이하의 정수로 N을 나누어서, 나머지가 0이 되는 수의 개수를 찾고, 그 개수에 2를 곱함 N이 제곱수이면, 그 수에 1을 뺌시간복잡도 ; O(루트N)제곱수 : 어떠한 정수의 제곱이 되는 정수  📌 유클리드 호제법이란?호제법이란 말은 두 수가 서로 상대방 수를 나누어 원하는 수를 구하는 것을 의미한다.수학적 성질두 자연수 A, B에 대해서(A > B) A를 B로 나눈 나머..

📝 개요다음 순열 알고리즘은 현재 순열보다 큰 다음 순열을 찾는 알고리즘이다. [1,2,3]이 있다고 해보자 해당 숫자의 모든 가능한 순열은 아래와 같다. 1 2 31 3 22 1 32 3 13 1 23 2 1  📝 동작 방식다음 순열 알고리즘은 다음 순열을 얻으려면 피벗 포인트를 사용한다.  오른쪽에서 왼쪽으로 가면서, 현재 요소( i )와 바로 오른쪽 요소( i + 1 )를 찾는다.  i 피벗 포인트보다 오른쪽에 위치한 요소들 중에서 피벗 포인트의 값보다 큰 가장 작은 값을 찾는다. 피벗 포인트와 찾은 값을 교환한다.피벗  포인트의 오른쪽부터 끝까지의 요소들을 오름차순로 정렬한다. 여기서 주목할 점은 교환 동작 후 피벗포인트의 오른족 요소들이 내림차순으로 정렬되어 있다는 점이다. 1. 초기 순열[..

📝그래프 탐색 알고리즘 : DFS/BFS 탐색이란? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 대표적인 그래프 탐색 알고리즘이 바로 DFS와 BFS DFS와 BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 공부하자!!!! 📝공부 전 알아야 하는 지식 - 자료구조 스택 먼저 들어온 데이터가 나중에 나가는 형식(Last - In - First - Out)의 자료구조이다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있어요! import java.util.Stack; Stack stack = new Stack(); stack.push(""); //스택에 데이터를 추가 stack.pop(); //스택에서 데이터를 가져온다. (삭제됨) stack.peek() //스택 맨 위의..