4. 슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결한다. 투 포인터 알고리즘과 매우 비슷하다. [❌][백준 12891] DNA 비밀번호 12891번: DNA 비밀번호 1단계 - 문제 분석하기 P와 S의 길이가 1,000,000으로 매우 큼 → O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 함. 부분 문자열의 길이가 P → 슬라이딩 윈도우의 개념을 이용하면 문제를 쉽게 해결 가능 길이가 P인 윈도우를 지정하여 배열 S의 시작점에 놓는다. 윈도우를 오른쪽으로 밀면서 윈도우에 잡힌 값들이 조건에 맞는지 탐색 배열 S의 길이만큼만 탐색을 진행하면 되므로 O(n)의 시간 복잡도로 문제 해결 가능 2단계 -..
알고리즘을 공부하면서 많은 정렬들이 등장한다. 버블 정렬, 삽입 정렬 등등... 오늘 공부한 내용은 이렇게 수많은 정렬 알고리즘 중 시간 복잡도가 O(n)으로 엄청난 성능을 보여주는 알고리즘이다. 카운팅 정렬을 공부하면서 처음에는 이게 왜 빠를까?를 생각했다. 시간 복잡도를 공부할 때, 시간 복잡도 도출 기준은 상수의 시간 복잡도는 계산에서 제외하고, 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다고 배웠다. 카운팅 정렬은 각 배열 원소끼리(예를 들어 for문 중첩) 직접 비교하지 않고, 인덱스를 가지고 위치를 찾아나가는 것이다. 이 방법의 가장 큰 장점은 매우 빠르다는 것이다. 하지만 카운팅 정렬은 수의 범위가 매우 클 경우(예를 들어 10억, 100억 등등...) 심한 메모리 낭비를..
1. 디버깅은 왜 중요할까? 1) 디버깅의 중요성 코딩 테스트에서 떨어졌을 때의 유형 학생1) index 범위 1개 차이로 떨어졌어!! 학생2) 계속 답이 나오지 않아 몇 시간 동안 헤맸는데, 알고보니 int를 long으로만 바꾸면 되는거였어!! → 디버깅을 제대로 했다면 아마 코딩 테스트에 통과했을 것! 디버깅은 코딩 테스트에 필요한 기술이고, 그냥 알아두기만 하면 되는 것이 아니라 문제를 풀면서 반드시 해야 하는 과정이다. 반드시 디버깅을 익힌 후에 코딩 테스트에 응시하라! 2) 디버깅하는 법 방법 코드에서 디버깅하고자 하는 줄에 중단점(break point)을 설정하고, IDE의 디버깅 기능을 실행해 진행하면 된다. 구체적인 방법은 다음과 같다. 코드에서 디버깅하고자 하는 줄에 중단점을 설정. 이때..
1-1 시간복잡도 표기법 알아보기 알고리즘에서 시간복잡도: 주어진 문제를 해결하기 위한 연산 횟수 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주 예제) 시간제한 2초 → 2억 연산 안에 답이 나와야 함. 1) 시간 복잡도 유형 빅-오메가(Ω(n)): 최선일 때(best case)의 연산 횟수를 나타낸 표기법 빅-세타(θ(n)): 보통일 때(average case)의 연산 횟수를 나타낸 표기법 빅-오(Ο(n)): 최악일 때(worse case)의 연산 횟수를 나타낸 표기법 public class timeComplexityExample1 { public static void main(String[] args) { // 1 ~ 100 사이의 값 랜덤 선택 int findNumber = (int..
1. 오늘의 고민 오늘은 알고리즘 공부 방향에 대한 생각에 많은 시간을 투자하였다. 인터넷을 찾다가 본 누군가의 말로 알고리즘을 파이썬으로 시작하였고, 공부는 성향상 백엔드가 적성에 맞아 자바, 스프링을 배워 백엔드 개발자가 되고자 한다. 그래서 최근에는 알고리즘 공부를 파이썬과 자바 두가지 언어로 모두 시행하고 있었는데, 시간적 여유가 없는 현 상황에 선택을 해야한다는 판단을 내렸다. 그래서 여러번 서칭하고 고민하다가, 당장 파이썬으로 풀 때보다 번거롭고 힘들더라도 내가 주력언어로 삼고 싶고 공부하고 있는 자바로 해야겠다는 결론을 내릴 수 있었다. 많은 사람들이 말하길, 언어는 수단이라고 한다. 한가지 언어를 깊게 공부하고 습득하면 다른 언어는 배우기가 쉬운 구조라고 한다. 나는 아직 자바, 파이썬 무..
알고리즘 문제를 풀다가, 자바의 random 함수에 익숙해져서 파이썬의 랜덤함수들이 헷갈려서 블로그에 정리하기로 했다. 파이썬(Python)에서의 랜덤함수 우선 랜덤함수를 사용하기 위해서는 import random을 하여야 한다. import를 하고 random.을 찍으면 사용할 수 있는 함수들이 나온다. 1. random.random(): 0.0 이상 1.0 미만의 무작위 실수(float)를 반환 [0.0, 1.0) 2. random.uniform(a, b): a 이상 b 이하의 무작위 실수(float) 반환 [a, b] 3. random.randint(a, b): a 이상 b 이하의 무작위 정수(int) 반환 [a, b] 4. randrange(start, stop, step): start 이상 st..
