전체 글
[용어 사전] 컴파일 언어 vs 인터프리터 언어
[ 1 ] 컴파일 언어 만약, C언어로 코딩을 입문했다면 관련 서적에서 '컴파일'이라는 단어를 쉽게 찾아볼 수 있었을 것이다. '컴파일'이란 쉽게 말하자면 개발자가 작성한 소스 코드를 컴퓨터가 이해할 수 있도록 번역하는 과정이다. 컴파일 언어는 개발자가 작성한 소스 코드를 컴파일러를 통해 기계어로 변환한 후 하나의 실행파일을 생성한다. 소스 코드가 방대한 경우 컴파일하는데 상당히 오랜 시간이 걸릴 수 있다는 단점이 있지만, 컴파일 후 생성된 실행파일은 기계어로 작성되어 있기 때문에 런타임이 빠르다는 장점이 있다. 대표적인 컴파일 언어로는 C, C++ 등이 있다. - 실제 C++ 컴파일 과정 (1) 헤더파일 등의 전처리기 매크로들을 처리하는 전처리(Preprocessing) 단계 (2) 소스 파일을 어셈블..
[자료구조/C++] 맵(map)
[ 1 ] 기본내용 map은 기본적으로 entry라고 불리는 (key, value)쌍이 저장되는 자료구조이다. 하나의 map은 중복된 key값을 가질 수 없다는 특성과 key값으로 해당 key값과 mapping된 value를 쉽게 검색할 수 있는 특성으로 인해 정보 저장 및 검색에 유리한 자료구조이다. 대표적인 map의 특성은 다음과 같다. - map은 중복된 key값을 가질 수 없기 때문에 하나의 key가 여러 개의 value값을 가질 수 없다. - map의 주요 연산으로는 search, insert, erase가 있다. - map을 연결리스트로 구현할 경우 위의 주요 연산의 시간복잡도는 O(n)이다. - map 연산의 시간복잡도를 줄이기 위해 hash map 등을 활용하기도 한다. [ 2 ] C++에..
[C/C++] 백준 2263번
문제출처: https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net [ 문제 ] n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. [ 입력 ] 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. [ 출력 ] 첫째 줄에 프리오더를 출..
[자료구조/C++] 이진탐색트리 (Binary Search Tree)
[ 1 ] 트리란? 트리는 대표적인 비선형 자료구조이며 노드와 노드를 연결하는 에지를 통해 계층을 구성한다. 이때 트리의 중심이 되는 노드를 root라고 하며, 이 노드는 일반적으로 맨 위에 나타난다. 즉, 트리 구조를 그림으로 나타낼 때는 실제 나무와는 반대로 뿌리가 맨 위에 나타나게 되는 것이다. 트리를 통해 우리는 선형 자료구조로는 표현할 수 없는 계층적 문제를 표현할 수 있다. [ 2 ] 이진탐색트리 (Binary Search Tree) [ 2 - 1 ] 이진트리 이러한 트리 중에서도 각 노드가 최대 2개의 자식 노드만 가질 수 있는 '이진 트리'가 자주 활용되는데, 이진 트리에도 Complete Binary Tree, Full Binary Tree, Binary Search Tree, AVL T..
[C/C++] 백준 1655번
문제출처: https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net [ 문제 ] 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면,..
[자료구조/C++] 우선순위 큐
[ 1 ] 기본내용 우선순위 큐(Priority Queue)란 First-In First-Out(FIFO) 구조를 따르는 일반적인 큐와 달리 힙(heap)을 활용하여 원소들의 우선순위를 설정하고, 우선순위에 따라 가장 작은(또는 가장 큰) 원소에 빠르게 접근할 수 있는 자료구조이다. 단, 최대 or 최소 둘 중 하나에 대해서만 우선순위를 적용할 수 있으며 최댓값을 우선순위로 둘 경우 최대 힙(Max heap), 최솟값을 우선순위로 둘 경우 최소 힙(Min heap)이라 한다. [ 2 ] C++에서의 우선순위 큐 [ 2 -1 ] 헤더파일 C++에서는 container adaptor로서 priority_queue를 제공하고 있으며, vector를 기본 컨테이너로 사용한다. priority_queue를 사용하..
[C/C++] 백준 5430번
문제출처: https://www.acmicpc.net/problem/5430 [ 문제 ] 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오. [ 입력..