Table of Contents 개요 기본 구조 반환 삽입 삭제 코드 문제 C++ STL stack 1. 개요 스택은 선형 자료구조 중 하나로서 추상화에 큰 도움을 주는 자료구조입니다. 요약하면 선형 구조의 양 끝 중에서 한쪽에서만 자료를 삽입하고 삭제할 수 있는 자료구조를 뜻합니다. 이 요약의 의미는 이후의 '기본 구조'란에서 자세히 설명하겠습니다. 스택은 간단한 선형 자료구조인 만큼, 배열만을 활용해도 간단히 구현할 수 있습니다. 굳이 스택이라는 새로운 이름을 붙여야 하나 싶을 정도로 간단하지요. 게다가 배열보다 자유도도 낮기 때문에 오히려 할 수 있는 일은 더 줄어들게 됩니다. 하지만 스택은 선형 자료구조를 공부할 때 빼놓지 않고 등장하는 주제로서, 꽤 중요한 자료구조 취급을 받습니다. 이는 스택의..
Table of Contents 개요효율성추상화재사용분류 1. 개요 자료구조란 자료를 저장하는 방법을 뜻합니다. 프로그램 대다수가 자료를 저장하고 사용하기 때문에, 자료구조는 프로그래밍에서 빼놓을 수 없는 요소로 분류되며, 프로그래밍 언어를 익힌 후에 학습해야 할 필수 과목 리스트에 항상 올라와 있습니다. 그런데 사실, 자료구조를 배우고자 하는 분이시라면 이미 자료구조를 사용하고 계실 가능성이 높습니다. C언어, 자바, 파이썬과 같은 언어를 배울 때 사용하는 변수, 배열, 구조체도 자료구조의 일종이기 때문이지요. 여러분들은 언어를 배우실 때 이들을 이용해 자료들을 잘 저장하고 사용해 오셨을 겁니다. 어쩌면 변수와 배열을 이용해 자료를 저장하고 처리할 자신이 있는데, 굳이 자료구조를 배워야 하나 생각하실 ..
Table of Contents 개요시간복잡도의 예시 : O(1), O(n), O(n^2)O 표기법실제 실행 시간 1. 개요 깔끔하고 이해하기 쉬운 코드, 유지 보수하기 좋은 프로그램 구조 등등 좋은 프로그램의 조건에는 여러 가지가 있습니다. 하지만 이런 요소들은 프로그램을 개발하는 사람들의 기준이고, 프로그램을 사용하는 사람 입장에서 중요한 건 아닙니다. 그렇다면 사용자의 입장에서 중요한 건 무엇일까요? 여기에도 다양한 답들이 존재할 수 있지만, 중 저희가 주목해야 할 요소로 프로그램의 실행 시간을 뽑을 수 있습니다. 예를 들어 검색에 3초가 걸리는 사이트와 0.1초가 걸리는 사이트가 있다고 했을 때, 사용자가 느끼는 답답함은 천지 차이일 것입니다. 따라서 프로그램을 만들 때도 실행 시간을 줄이기 위해..
Table of Contents printf이스케이프 시퀀스문제 1. printf C언어로 프로그램을 만들 때, 가장 많이 하게 되는 작업 중 하나가 사용하고 싶은 기능을 가진 함수를 만드는 것입니다. 그러나 사용할 함수를 모두 스스로 코딩할 필요는 없습니다. 미리 만들어져 있는 함수를 가져다 씀으로써 효율적인 프로그래밍이 가능하기 때문입니다. 이 글에서는 그러한 함수 중, printf 를 소개합니다. printf 는 에 있는C언어의 대표적인 출력 함수로서, printf("출력할 내용"); 이런 식으로 큰따옴표 안에 원하는 내용을 적기만 하면 되는 편리한 함수입니다. 아래와 같은 프로그램을 실행해보면 큰따옴표 안의 내용이 출력되는 걸 확인할 수 있습니다. 123456789//code by RiKang, ..
Table of Contents 개요 트리 펼치기 Mo's algorithm 의 적용 문제 1. 개요 https://www.acmicpc.net/problem/13518 위 문제와 같이 트리에서의 쿼리를 처리할 때, 쿼리의 처리 순서를 마음대로 조작할 수 있다면, DFS로 트리 펼치기 + Mo's algorithm 의 조합으로 시간 복잡도 O( (N+Q) * sqrt N * f(x) ) 을 맞춰 줄 수 있는 경우들이 있습니다. ( * f(x) = 모스 알고리즘에서 노드의 추가 / 삭제 시 필요한 시간복잡도 ) 2. 트리 펼치기 트리에서 DFS를 돌면서, 각각의 DFS 함수가 '시작 했을 때', 그리고 '끝날 때' 해당하는 노드를 배열에 추가해서 트리를 펼치는 스킬입니다. 아래 예시를 통해 알아보겠습니다...