sh1mj1_log

알고리즘에서의 정렬은 크게 아래와 같습니다. 버블(bubble) 정렬: 데이터의 인접 요소끼리 비교하고 swap 연산을 수행하며 정렬 선택(selection) 정렬: 대상에서 가장 크거나 작은 데이터를 찾아가 반복하면서 정렬 삽입(insertion)정렬: 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬 퀵(quick) 정렬: pivot 값을 선정해 해당 값을 기준으로 정렬 병합(merge) 정렬: 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬 기수(radix) 정렬: 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬 이 중에서 버블 정렬을 알아보고 문제를 풀어봅시다. 버블 정렬 버블 정렬(bubble sort) 는 두 인접한 데이터의 크기를 비교해 정렬합니다. 매..

자바 코딩테스트 공부 중 백준 11286 절댓값 힙 문제를 푸는 중에 Priority Queue 을 사용하는 방법에 대해 간단하게 정리해보려고 합니다. 이 포스팅에서는 매우 간단한 사용 방법을 설명합니다. 추가로 PriorityQueue 의 인자로 comparator 을 가질 수 있는데 이 부분은 오른쪽 링크 https://sh1mj1-log.tistory.com/122 포스팅하단에서 확인할 수 있습니다. Priority Queue(우선순위 큐)? Priority Queue 는 Queue 와 구조가 비슷합니다. Queue 는 FIFO(First In First Out) 구조로 먼저 들어온 순서대로 데이터가 나가는 것인 반면에 Priority Queue 는 데이터의 우선순위를 정해 우선순위가 높은 순서대로..

바로 문제를 풀어봅시다. 백준 2164번 - 카드2 2164번: 카드2 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 분석하기 큐를 잘 이해하고 있는지를 묻는 문제입니다. 가장 위의 카드를 가장 아래에 있는 카드 밑으로 옮기는 동작은 큐의 선입선출이 떠오릅니다! 카드의 개수의 최대가 500,000 이므로 시간 복잡도의 제약도 크지 않습니다. 큐로 이 문제를 해결해봅시다. 손으로 풀어보기 poll 을 수행하여 맨 앞의 카드를 버립니다. 이어서 바로 add 을 수행해서 맨 앞에 있는 카드를 가장 아래로 옮..

Stack 스택은 삽입과 삭제가 LIFO(Last-in First-out = 후입선출) 로 이루어지는 자료구조입니다. LIFO 는 삽입과 삭제가 한쪽에서 만 일어나는 특징이 있습니다. top: 삽입과 삭제가 일어나는 위치 push: top 위치에 새로운 데이터를 삽입하는 연산 pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산. Stack 은 DFS(Depth First Search = 깊이 우선 탐색), 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아두어야 합니다. LIFO 는 개념 자체가 재귀함수 알고리즘 원리와 일맥상통하기 때문입니다. Queue 큐는 삽입과 삭제 연산이 FIFO(First-in First-out ..

'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다 슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위(window) 을 유지한 채로 이동(sliding) 하면서 문제를 해결한다. 위 문장만 읽어봐도 투 포인터 알고리즘과 매우 비슷하다는 것을 알 수 있을 겁니다! 원리도 간단하므로 바로 백준 문제 2개를 풀어보면서 윈도우 알고리즘의 개념과 원리를 공부해 봅시다! 백준 12891 번 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문..

'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다 투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화 시키는 알고리즘이다. 알고리즘이 매우 간단하여 문제를 풀면서 이해를 해봅시다. 백준 2018 번 https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 1. 문제분석 먼저 시간 복잡도 분석으로 사용할 알고리즘의 범위부터 줄여야 한다. 주어진 N 의 최대값은 10,000,000 이다. 만약 이 ..

'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다 구간 합 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 것이다. 코딩 테스트에서 자주 사용되므로 잘 알아둡시다. 먼저 합 배열이 무엇인지 정의합시다. 만약 배열 A 가 있을 때 합 배열 S는 아래와 같다. S[i] = A[0] + A[1] + A{2] + … A[i-1] + A[i] 즉, S[i] 는 A[0] 부터 A[i] 까지의 합이다. 합 배열은 기존 배열을 전처리한 배열이라고 할 수 있다. 만약 이렇게 합 배열을 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) 에서 O(1) 으로 줄어든다. 예를 들어서 A[i] ~ A[j] 까지의 배열 합을 구해야 한다고 합시다. 합 배열 ..

'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다. 배열과 리스트 배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 배열의 특징 Index 을 사용하여 값에 바로 접근할 수 있다. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입/삭제 하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다. 배열의 크기는 선언할 때까지 지정할 수 없으며 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 구조가 간단하여 코딩 테스트에서 많이 사용한다. 리스트 값과 포인터를 묶은 ‘노드’를 포인터로 연결한 자료구조 리스트의 특징 인덱스가 없어서 값에 접근하려면 Head Pointer 에서부터 순서대로 접근해야 한다. 포인터로 연결되어 있으므로 데이터 ..