섹션 2. 코딩테스트 - 05. 탐색 - (2) 이분 탐색
섹션 2. 코딩테스트 - 05. 탐색 - (2) 이분 탐색 ⬛ 05-3. 이진 탐색 🟦 이진 탐색 (=이분 검색) 이진 탐색 : 이미 정렬된 데이터에서 원하는 값을 찾아내는 알고리즘 정렬된 대상 데이터 중앙값 vs 타겟값 비교하여 검색 범위를 절반씩 줄여나감 시간 복잡도 : O(logN) 🟧 이진 탐색 핵심 (1) 이미 정렬된 데이터에서 중앙값 선택 (2) 키값 < 중앙값 : 중앙값의 왼쪽 데이터셋 선택 (3) 중앙값 < 키값 : 중앙값의 오른쪽 데이터셋 선택 (4) 중앙값 == 키값 : break 탈출 🟦 백준 1920번. 원하는 정수 찾기 for문으로 각 타겟 데이터셋 찍으면서 while()문으로 탐색 대상 데이터의 st≤ed 동안 mid 값과 현재 타겟값 비교하며 if, if else 문 통과하면 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 13.
섹션 2. 코딩테스트 - 05. 탐색 파트 - (1) DFS, BFS
섹션 2. 코딩테스트 - 05. 탐색 ⬛ 05. 탐색 (= 순회) 그래프의 순회 한 정점에서 시작하여 그래프의 모든 정점을 ‘한 번씩’ 중복 없이 방문하는 것 🏓그래프 순회의 종류 1) DFS (깊이 우선 탐색) 한 정점에서 시작하여 깊이 탐색하다가 다시 직전 정점으로 돌아와 깊이 탐색을 반복 (1) 정점 v 방문 (2) 정점 v에 대한 인접 정점들 中 (1개) 방문 방문 안한 w 존재 O : v 방문처리(push) 후, w 방문 (DFS(v) ) 방문 안한 w 존재 X : 더이상 방문할 w들이 존재하지 않으므로 복귀 pop (3) 스택(DFS) 공백되면 종료 2) BFS (너비 우선 탐색) 시작 정점에 대한 인접 정점들 모두를 차례로 방문하고, 다시 처음 방문했던 정점으로 되돌아와 너비 우선 탐색 반복..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 8.
섹션 2. 코딩테스트 - 04. 정렬 파트
섹션 2. 코딩테스트 - 04. 정렬 ⬛ 04. 정렬 ⬛ 04-1. 버블 정렬 🟦 버블 정렬 두 인접한 요소끼리 비교한 뒤, swap 연산 수행하며 정렬 O(n2) 속도 느린 편 🟦 백준 2750번. 수 정렬하기 -1 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. package to_0605_6; import java.util.*; /* 2750번. 수 정렬 하기 1 - 버블 정렬 사용 * */ p..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 5.
섹션 2. 코딩테스트 - 자료구조 (2) 파트
⬛ 03-4. ‘슬라이딩 윈도우’ 알고리즘 🟦 슬라이딩 윈도우 알고리즘 2개의 포인터로 고정 범위 지정한 뒤, 고정 범위를 옆으로 밀면서 이동함. O(n)으로 해결 원할 때 多 사용 크기를 유지한 상태로 이동하면서 조건에 맞는지 유효성 검사하며 탐색함 ⬛ 03-5. 스택과 큐 🟦 스택 (Stack) 삽입/삭제 연산이 후입선출 LIFO 로 이루어지는 자료구조 top 지칭하는 값(한쪽)에서만 삽입과 삭제가 일어남 🟧 스택 용어 1) 위치 top : 삽입과 삭제가 일어나는 위치 지칭 2) 연산 push : top 위치에 새 데이터 삽입 연산 pop : top 위치의 데이터 삭제 & 확인 연산 peek : top 위치의 데이터 단순 확인 연산 🟧 스택 활용 DFS(깊이 우선 탐색), 백트래킹 에서 多 활용 🟦 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 6. 5.
섹션 2. 코딩테스트 - 자료구조 (1) 파트
섹션 2. 코딩테스트 [기초] ⬛ 03. 자료구조 ⬛ 03-1. 배열과 리스트 🟦 배열과 리스트 🟧 배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 각 값은 인덱스를 통해 참조 가능 배열 크기는 최초 선언 시 지정 가능하며, 한 번 선언한 뒤 크기 변경 불가능 🟧 리스트 값과 포인터를 묶은 노드를 다시 포인터로 연결한 자료구조 선언 시 크기 별도 지정 안하므로 크기 정해져 있지 않다. ⬛ 03-2. ‘구간 합’ 알고리즘 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 미리 구간합을 구해놓는 알고리즘 **** 🟦 구간 합 알고리즘 1차원 배열의 합 배열 S[i] 🟧 1) 합 배열 S의 정의 S[i] = A[0] + A[1] + ... + A[i]; //A[0] ~ A[i]까지의 합 저장 🟧 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 31.
섹션 1. 코딩테스트 [준비] 하기 - 시간 복잡도, 디버깅
섹션 1. 코딩테스트 [준비] 하기 ⬛ 01. 시간 복잡도의 중요성 어떤 알고리즘으로 풀어야 하는가 ? 알고리즘 선택의 기준이 되는 ‘시간복잡도’ ⬛ 01-1. 시간 복잡도 표기법 🟦 시간 복잡도 시간복잡도 : 주어진 문제 해결을 위한 ‘연산 횟수’ 기본적으로 1억 번(10의 8승) 의 연산 = 1초의 시간으로 간주한다. 🟦 시간 복잡도의 유형 1) 빅-오메가 : ‘최선’일 때의 연산 횟수 표기법 2) 빅-세타 : ‘보통’일 때의 연산 횟수 표기법 3) 빅-오(O(n)) : ‘최악’일 떄의 연산 횟수 표기법 - 코테에서 사용 ⬛ 01-2. 시간 복잡도 활용하기 연산 횟수 = (알고리즘 시간복잡도) X (데이터 크기) 시간 제한을 확인하여 가능한 연산 횟수의 제한을 두고 생각할 것. 🟦 (1) 시간 제한 ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 30.
섹션4. Sorting & Thinking - (3)
🎈섹션4. Sorting & Thinking - (3) 🟦 4-5. 모임 장소 문제 풀이 완성 코드 최소거리가 될 중앙점 찾는 게 중요하다. row[] 에 각 학생 행 위치 좌표 담고 col[]에 각 학생 열 위치 좌표 담고 그 각각을 오름차순 정렬해준다. 오름차순 정렬된 인덱스가 갖는 좌표의 값(행, 열) 이 최소 이동 거리 좌표값이 된다. ⇒ 이유 : 모이는 지점이 모든 좌표(가장 밀접한 두 점) 의 중앙에만 위치한다면 (그 사이에만 존재한다면) 그 사이의 어디에서 모여도 최소 이동 거리가 동일하다는 사실을 이용한다. package to_0525_1; // 4-5. 모임 장소 import java.util.*; class Solution { //솔루션 함수 public int solution(int[..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 25.
섹션4. Sorting & Thinking - (2)
🎈섹션4. Sorting & Thinking - (2) 🟦 4-3. 카드 가져가기 문제 풀이 첫 시도 코드 1) 먼저 내림차순 정렬 한 뒤에 2) 기본적으로 영희 우선권이므로 (짝수 번째), 철수는 홀수번째 일텐데 3) k번의 철수 우선권이 존재하므로 각 케이스별 차이를 담을 배열을 생성하고 4) 차이가 클 때 철수가 우선권을 사용할 index값을 따로 담고 그 인덱스값의 2배에서 철수가 (짝수 번째) 값을 누적하여 사용할 수 있게 문제 풀이를 시도했다. → 코드가 꼬여서 마무리를 못했다. import java.util.*; class Solution { public int solution(int[] nums, int k){ int answer = 0; //복붙 ArrayList numsA = new A..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 24.
섹션4. Sorting & Thinking - (1)
🎈섹션4. Sorting & Thinking - (1) 🟦 4-1. 이진수 정렬 문제 풀이 첫 시도 코드 정답은 맞았는데 ,코드가 너무 길고 비효율적이다. 우선 객체를 NumCnt로 생성했다. 이 클래스의 경우 Comparable를 implements해서 내부적으로 compareTo메소드를 재정의할 수 있도록 했다. compareTo() 메소드는 기본적으로 cnt값 기준 오름차순 하되, 만약 두 객체간 cnt 값이 일치할 경우 num의 값 기준 오름차순 정렬이 되도록 재정의했다. 우선 [10진수 → 이진수(String) ] : Integer.toBinaryString() 사용하여 각 nums별로 이진수값을 tmp에 담은 뒤, tmp내부를 탐색하여 ‘1’을 가진 경우에 한해서 OneCnt[i]로 카운팅했다..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 22.
섹션3. 자료구조 활용 섹션 -(4)
🎈섹션3. 자료구조 활용 섹션 -(4) ⬛ 우선순위 큐 | Priority Queue 큐(Queue)는 FIFO 의 형태로 데이터를 처리한다. Priority Queue 는 우선순위를 먼저 결정한 뒤, 그 우선순위가 높은 요소부터 먼저 나가는 자료구조이다. import java.util.PriorityQueue; //import //int형 priorityQueue 선언 (우선순위가 내부 값 오름차순) PriorityQueue priorityQueue = new PriorityQueue(); //int형 priorityQueue 선언 (우선순위가 내부 값 내림차순) PriorityQueue priorityQueue = new PriorityQueue(Collections.reverseOrder()); /..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 4.
섹션3. 자료구조 활용 섹션 -(3)
🎈섹션3. 자료구조 활용 섹션 -(3) 🟦 3-3. 현관문 출입 순서 | 너무 어렵다. . . 이 문제는 큐를 2개 사용하여 대기열을 각각 만든다. prev 변수로 직전 현관문 사용 상태를 (0 or 1) 저장해두고 참고해야 한다. 시간 변수 t 가 하나씩 증가하면서 각 시간 별로 이용 사원을 세팅해야 한다. 완성 코드 package to_0502; /* 3-3. 현관문 출입 순서 | 진짜 개어렵다. .. */ import java.util.*; class Solution1 { //솔루션 함수 public int[] solution(int[] arrival, int[] state){ //들어오는 대기열 Queue enter = new LinkedList(); //나가는 대기열 Queue exit = ne..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 2.
섹션3. 자료구조 활용 섹션 -(2)
🎈섹션3. 자료구조 활용 섹션 -(2) 🟦 3-4. 피부과 문제 풀이 첫 시도 코드 이 문제는 enter 가 최대 100,000 이므로 이중 for문을 돌면 안되는데 도저히 해결 방법이 떠오르지 않아서 이중 for 문 사용하고 답은 나왔다. . package to_0501; /* 3-4. 피부과 문제풀이 -> 이중 for 돌지 않아야 함 ㅠ * */ import java.util.ArrayList; class Person { int inTime; int outTime; Person(int inTime, int outTime){ this.inTime = inTime; this.outTime =outTime; } } class Solution1 { //시간 HH:MM -> M분으로 변경 public int ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 5. 1.
섹션3. 자료구조 활용 섹션 - (1)
🎈섹션3. 자료구조 활용 섹션 - (1) 🟦 3-1. 최대 길이 연속 수열 문제 풀이 코드 | 오류 났다. 최초 시도 때 나는 arr[i+1]-arr[i] == 1 즉, 1씩 차이나는 값일 때만 카운팅++하고, 나머지는 continue로 지속한 뒤, Math.max()로 더 큰 cnt 값이 나타날 때 answer에 세팅해주면 되는 문제라고 생각했는데, 계속해서 오류가 났다. package to_0428; /* 3-1. 최대 길이 연속수열 * */ import java.util.*; class Solution1 { public int solution(int[] nums){ int answer = 0; int cnt = 0; //1) 정렬 해놓고 Arrays.sort(nums); for(int i=0; i
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 4. 28.
섹션2. 해싱 & 시간 파싱 알고리즘 - (4)
🎈섹션2. 해싱 & 시간 파싱 알고리즘 - (4) 🟦 2-6. 문서 도난 ⬛ 문자열 (알파벳 순으로 ) 비교하는 compareTo() 사용법 A.compareTo(B) 1) A 가 B보다 앞순이면 음수 출력 2) A 가 B보다 뒷순이면 양수 출력 3) A== B순이면 0 출력 ⬛ 시간 파싱 HH:MM → 분 단위로 변환하여 비교할 것 getTime(String HH:MM) 함수 만들어서 들어온 입력을 → 분 단위로 변환시킴 HH:MM 단위로 들어온 String은 split(”:”) 기준으로 잘라서 앞은 HH, 뒤는 MM //시간 -> 분 단위 변형 함수 public int getTime(String time) { int H = Integer.parseInt(time.split(":")[0]); int M..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 4. 27.
섹션2. 해싱 & 시간 파싱 알고리즘 - (3)
🎈섹션2. 해싱 & 시간 파싱 알고리즘 - (3) 🟦 2-4. 음수가 있는 부분수열 최초 내 시도 | ⇒ 이중 for()문으로 답은 나왔다. | O(n2) 여서 비효율 나는 이중 for문 돌면서 특정 i로 찍은 현재 값에서 j로 0~i-1까지 차례로 돌며 구간합 == m 일때마다 answer++처리 했다. 다만, 만약 m값이 nums 값 그 자체일 경우도 고려해야 한다고 생각 package to_0426; /* 2-4. 음수가 있는 부분수열 문제 풀이 * */ import java.util.*; class Solution1 { //솔루션 함수 public int solution(int[] nums, int m){ int answer = 0; int[] az = new int[nums.length]; fo..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 4. 26.
섹션2. 해싱 & 시간 파싱 알고리즘 - (2)
🎈섹션2. 해싱 & 시간 파싱 알고리즘 - (2) 🟦 2-3. 서로 다른 빈도수 만들기 문제 풀이 이 문제는 유일한(Unique) 빈도수를 구하는 게 관건이다. 새로운 HashSet 를 만들어서 HashMap에 각 문자별 빈도수만 뽑아서 중복 검사 후 담아야 한다. 1) 각각의 Map에 담긴 전체 key 순회하면서 2) 각 key의 빈도수값이 Set에 중복되는 동안 계속 while() 문 돌며 Map에 다시 해당 key에 대한 value를 -1 처리, answer++ (중복 동안) 3) while 빠져나와서 만약 map의 해당 key 값이 0인 경우 continue 4) 확인용 Set에 최종 add처리한다. 코드 package to_0424; import java.util.HashMap; import j..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 4. 24.
섹션2. 해싱 & 시간 파싱 알고리즘 - (1)
🎈섹션2. 해싱 & 시간 파싱 알고리즘 - (1) 🟦 2-1. 한 번 사용한 최초 문자 코드 HashMap 저장해야 한다. map.getOrDefault() 사용해서 문자가 중복없이 카운팅 되도록 해야 함 다시 i로 전체 길이 순회하면서 i번째 문자(key) 기준으로 get 한 value가 1인 경우 해당 i+1을 곧장 리턴해주어야 한다. // 2-1. 한 번 사용한 문자 import java.util.*; class Solution1 { //솔루션 함수 public int solution(String s){ //각 문자, 빈도수 HashMap map = new HashMap(); //각 문자별 빈도수 카운팅 for(char x : s.toCharArray()) { //맵에 담되, 중복 없이 담음 map..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 4. 20.
섹션1. 시뮬레이션 & 구현 - (3) | 과일 가져가기 문제 풀이
🎈섹션1. 시뮬레이션 & 구현 - (3) | 과일 가져가기 문제 풀이 🟦 1-6. 과일 가져가기 문제 문제 분석 (풀이) 문제 조건 1. 서로 이득이 될 때만 교환이 가능 문제 조건 2. 교환 가능 여러명 이면 번호 작은 학생과 교환 ⇒ 서로 교환 시 이득이 나는 조건 1) 각 학생에게 최솟값이 유일해야 한다. 2) 서로 교환하려는 최솟값 과일이 달라야 한다. (= 과일 idx 번호 달라야 한다.) 3) 교환 이후, 1개 증가한 과일 개수가 여전히 그대로 최솟값인 과일이어야 한다. (= 증가한 과일 ≥ 감소한 과일) 내 시도 나는 Fruit (사과, 배, 귤) 객체를 새로 생성해서, ArrayList 에 담아 → 각 학생의 최솟값을 체크해놓고, 최솟값 과일이 다를 경우 교환이 되도록 할 생각이었다. → ..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 4. 19.
섹션1. 시뮬레이션 & 구현 - (2)
🎈섹션1. 시뮬레이션 & 구현 - (2) 🟦 1-3. 잃어버린 강아지 | 현수, 강아지 동시 이동 문제 현수는 농사지을 땅을 찾아 강아지를 데리고 산으로 들로 땅을 찾아 다니고 있었다. 숲속에서 낮잠을 자던 현수는 강아지가 도망가버려 강아지를 잃게 되었다. 강아지가 어디로 갔는지 모르는 현수는 강아지를 찾아 나섰다. 다행히 강아지에게 위치 추적기가 달려 있어 핸드폰 실시간 위성지도로 현수의 위치와 강아지의 위치, 그리고 근처의 지도를 현수는 알 수 있습니다. 지도의 크기는 항상 10_10이며, 각각의 칸에는 각각 나무, 빈칸, 강아지, 그리고 현수가 있을 수 있습니다. 지도는 다음과 같이 주어진다. 0 - 빈칸, 1 - 나무, 2 - 현수, 3 - 강아지 강아지와 현수는 항상 고정된 방법으로 지도를 다닌..
- 알고리즘 이론 [개념]/[개념] 코테 알고리즘 공부 - 시즌 2
- · 2023. 4. 14.