[알고리즘] 선형 시간 선택 알고리즘
10개의 원소를 갖는 아래와 같은 배열이 있다. 이 배열에서 i번째의 값을 찾는다고 해보자. arr[10] = { 10, 2, 5, 7, 6, 4, 8, 1, 9, 3 } 우선 배열을 한 번씩은 다 훑어봐야 하므로 적어도 n에 비례하는 시간이, 즉 \(\Omega(n)\)이 될것이다. 정렬을 한다면 \(O(nlogn)\)일 것이다. 어떤 시간에서든 선형 시간에 가능하도록 보장해줄 수 있도록 하는 알고리즘이 없을까? 이를 가능하도록 하는 알고리즘이 바로 선형 시간 선택 알고리즘이다. 평균 선형 시간 선택 알고리즘 선택 알고리즘은 퀵 정렬에서 사용했던 분할 알고리즘을 사용한다. 위의 경우에서 분할 알고리즘을 사용한다면 i번째 값을 찾을 수 있다. 기준원소를 5로 하고, 3번째로 작은 원소를 찾는다고 해보자...
[프로그래머스/C++] 행렬 테두리 회전하기
미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요! 문제 제목 https://programmers.co.kr/learn/courses/30/lessons/77485# 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 문제 rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적..
[자료구조] 우선순위 큐와 힙
우선순위 큐(Priority Queue) 우선순위 큐의 큐는 먼저 들어온 데이터가 먼저 나가는, 그 큐가 맞다. 둘의 차이점이라면, 우선순위 큐는 우선순위가 높은 데이터가 먼저 출력되는 것이 차이다. 아래와 같은 배열이 있다고 하자. Array arr[10] = { 1, 3, 4, 9, 6, 2, 7, 8, 10, 5 }; Priority_Queue pq[10]; 이 배열을 우선순위 큐(pq)에 저장된다고 하자. 큰 수에 우선순위가 주어진다고 하면, pq에는 아래와 같이 저장된다. Priority_Queue pq[10] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; 입력은 1, 3, 4, ..., 10, 5 순으로 되었지만, 우선순위 큐에는 큰 수부터 나열되어있다. 즉, 높은 우선순위..
[자료구조] 트리
트리 트리는 스택, 큐 등의 선형적인 자료구조가 아니라, 계층적인 구조의 자료구조이다. 컴퓨터의 폴더 구조, 가계도, 회사의 조직도 등 계층적인 관계들을 표현한 자료구조이다. 이 외에도 인공지능에서 사용되는 결정 트리도 트리라고 할 수 있겠다. 트리는 위의 그림과 같이, 1개 이상의 노드로 이루어져 있다. 트리 용어 노드(Node) : 트리를 구성하는 요소들로 그림에서 A, B, C, D, E, F, G, H, I 를 말한다. 루트(Root) 노드 : 트리에서 가장 높은 곳에 있는 노드. 위 그림에서 A가 루트 노드이다. 서브 트리(Subtree) : 루트 노드에서 갈라져 나온 트리. 간선(Edge) : 루트와 서브트리 사이에 연결된 선. 부모 노드(Parent node) : 자식 노드와 직접 연결된 상..
[프로그래머스/C++] 영어 끝말잇기
미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요! 영어 끝말잇기 https://programmers.co.kr/learn/courses/30/lessons/12981 코딩테스트 연습 - 영어 끝말잇기 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather"..