시간 측정 입력(input) 여러개의 데이터를 공백을 통해 입력받기 여러개의 데이터를 공백을 통해 입력받기(속도개선) 최대/최소 구하기 최대값, 최소값 구하기 최대값, 최소값 인덱스 구하기 타입 변환 아스키 타입 변환 리스트 리스트 컴프리헨션(List Comprehension) - 2차원 리스트 초기화 정렬 - 리스트 및 딕셔너리 자료형 등 정렬 Deque(데크) Deque를 스택, 큐에 사용하기
그리디 알고리즘(Greedy Algorithm) 당장 좋은 것만 선택하는 방법을 그리디(탐욕법) 알고리즘이라고 하며 단순하지만 강력한 문제 해결 방법이다. 그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만을 고르는 방법'을 의미한다. 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 이는 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있다.(정렬, 최단 경로 등의 알고리즘 유형의 경우 미리 알고리즘 사용 방법을 숙지하고 있어야 해결 가능한 경우가 많다.) 그리디 알고리즘 자체가 문제 출제 폭이 매우 넓기 때문에 최단 경로 알고리즘에 속하는 다익스트라 알고리즘은 엄밀히 말하면 그리디 알고리즘이므로 그리디 알고리즘이면서도 '암기'가 필요한 알고리즘도 있을 수 있..
최근 학교 수업과 여러 프로젝트에 쫓기다 보니 포스팅을 많이 소홀히 했었다. 중요하다는 것을 알면서도 헤이해지는 자신을 다잡기 위해 다시 조금씩이라도 시작해보려고 한다. 실제 코딩 테스트에는 제출횟수에 제한이 있다. 오프라인 테스트의 경우 푼 다음에 어떤 식으로 풀었고 어떤 알고리즘을 사용했는지 화이트보드에 설명해야하는 경우도 있다. 삼성전자는 BFS/DFS를 활용하는 탐색과 시뮬레이션 문제 유형을 자주 출제한다. 알고리즘 대회를 준비한다면 다른 언어에 비해 빠른 C++이 좋다. 파이썬은 기본 자료형이 제공하는 기능이 매우 강력해 표준 라이브러리나 추가 외부 라이브러리를 적게 사용하는 편이다. 추천 온라인 IDE : 리플릿(Repl.it), 파이썬 튜터, 온라인 GDB 복잡도는 알고리즘의 성능을 나타내는..
당연히 기초적인 내용이라 다 알고있을거라고 생각할 수도 있지만 취업하는 중에 생각보다 기초적인 부분에서 발목을 잡힐 수도 있다고 생각하기에 이미 알고 있는 개념이라도 한번쯤 정리하고 넘어가는게 좋을 것 같다는 생각에 포스팅을 작성한다. 컴퓨터 시스템 우선 컴퓨터 시스템은 크게 하드웨어와 소프트웨어로 나뉜다. 소프트웨어는 운영체제(Windows, Linux, Mac OS)와 응용 프로그램(운영체제 위에서 돌아가는 여러 가지 프로그램)으로 구분이 된다. 하드웨어는 CPU(중앙처리장치(필수)), Memory, Storage(SSD/HDD)(외부저장매체), Network(인터넷) 등이 필요하다. 이게 4대 하드웨어 정도로 보면 될 것 같다. 폰노이만 구조 폰노이만 구조 이전에는 컴퓨터가 어떤 작업을 하려면 각 ..
트라이(Trie) 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조이다. Prefix Tree, Retrieval Tree, Digital Search Tree 라고도 부른다. 정렬된 트리구조다. 문자열같은 것들을 트라이에 구축을 해둬야하기 때문에 문자열 저장을 위한 메모리가 (많이)필요하지만 탐색이 빠르다. 길이가 N개인 문자열 탐색의 시간복잡도는 O(N)이다. 대신 사전에 이런 문자열들을 이 트라이 형태로 구축을 해야하는데 구축할 때 드는 생성시 시간복잡도는 트라이에 넣으려는 문자열의 개수가 M개라고 할 때 O(MN)이다. 하지만 한번 구축하면 탐색할 때 굉장히 빠르다는 장점이 있다. 동일 위치에서의 공통 부분들은 중복해서 들어가지는 않지만 다른 부분에 대해서는 트라이를 적용시켜줘야 하기 ..
선형 큐에 대한 설명과 힙(보통 우선순위 큐를 구현할 때 사용되는 자료구조)에 대한 설명은 아래 링크에 있다. 더보기 [자료구조] 큐 / 원형 큐 / 양방향 큐 [비선형 자료구조] 힙(Heap) 우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. ( 일반적인 큐는 선입선출(FIFO)인 선형 자료구조이다. ) 일반적으로 힙(Heap)을 이용하여 구현한다. (힙으로 구현했을 때, 우선순위 큐의 Enqueue, Dequeue는 최소(or 최대) 힙의 삽입, 삭제와 같다.) Dequeue시, 우선순위가 높은 순서대로 나간다. 우선순위가 같은 경우에는 FIFO가 적용된다. 우선순위 큐의 구현..
힙에 들어가기에 앞서, 이진 트리에 대해서는 알아두는 편이 좋다. 이진 트리 포스팅 더보기 트리(1) - 이진 트리(Binary Tree) 힙(Heap) 힙은 우선순위 큐를 구현하는데 자주 사용되는 자료구조이다. ( 우선순위 큐 링크 ) 완전 이진 트리(Complete Binary Tree) 형태이다.(왼쪽부터 차곡히 다 쌓인 트리) BST(이진 탐색 트리)와 달리 중복 값을 허용한다. 반 정렬 상태(느슨한 정렬 상태)를 유지한다. 반 정렬 상태가 무슨 뜻이냐면 최소 힙(Min Heap)에서는 루트 노드(최상단 노드)가 가장 최소값이고, 최소 힙 기준으로 부모 노드의 값은 자식 노드보다 작다. 최대 힙(Max Heap)에서는 루트 노드(최상단 노드)가 가장 최대값이고, 최대 힙 기준으로 부모 노드의 값은..
그래프(Graph) 그래프는 트리의 상위 개념의 자료구조로, 정점과 간선으로 구성된다. 연결된 정점간의 관계를 표현할 수 있는 자료구조이다. 그래프의 용도는 지하철 노선도나 통신 네트워크같은데에서 쓰인다. 그래프에서 사용되는 용어 정점(Vertex) : 그래프 구조의 자료 값을 담고 있는 단위(노드) 간선(Edge) : 노드 간의 연결선(link, branch) 인접 정점(Adjacent vertex) : 간선 하나를 두고 바로 연결된 정점 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수의 2배 진입 차수(In-degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(Out-degree) : 방향 그래프..
저번 포스팅에선 AVL 트리에 대해 알아보았다. [비선형 자료구조] 트리 링크 더보기 트리(1) - 이진 트리(Binary Tree) 트리(2) - 이진탐색트리 트리(3) - AVL 트리 이번 포스팅에서는 AVL 트리와 같이 자기 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)의 종류중 하나인 Red-Black 트리에 대해 알아보자. 마찬가지로 O(logN)의 시간복잡도를 가진다. Red-Black Tree(RB tree) 여러개의 규칙으로 이루어진 트리로 다소 이해하기 어려운 면이 있다. AVL 트리보다 균형을 맞추는 방법이 직관적이지는 않다.자바의 TreeSet과 TreeMap은 Red-Black 트리를 베이스로 한 구현을 사용한다. RB 트리는 다음과 같은 조건을..
저번 포스팅에선 트리, 이진 트리에 대해 알아보았다. [비선형 자료구조] 트리 링크 더보기 트리(1) - 이진 트리(Binary Tree) 트리(2) - 이진탐색트리 트리(4) - Red-Black 트리 이전 포스팅에서 구현한 기본적인 이진 탐색 트리의 경우 삽입 순서에 따라 편향이 발생할 수 있다. 편향이 발생한 경우 탐색에 O(N)의 시간이 필요하므로 성능이 떨어지게 된다. 이번 포스팅에서는 BST의 종류중 조건에 맞춰 균형을 유지하도록 하는 AVL 트리에 대해 알아보자. 균형이진탐색트리(Balanced Binary Search Tree) 노드의 삭제나 삽입에 균형을 유지하도록 조건을 맞춰서 코드가 더 짜여진 트리로 AVL 트리, Red-Black 트리 등이 있다. 편향을 해결하여 탐색에 O(logN..
