본문 바로가기

CODING TEST/THEORY11

임시) 정수론 소수 구하기 개념은 쉽게 이해되고, 시간 복잡도가 nlog(logn)이라는 게 신기하네 정도. 37번, 소수 구하기에라토스테네스를 이해해가지고 코딩으로 구현하는 코테 문제가 많이 나와요.  n의 제곱근까지만 탐색하는 이유즉 예로 16은 (1,16), (2,8), (4,4) 이렇게 약수가 있지. 이 때 우린 1, 2, 4 즉 괄호의 왼쪽 부분만 탐색하고 싶은 거야왜 굳이 오른쪽 부분, 즉 16, 8, 4 이런 부분까지 일일이 루프 돌면서 해당 수와 짝지어 지는 약수 있는지 탐색해야 함?이미 n의 제곱근 이하인 수로만 탐색해서 소수 아닌 거 다 판별하면, 그럼 n의 제곱근 이상의 수들을 가지고 다시 할 필요 없지. 이미 다 했는데. 이미 n 제곱근 이상의 수들을 가지고 해당 수로 나눠지는 걸 판별하는 짓을 .. 2024. 6. 18.
임시) 그리디 그리디 알고리즘 그리디를 썼을 때 최적의 해를 도출해 낼 수 있는 문제가 있고 아닌 게 있음⇒ 이 문제에 그리디 쓸 수 있는지 판단해야 함뭔가 문제 보니까 최소, 최대를 구하는 문제가 많네그리디 알고리즘은 또 우선순위 큐와 자주 쓰이네또는 정렬하는 로직이 자주 쓰이네 문제 32, 동전 개수의 최솟값 구하기 그리디 썼을 때 반례 안 생기는 지 한번 따져봐야 함(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)즉 2 4 8처럼 배수 관계란 소리 → 그냥 현재 상태에서 가장 큰 동전부터 차례대로 나눠주면 되는 게 성립이 되는 것임반례) 동전 1 6 7 있고, 금액 12를 맞춘다면그리디 알고리즘 → 7이 1개, 1이 5개그러나 동전 최소값은 → 6이 2개배수 형태가 .. 2024. 6. 13.
임시) 탐색 깊이 우선 탐색 가장 많이 사용, 매우 중요인접 리스트, 방문 배열을 만들고 시작스택을 쓸지, 재귀를 쓸지 알아서, 보통 재귀를 쓰긴 함스택과 재귀의 유사성호출 스택(Call Stack) 사용:재귀 함수: 재귀 함수가 호출될 때마다 현재 함수의 실행 상태(매개변수, 로컬 변수 등)가 호출 스택에 저장됩니다. 함수가 종료되면, 스택에서 이전 상태로 되돌아갑니다.스택: 명시적으로 데이터를 쌓고 제거하는 데이터 구조로, 후입선출(LIFO) 원칙을 따릅니다.후입선출(LIFO) 원칙:재귀 함수: 가장 마지막에 호출된 함수가 가장 먼저 종료됩니다. 이는 스택의 후입선출 원칙과 동일합니다.스택: 가장 마지막에 추가된 데이터가 가장 먼저 제거됩니다.함수 호출 관리:재귀 함수: 각 재귀 호출은 호출 스택의 새로운 프레임.. 2024. 6. 9.
[임시] 정렬 보통 정렬 쓸 땐 퀵 정렬이나 병합 정렬을 많이 코테에서 쓴다고 함버블 정렬 버블 정렬: 데이터 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식한 번 반복할 때마다 가장 큰 요소가 제일 뒤에 가게 됨(오름차순 기준)  => 그럼 제일 뒤의 요소들은 정렬되어 건드릴 필요가 없는 영역임.간단하게 구현 가능하지만, 시간 복잡도가 n의 제곱으로 다른 정렬 알고리즘보다 속도 느림구현 원리는 영상과 교재 보기문제 15, 수 정렬하기, 2750번 이 문제 그냥 sort로 해결 가능굳이 버블 정렬로 구현하면 이중 for문으로 가능 for (int i = 0; i       for (int j = 0; j         if (A[j] > A[j + 1]) {           int temp = A[j.. 2024. 6. 3.
[임시] 스택과 큐 이론 스택pop은 삭제하고 확인, peek은 단순 확인만깊이 우선 탐색(DFS), 백트래킹에 효과적. 후입선출은 재귀 함수 원리와 일맥상통하기 때문물론 스택보다 재귀를 좀 더 쓰긴 함그래도 구조가 특이해서 가끔 응용문제가 나오니, 원리만 잘 알아두기 큐선입선출, 양방향에서 삽입과 삭제추가는 큐의 rear에서, 삭제는 큐의 front에서너비 우선 탐색(BFS) 구현할 때 자주 사용 큐랑 스택은 배열의 확장판큐랑 스택은 자료구조 자체를 이용하기도 하지만,개념을 이해하고 이에 따라 문제 푸는 경우 많음=> 후입선출, 선입선출 두 원리만 잘 이해하면 됨 우선순위 큐들어간 순서 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조front에 따라 항상 최댓값 또는 최솟값 위치힙을 이용해 구현함 관련 문제 [ja.. 2024. 5. 29.
[임시] 슬라이딩 윈도우 공통: 블로그 글과 책 내용 및 필기를 내 병행해서 보기 [Java] 문제 009 (백준 12891번)문제DNA 비밀번호설명  교재 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class P12891_DNA비밀번호 { static int checkArr[]; staperson-do-my-best.tistory.com  [java] 문제 010 (백준 11003번)문제최솟값 찾기 교재 풀이import java.io.*;import java.util.Deque;import ja.. 2024. 5. 28.
[Do it 코테 자바편] 투 포인터 설명 [Java] 문제 006(백준 2018번)문제수들의 합 5 (2018번) 풀이import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int count = 1; int start_index = 1; int end_index = 1; int sum = 1; whilperson-do-my-best.tistory.com 대표적인 유형이 006번이니, 이 문제 풀이나 접근법을 기준으로 삼고 개념으로 삼기startIndex와 endIndex가 각각 n번 훑으니 시간 복잡도는 2n이다 -> 이 때 상수는 무시하.. 2024. 5. 24.
[Do it 코테 자바편] 구간 합 설명 구간 합? a 배열에서 2~7번째 인덱스 값의 합을 구해란 것처리하기 쉽게 a 배열을 가지고 합 배열 s를 만들어 보는 거다.합 배열? 즉 s[4]가 a[0] + a[1] + a[2] + a[3] +a[4]가 되도록 만드는 배열즉 s[4]는 a[0]부터 a[4]까지 합한 값이 된다.왜 필요? 그야 구간 합을 자주 물어보면 a 배열로 일일이 반복문 돌려서 하면 느리니까.합 배열 만드는 법? s[0]은 a[0]으로 초기화 후, 그 다음부턴 s[i] = s[i-1] + a[i]하면 됨. 즉 s[4] = s[3] + a[4]합 배열로 구간 합 구하는 법? a[2] ~ a[5]의 합 => s[5] - s[1]왜? s[5]는 a0부터 a5까지의 합, s[1]은 a0부터 a1까지의 합 => 두 개를 빼면 a2+.. 2024. 5. 18.

티스토리툴바