본문 바로가기

전체148

05. 스택, 큐, 덱 - Deque 큐와 스택은 각각의 상황에 맞춰서 값을 넣고 뺄 수 있지만, 그 외의 경우는 그러지 못한다는 단점이 있습니다. 이런 문제를 해결하기 위해 스택과 큐의 특성을 합친 새로운 자료구조가 있습니다. 바로 덱입니다! 덱은 스택과 큐와 달리 맨 앞/뒤에서 삽입/삭제가 모두 가능하며, 배열과 달리 네 메소드의 시간복잡도가 모두 O(1)입니다. 예를 들어 연결리스트를 사용하여 덱을 구현하면 양쪽 끝에서 삽입 삭제하는데 걸리는 시간이 O(1)이 되기 때문에 이러한 시간복잡도를 갖는 덱이라는 자료구조를 만들어낼 수 있습니다. 중요한건, 스택과 큐 처럼 push/pop을 사용하기엔 앞과 뒤에서 모두 삽입과 삭제를 진행하기 때문에, 사용하는 연산의 이름을 다르게 해야한다는 점 입니다. 이 이름은 .. 2023. 8. 18.
** [C++] 입문 [cin, cout 입출력문 사용] C언어에서는 에 있는 scanf, printf를 통해서 입출력문을 사용합니다. 물론 C++에서도 scanf, printf를 통해서 입력, 출력을 할수도 있지만 C++의 표준 입력 및 출력은 cin, cout를 사용합니다. std 네임스페이스에 속한 cin, cout객체는 클래스내에 있는 인스턴스입니다. 출력문 std::cout - C++의 출력문 cout은 위와 같이 사용하시면 됩니다. 대부분의 언어는 괄호() 안에 출력할 대상을 넣는데 반해 C++에서는 2023. 8. 18.
05. 스택, 큐, 덱 - 큐 02. 큐의 정의와 활용 유명 맛집에 갔다고 가정해봅시다. 대기줄이 너무 길지만, 오늘 아니면 못 먹을 것 같아 꾹 참고 기다리기로 했습니다. 당연하겠지만, 앞 사람들이 중간에 지쳐서 나가지 않는다면 앞 사람들이 모두 들어가야 여러분들이 들어갈 기회가 생기겠죠? 이런식으로 줄을 설 때, 먼저 줄을 선 사람이 먼저 식당에 입장할 수 있다는 것은 길게 설명하지 않아도 모두가 알 것입니다. 우리는 이런 구조를 선입선출 구조 (FIFO; First In First Out) 라고 부르는데, 이번에 배울 큐 라는 자료구조는 이 선입선출 구조를 따르고 있는 구조입니다. queue는 크게 5가지 함수 사용이 가능합니다. 1. push(x) : x를 queue의 맨 뒤에 추가합니다. 2. size() : queue 안에.. 2023. 8. 16.
05. 스택, 큐, 덱 - Stack 01. 스택 정의, 값 넣기/빼기 젠가를 떠올려봅시다. 통에서 젠가 블럭을 꺼낼때, 하나씩 꺼내려면 당연히 위에서 하나씩 꺼내야 할 것입니다. 만약 실수로 아래쪽에 종이 한 장을 넣어놔서 다시 꺼내려고 한다면, 통을 엎어버리지 않는 이상 위에 있는 모든 블럭을 다 꺼내야 할 것입니다. 우리는 젠가처럼 데이터를 넣는 곳과 빠지는 곳의 위치가 같은 자료구조를 스택이라고 부릅니다. 즉, 젠가와 동일하게 맨 아래에 있는 데이터를 꺼내기 위해서는 그 위의 데이터들을 모두 꺼내야 할 것입니다. 우리는 이런 구조를 후입선출 구조 (LIFO; Last In First Out) 라고 부릅니다. 영어 단어 Stack은 "쌓아올리다" 라는 의미를 갖고 있습니다. 스택 자료구조 또한 데이터가 들어가는 곳과 나가는 곳이 같다보.. 2023. 8. 16.
03. 정렬 - 기수 정렬, 정렬 속도 비교, 병합 정렬, 퀵 정렬, 합 정렬, Stable Sort, In-place Sort 앞에서 학습했던 시간복잡도는 전부 O(N2)라는 공통점이 있습니다. 이번에는 조금 특이한 시간복잡도를 가지고 있는 정렬 알고리즘을 설명하도록 하겠습니다. 이 알고리즘의 이름은 기수정렬 입니다. 기수 정렬은 맨 뒤에 있는 자릿수 부터 해당 자리수를 기준으로 정렬한 뒤, 점점 앞으로 이동하며 각 자리수를 기준으로 정렬하다가 최종적으로 가장 높은 자리수를 기준으로 정렬하는 방법입니다. 위에서 학습했던 정렬 알고리즘들과는 다르게, 기수 정렬은 값을 비교하지 않고 정렬하는 알고리즘입니다. 시간복잡도는 O(kN)으로 다른 알고리즘들과 구분되는 특성이 있습니다. 한번 자세히 알아보겠습니다. 먼저 가장 뒤에 있는 자리를 기준으로 정렬을 진행해보겠습니다. 위에서부터 밑으로 순서대로 진행하면서 가장 작은.. 2023. 8. 14.
멤리스터 뉴로모픽 반도체 소자 ‘멤리스터’ 한국과학기술연구원(KIST)은 정연주 인공뇌융합연구단 선임연구원 연구팀이 뉴로모픽 반도체 소자인 ‘멤리스터’ 소자의 고질적 문제점을 해결해 고성능·고신뢰성 뉴로모픽 컴퓨팅이 가능한 인공 시냅스 반도체 소자를 개발했다고 24일 밝혔다. 멤리스터란 메모리와 레지스터의 합성어로 소자의 저항값이 일정하지 않고 전압에 따라 저항값이 변화해 일정 시간 동안 정보를 저장하는 소자다. 뉴로모픽 반도체는 인간의 뇌를 모사해 전력 소모를 줄이면서 성능을 높이는 컴퓨팅을 위한 기술로 주목받는다. 인간 뇌의 뉴런이 스파이크 신호를 발생시키면 시냅스를 통해 다른 뉴런으로 신호가 전달되는 정보 전달 방식을 반도체 소자에 구현하는 것이다. 이를 위해서는 시냅스의 다양한 연결 강도를 표현하는 고성능.. 2023. 8. 11.

티스토리툴바