728x90 책/Do it! 알고리즘 코딩 테스트 자바 편26 Day-5 버블 정렬 1. 버블 정렬 두 인접한 데이터의 크기를 비교해 정렬하는 방식이다. 구현이 쉽다. 시간 복잡도가 O(n²)으로 속도가 느리다. 반복문을 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다. 2. 버블 정렬 과정 비교 연산이 필요한 루프 범위를 설정 (0~6) 인접한 데이터 값 비교 swap 조건에 부합하면 swap 수행 루프 범위가 끝날 때까지 2, 3을 반복 정렬 영역 재설정 (0~5) 비교 대상이 없을 때까지 위 과정을 반복 만약 swap이 한 번도 발생하지 않았다면 정렬이 완료되었다는 뜻이므로 정렬을 중단해도 된다. 3. 예제 문제 [2750] 수 정렬하기 (JAVA) # 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤.. 2024. 3. 22. Day-4 스택과 큐 1. 스택 스택은 삽입과 삭제 연산이 후입선출(Last-In First-Out)으로 이뤄지는 자료구조이다. 스택은 삽입과 삭제가 한 쪽에서만 이뤄진다. top : 삽입과 삭제가 일어나는 위치(제일 최근 값을 가리킴) push : top 위치에 새 값을 삽입 pop : top 위치에 있는 값을 삭제 peek : top 위치에 있는 값을 확인 2. 큐 큐는 삽입과 삭제 연산이 선입선출(First-In First-Out)으로 이뤄지는 자료구조이다. 큐는 삽입과 삭제가 양방향에서 이뤄진다. rear : 큐에서 가장 끝의 값을 가리킴 front : 큐에서 가장 앞의 값을 가리킴 add : rear 위치에 새 값을 삽입 poll : front 위치에 있는 값을 삭제 peek : front 위치에 있는 값을 확인 3.. 2024. 3. 21. Day-3 슬라이딩 윈도우 1. 슬라이딩 윈도우 슬라이딩 윈도우는 투 포인터와 매우 비슷한 알고리즘이다. 2개의 포인터로 범위를 지정하고 범위를 유지한 채로 이동한다. 1 2 3 4 5 6 위와 같은 배열이 있고 범위가 2라고 가정해보자. 처음 위치는 1과 2이다. 1 2 3 4 5 6 다음 범위로 이동하면 위와 같다. 2. 예제 문제 2024. 3. 17. Day-3 투 포인터 1. 투 포인터 투 포인터는 2개의 포인터를 이용하는 알고리즘이다. 이를 이용하여 알고리즘의 시간 복잡도를 최적화 할 수 있다. 알고리즘은 매우 간단하지만 여러 문제에 자주 쓰인다. 2. 예제 문제 [2018] 수들의 합 5 (JAVA) # 문제 설명 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 spicyrisotto.tistory.com [1940] 주몽 (JAVA) # 문제 설명 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아.. 2024. 3. 17. Day-2 구간 합 1. 구간 합 이론 합 배열 S는 기존의 배열 A가 있을 때, 일정 범위의 합을 구해둔 배열이다. 미리 합 배열을 구해두면 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다. 합 배열이 없는 경우에는 배열 A를 순회해야 구할 수 있으므로 최악의 경우 0부터 n까지 돌게 된다. 따라서 이 경우 O(N)이 된다. 2. 구간 합 공식 합 배열을 만드는 공식 : S[i] = S[i-1] + A[i] 구간 합을 구하는 공식 : S[j] - S[i-1] (i에서 j까지의 합) 합 배열이 있는 경우에는 시간 복잡도가 O(1)이 된다. 이는 구간 합을 구할 때 특정 인덱스의 값을 참조해야 하는데 이 시간 복잡도가 O(1)이기 때문이다. 위 공식들을 이용하여 합 배열을 만들고 구간 합을 구하면 시간.. 2024. 3. 13. Day-2 배열과 리스트 1. 배열 데이터를 메모리 공간에 연속적으로 저장하는 자료구조이다. 인덱스로 값을 참조할 수 있다. 배열의 크기는 선언할 때 지정할 수 있고 한 번 선언하면 크기를 바꿀 수 없다. 값을 중간에 삽입하거나 삭제하기 어렵다. 2. 리스트 노드(값 + 포인터)를 포인터로 연결한 자료구조이다. Head 포인터부터 접근하여 값을 참조할 수 있다. 따라서 값에 접근하는 속도가 느리다. 리스트의 크기는 선언할 때 지정하지 않아도 되므로, 크기가 변하는 데이터를 다루기 적절하다. 값을 중간에 삽입하거나 삭제하기 쉽다. 포인터를 저장하기 위한 공간을 사용하므로 구조가 복잡하다. 3. 예제 문제 [11720] 숫자의 합 (JAVA) # 문제 설명 N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램.. 2024. 3. 13. Day-1 디버깅 1. 디버깅 방법 디버깅이란 시스템의 논리적인 오류나 비정상적 연산을 찾아내고 수정하는 과정을 의미한다. Intellij에서는 디버깅하려는 줄에 break point(중단점)을 설정하고 디버깅 모드로 실행하면 된다. 실행 버튼 오른쪽의 벌레 모양 버튼이 디버깅 모드이다. 디버깅 모드를 실행하면 아래와 같이 중단점에서 실행을 멈추게 되며 현재 변숫값을 알 수 있다. 표시한 버튼을 누르면 다음 중단점까지 실행한다. 2. 디버깅 활용 사례 실수하기 쉬운 4가지 오류가 있다. 변수 초기화 오류 반복문에서의 인덱스 범위 지정 오류 잘못된 변수 사용 오류 자료형 범위 오류 디버깅을 이용하여 위와 같은 오류들을 해결할 수 있다. 2024. 3. 11. Day-1 시간 복잡도 1. 시간 복잡도 표기 수행 시간은 1초에 1억 번의 연산을 하는 것으로 간주한다. 문제를 해결하기 위한 연산 횟수인 시간 복잡도는 3가지 유형으로 정의한다. 빅-오메가(Ω(n)) : best case 빅-세타(Θ(n)) : average case 빅-오(O(n)) : worst case 각각 최선, 보통, 최악일 때 연산 횟수를 나타낸다. 시간 복잡도는 n이 증가함에 따라 같이 증가한다. 증가 속도는 위 그림과 같다. 2. 시간 복잡도 활용하기 시간 복잡도로 코드의 로직을 개선할 수 있다. 시간 복잡도 계산에는 상수를 제외하고, 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다. public class Main { public static void main(String[] args) {.. 2024. 3. 11. 이전 1 2 3 다음 728x90
