프로그래머스의 [3차] 파일명 정렬 문제에서 파이썬으로 푼 방식과 똑같이 C++로 문제를 푸는데, 계속 1, 2번을 제외한 테스트케이스가 모두 틀려 의문이 들었다. 질문하기 게시판을 읽어 보았더니, 보통 C++에서 사용하는 sort() 메소드가 불안정 정렬이라서 틀렸을 것이라고 한다. 글에서 말한대로 안정 정렬을 사용하여 푸니 바로 풀렸다. 알고리즘 문제를 풀며 알게 된 안정 정렬과 불안정 정렬. 이를 까먹지 않고자 다루어보려 한다.1. 불안정 정렬이란?불안정 정렬을 설명하기 전, 정렬의 개념부터 알고 가야 할듯하다.정렬이란 데이터 요소를 특정 기준에 따라 순서대로 배치하는 과정을 말한다. 각 언어의 내장 정렬 함수는 기본적으로 숫자나 문자를 오름차순으로 정리하지만, 사용자의 정의 기준에 따른 커스텀 정..

정렬 기능은 알고리즘 문제 풀이 뿐만 아니라 솔루션 및 웹사이트 등을 개발할 때에도 매우 중요한 기능이다.오늘은 파이썬의 내장함수를 통한 기본 정렬 뿐 아니라 사용자 정의 기준에 따른 커스텀 정렬 방법까지 자세히 알아보고자 한다.파이썬의 기본 정렬파이썬에서 정렬을 수행하는 가장 기본적인 방법은 sorted() 메소드와 list 자료형의sort() 내장 메소드를 사용하는 것이다. 이 두 방법을 정렬된 결과를 메소드 하나로 쉽게 얻을 수 있도록 해준다. 1. sorted() 메소드sorted() 메소드는 원본 리스트는 변경하지 않은 채 정렬된 새로운 리스트를 반환한다. 이 메소드는 리스트 뿐만 아니라 모든 반복 가능한 객체에서 사용할 수가 있다 (리스트, 튜플, 문자열 등). sorted(iterable, ..

Programmer 문제를 풀던 중 Priority Queue가 필요한 경우가 생겼다.파이썬에는 여러 라이브러리가 있다보니 대중적으로 알고리즘 문제 풀이에 많이 쓰이는Priority Queue 구현 방법을 복기하고자 한다.heapq 모듈파이썬에서는 heapq 모듈을 사용해 간단하고 효율적으로 리스트 자료형의 우선순위 큐를 구현할 수가 있다. heapq가 단순히 우선순위 큐만을 제공하기 위해 나온 것은 아니고, 최소 힙(Min-Heap) 자료구조를 제공하는 모듈이다.이를 통해 우선순위 큐를 구현할 수 있는 이유는 최소 힙은 완전 이진 트리로, 부모 노드가 항상 자식 노드보다 작거나 같은 값을 가지는 특성을 갖고 있기 때문이다. 이를 통해서 항상 최솟값을 O(1)의 시작 복잡도로 얻을 수 있고, 트리 노드를..

C++에서 키-값 쌍으로 데이터를 관리하는 자료구조는 특이하게 map과 unordered_map 두 가지가 있다.이 두 컨테이너는 얼핏 봐서는 비슷해 보이지만, 내부 구현 방식이나 성능 측면에서 간과할 수 없는 차이점이 존재한다.map과 unordered_map의 차이점과 사용 사례, 성능을 비교해보며 자신의 프로젝트에 어느 자료구조를 쓰는 것이 더욱 적합한지 판단할 수 있도록 해보자.std::mapmap은 내부적으로 균형 이진 검색 트리(BST)를 사용해 데이터를 저장한다.이로 인해 키는 항상 정렬된 상태로 저장되어 요소에 대한 삽입/삭제/검색에 O(log n)의 시간복잡도를 가진다. 추가적인 트리 구조로 인하여 메모리 사용률 또한 높다. map은 보통 키의 정렬이 필요할 때, 범위 기반의 검색이 자주..

사내 솔루션을 건드려보며 학습하던 중 아래와 같은 오류를 만나게 되었다. 오류의 원인해당 오류는 패키지명과 클래스명이 충돌할 때 발생한다고 한다. 그렇다면 왜 패키지명과 클래스명이 같면 안 될까?그 이유는 Java에서 동일한 이름을 가진 패키지와 클래스가 있을 때 컴파일러가 혼동을 일으키기 때문이다. 깊은 이해를 위해 필자의 상황으로 예시를 들어보자. package com.my.example.test;public class Example { // 클래스 내용} 필자는 `com.my.example` 패키지에 새롭게 `test`라는 패키지를 생성하였다.그런데 생성 후 패키지 내에 파일을 만드니 위처럼 컴파일 오류가 발생한 것이다. package com.my.example;public class Test..

LeetCode에서 알고리즘 문제를 푸는 사람들이라면 무조건 한 번 쯤은 접해봤을 TreeNode.Queue를 사용하면 각 노드들의 방향을 알면서 BFS 탐색이 가능하기 때문에오늘의 문제에서는 Python, C++, Java 각기 다른 언어를 사용해 Queue를 사용한 알고리즘 문제를 풀었다.Java를 사용한 큐 구현엔 익숙하지만, 아직 Python으로 구현하는 자료 구조들엔 익숙하지 않아블로그에 포스팅하며 제대로 사용하는 방법을 복기하고자 한다.Queue란 무엇일까 큐는 데이터를 순서대로 처리하기 위해 사용하는 FIFO 구조의 선형 자료 구조이다. 큐의 가장 큰 특징은 FIFO 구조이다. FIFO(피포; First-In First-Out)란 가장 먼저 온 데이터가 가장 먼저 나가고, 가장 늦게 온 데이..