이론 공부 내용 정리/알고리즘14 c++ 라이브러리 - map 보호되어 있는 글 입니다. 2022. 8. 5. 백준 2504_괄호의 값 해당 문제 링크 ) 문제 한 줄 요약 문자열의 괄호가 온전한 개수로 이루어졌는지 파악하고, 온전한 개수로 이루어졌을 경우 괄호들이 이루는 값을 구한다. 내가 생각한 조건 우선 스택을 써야 한다고 생각했다. 그 이유는 문자열을 입력받을 때 ) 또는 ]을 입력받아서 pop해야 할 경우, 가장 최근의 문자가 나와야 하기 때문이다. 그래서 괄호들을 저장하는 문자열 스택과 괄호로 인해 만들어지는 값을 저장하는 정수 스택을 따로 만들었다. 그리고 []과 ()처럼 연속되게 완전한 괄호가 만들어지는 경우를 따로 두고 계산하였는데, 이렇게 하니 코드 길이도 길어지고 연속으로 같은 기호가 나왔을 때 처리가 비효율적이어서 다시 생각해보았다. 그래서 (인 경우와 )로 나눠서 생각해 보았는데, (인 경우는 위와 동일하게 스택에.. 2022. 8. 3. c++ 자료구조 - priority queue 백준 자료구조 문제를 풀다가 1966 프린터 큐 문제에서 우선순위 큐를 사용해서 그에 대한 내용을 정리해본다. 정의 일반적인 선형 자료구조인 큐에 우선순위 개념이 추가된 것이다. 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 속성 모든 항목에는 우선순위가 있습니다. 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 큐에서 제외됩니다. 두 요소의 우선 순위가 같으면 큐의 순서에 따라 제공됩니다. 구현 방식 구현 방식에는 배열, 연결 리스트, 힙이 있다. 구현 방법에 대해서는 해당 링크에 설명되어 있다. 이 구현 방법의 시간 복잡도에 대해 간단히 설명을 하겠다. (1) 우선순위 큐를 배열로 구현할 경우 우선순위가 높은 순서대로 배열의 가장 앞부분부터 넣는다. 우선순위가 높은 데이터를 .. 2022. 8. 2. c/c++ switch/case문에 대해 실수한 사항 일반적으로 switch/case문에서 string을 쓸 수 없다. 그렇다면 왜 사용할 수 없는지 짧게 이론적으로 정리해 보려 한다.(필자가 까먹지 않기 위함으로) c++에서 switch/case문에서 string을 왜 사용하지 못할까? 우선 switch 명령은 case가 많을수록 이론상 if문과의 성능 차이가 기하급수적으로 벌어지게 되어 있다. 여기서 이론상인 이유는 if문의 경우에도 비교하는 대상 중 어느 한 쪽이 상수라면 자동으로 점핑 테이블을 만들어 switch - case처럼 동작하기 때문이다. 잠깐 if문과 switch 문의 내부적 차이를 비교해보자. if문은 각 경우마다 값을 비교하므로 최악의 경우는 모든 case에 대해 값을 비교하는 (어셈블리에서 CMP 연산)을 한다. if문은 switch.. 2022. 7. 31. 이전 1 2 3 4 다음