2. 구간합 구간 합은 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘. 코딩 테스트에서 사용 빈도 높음! 구간 합의 핵심 이론 합 배열 S 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열. 합 배열을 미리 구해두면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소! A[i]부터 A[j]까지의 배열 합을 합 배열 없이 구하는 경우, 최악의 경우는 i가 0이고 j가 N인 경우로 시간 복잡도는 O(N)이다. 합 배열을 사용한다면 O(1) 안에 답을 구할 수 있다. 합 배열 S를 만드는 공식 S[i] = S[i - 1] + A[i] ..
1. 배열과 리스트 배열과 리스트의 핵심 이론 배열 배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 배열의 값은 인덱스를 통해 참조 가능하고 선언한 자료형의 값만 저장 가능 ex) 아래 배열을 배열 A라 하고, 값 4에 접근하고자 하면 → A[3] 배열의 특징 인덱스를 사용하여 값에 바로 접근 가능 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움. -> 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정 필요 배열의 크기는 선언할 때 지정 가능, 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 구조가 간단 → 코딩 테스트에서 많이 사용 리스트 리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 리스트의 특징 인덱스가 없다 → 값에 접근하..
알고리즘을 공부하면서 많은 정렬들이 등장한다. 버블 정렬, 삽입 정렬 등등... 오늘 공부한 내용은 이렇게 수많은 정렬 알고리즘 중 시간 복잡도가 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. 오늘의 고민 오늘은 알고리즘 공부 방향에 대한 생각에 많은 시간을 투자하였다. 인터넷을 찾다가 본 누군가의 말로 알고리즘을 파이썬으로 시작하였고, 공부는 성향상 백엔드가 적성에 맞아 자바, 스프링을 배워 백엔드 개발자가 되고자 한다. 그래서 최근에는 알고리즘 공부를 파이썬과 자바 두가지 언어로 모두 시행하고 있었는데, 시간적 여유가 없는 현 상황에 선택을 해야한다는 판단을 내렸다. 그래서 여러번 서칭하고 고민하다가, 당장 파이썬으로 풀 때보다 번거롭고 힘들더라도 내가 주력언어로 삼고 싶고 공부하고 있는 자바로 해야겠다는 결론을 내릴 수 있었다. 많은 사람들이 말하길, 언어는 수단이라고 한다. 한가지 언어를 깊게 공부하고 습득하면 다른 언어는 배우기가 쉬운 구조라고 한다. 나는 아직 자바, 파이썬 무..
