알고리즘

[C] 단방향 연결리스트(Linked List) 구현

by

단방향 연결리스트의 연결리스트와 노드 구조체 선언 cnt는 연결리스트의 노드 개수. 연결리스트의 head는 첫 노드, 실제 값이 들어가지는 않으며 head에 연결될 다음노드부터 값이 들어간다. tail노드는 연결리스트의 마지막 노드, 노드 추가시 tail 다음에 연결된다. 연결리스트 초기화 연결리스트의 head노드를 만들어주고 tail노드는 없으므로 NULL. 만약 연결리스트에 실제 값이 들어가는 노드가 하나라면 그 노드는 tail 노드 추가 추가될 tmp노드를 만든 … Read more

[C++, STL] 알고리즘 문제풀이를 위한 pair

by

서론 pair는 두 종류의 자료를 하나의 컨테이너에 저장할 수 있는 템플릿이다. 순번 이름 1 김자료 2 이구조 3 박페어 위 테이블의 자료를 벡터에 저장하려고 한다. 우선 벡터를 두 개 만들고 첫 번째 벡터에 순번을 넣고 두 번째 벡터에 이름을 넣는 방법이 있다.   0 1 2 V1 1 2 3 V2 김자료 이구조 박페어 그러나 … Read more

[C++, STL] 알고리즘 문제풀이를 위한 셋(set)

by

서론 set의 특징 셋은 자료를 담을 수 있는 컨테이너다. 그러나 벡터, 리스트 등 시퀀스 컨테이너와는 다르게 원소의 삽입순서에 의미를 두지 않는다. 일단 셋에 원소가 삽입되면 자동으로 오름차순이나 내림차순으로 정렬된다. 따라서 삽입순서가 필요하다면 사용해서는 안된다. 셋의 가장 큰 특징은 중복값을 허용하지 않는 것이다. 셋에 1을 10번 넣으면 첫 한번만 들어가고 나머지는 버려진다. 셋에 원소가 들어가면 그 … Read more

[C++, STL] 알고리즘 문제풀이를 위한 우선순위 큐(priority queue)

by

서론 우선순위 신용카드 신청을 위해 상담사와 통화를 했다. 급하게 받아야 해서 금요일까지 수령할 수 있겠냐고 여쭸더니 긴급으로 발송해주겠다고 한다. 원래는 신청받은 순서대로 발송을 하겠지만 내 카드는 우선순위를 높여서 먼저 발송해 줄것이다. 큐와 우선순위 큐 [C++, STL] 알고리즘 문제풀이를 위한 큐(queue) 우선순위 큐는 우선순위가 포함된 자료가 들어간다. 그러면 큐 내부에서 pop을 했을 때 가장 우선순위가 높은 … Read more

[C++, STL] 알고리즘 문제풀이를 위한 스택(stack)

by

서론 쌓여있는 접시 초밥과 LA갈비를 동시에 먹고 싶었던 나는 뷔페에 갔다. 그리고 음식을 담기 위한 접시를 집으려던 순간, 직원이 내가 집으려던 접시 위에 새로운 접시들을 또 쌓았다. 새로 올려진 접시에는 물기가 가득했다. 물기가 없는 처음 보았던 접시를 가져가고 싶지만 가져갈 수 없다. 이미 그 위에 많은 접시들이 쌓여있기 때문이다. 자료를 쌓는 스택 스택을 번역하면 명사로는 … Read more

[C++, STL] 알고리즘 문제풀이를 위한 큐(queue)

by

서론 줄을 세우다 어느 중학교, 점심시간을 알리는 종과 함께 학생들이 달린다. 배식을 먼저 받기 위해서는 달려야한다. 한참을 달리던 학생들은 식당 입구에서 식권을 내고 한줄로 천천히 배식구를 향해 걸어간다. 이들은 더이상 뛰지 않는다. 먼저 식권을 낸 학생이 먼저 배식을 받을것을 알기 때문이다. 그래서 큐는 뭐지? 큐는 먼저 들어온 자료가 먼저 나가는 자료구조다.(=선입선출, First In First Out) … Read more

[C++, STL] 알고리즘 문제풀이를 위한 벡터(vector)

by

서론 우리는 다수의 자료를 저장하기 위해 배열을 사용한다. 그러나 배열은 임의의 위치에 원소를 삽입하거나 할당된 메모리가 꽉 찼을때 등 여러 상황에서 까다로운 문제가 발생한다. 이를 해결하기 위해 동적배열을 사용한다. 동적배열은 사용하면서 원소가 추가되면 메모리를 조금씩 추가 할당하며 대표적으로 리스트, 벡터가 있다. 리스트는 배열이 가지는 위 단점을 해결할 수 있다. 그러나 배열과 벡터는 원소에 직접 접근하여 … Read more

시간 복잡도 표기법 빅오, 빅오메가, 빅세타

by

* 시간 복잡도를 처음 접한다면 아래 글은 이해하기 어려울 수 있습니다. 시간 복잡도 같은 목적지를 향해 가는 길이 여러 갈래일 때 우리는 더 빠르게 도착하는 길을 찾는다. 마찬가지로 동일한 목적을 가지는 기능을 여러 알고리즘으로 구현했을 때 그것들의 효율성을 비교하기 위해 시간 복잡도를 사용한다. 당연히 더 오래 걸리면 더 안 좋다. 알고리즘A의 시간복잡도가 O(n)이고 알고리즘B의 시간복잡도가 … Read more