OON

LinkedList 란? linkedList 란 연결 리스트로 각 노드가 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다. 이는 인덱스에 의한 물리적 배치를 하지 않고 포인터에 의해 다음 노드를 연결합니다. 연결 리스트의 구조에서 맨 앞을 Head 맨 마지막을 Tail 이라 합니다. 노드 : 데이터와 포인터로 구성된 객체 시간 복잡도 접근 (Access) : O(n) 특정 인덱스에 접근할 때 배열과 달리 Linked List 는 순차적으로 접근해야 하므로 해당 인덱스까지 탐색이 필요합니다. 탐색 (Find) : O(n) 접근과 마찬가지로 순차적으로 접근해야합니다. 삽입/삭제 여러 블로그의 내용을 보면서 삽입/삭제 시 시간 복잡도는 O(1) 라고 생각하면서 링크드리스트를 학습하고 있었습니다..

가장 간단한 정렬 알고리즘 중 버블정렬에 대해 알아보도록 하자 데이터의 인접 요소끼리 비교하고, 스왑 연산을 수행하며 정렬하는 방식 최상의 경우 : O(n) 최악의 경우 : O(n^2) Bubble Sort 데이터가 이미 정렬되어 있는 경우에는 한번의 순회로 정렬이 가능하나, 그렇지 않다면 각 자리를 찾기 위해 n번 동안 n번 값을 찾아야한다. function bubbleSort(arr) { for (let i = 0; i arr[j]) { swap = arr[i]; arr[i] = arr[j]; arr[j] = swap; } } } return arr..

퀵 정렬이란 기준 값을 선정하여 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘 입니다. 기준값에 따라 시간 복잡도가 평균 O(nlogn)에서 최악의 경우에는 O(n ² ) 퀵 정렬 과정 데이터 분할을 하는 pivot데이터를 설정 pivot을 기준으로 아래 2.1 ~ 2.5 과정을 거쳐 데이터를 2개의 집합을 분리 start 가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동 end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동 start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end 가 가리키는 데이터보다 작으면 start, end가 가리키는 데이터를 swap 하고 sta..

1541번: 잃어버린 괄호 (acmicpc.net) 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연..

11047번: 동전 0 (acmicpc.net) 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가..

그리디 알고리즘 이란? 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 즉, 매 순간 마다 최선의 선택을 통해 최고의 결과를 도출해내는 알고리즘이다. 그러나 매 순간 최선의 선택이 최고의 결과를 도출해 내는 것은 아니기 때문에 그리디 알고리즘을 사용하여 코딩 테스트를 응시할때는 그리디 알고리즘을 사용해도 되는 문제인지 판별할 수 있어야 한다. 핵심 이론 1. 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 2. 선택한 해가 전체 문제의 제약조건에서 벗어나지 않는지 검사한다. 3. 현재까지 선택한 해 집합이 문제를 해결할 수 있는지 검사 후 해결하지 못한다면 1부터 반복한다. 출처: [지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강..