728x90
728x90
[ 42경산 & 알고리즘/42 과제 회고 ][42경산 push_swap] 11개 명령어로 정렬하기: 순위 변환, 비용 계산, 이진 기수 정렬2025-09-21 17:33:28TL;DR (세 줄 요약)push_swap은 스택 두 개와 명령어 11개만으로 정수를 정렬하는 42 과제입니다. 최고점 기준은 숫자 100개를 700회 미만, 500개를 5,500회 이하의 명령어로 정렬하는 것입니다.숫자를 0부터 N-1까지의 순위로 바꾸면 문제가 단순해집니다. 이진 기수 정렬은 구현하기 쉽지만, 계산하면 100개에 1,084회, 500개에 6,784회가 필요해서 최고점 기준에는 미치지 못합니다.명령어를 줄이려면 회전 방향(ra와 rra) 가운데 횟수가 적은 쪽을 고르고, rr과 rrr로 두 스택을 함께 돌려야 합니다. 제 구현은 이 비용 계산을 쓰는 그리디 방식입니다.이 글은 42경산의 push_swap 과제를 풀면서 정리한 내용입니다. 과제의 규칙, 명령어 11개, 숫자를 순위로 바꾸..
[ 42경산 & 알고리즘/자료구조 & 코테 ]코드트리 2025 리뉴얼 완전 분석: UI/UX 개편부터 백준·프로그래머스와의 비교까지2025-02-09 11:56:40TL;DR (세 줄 요약)코딩테스트 학습 서비스인 코드트리가 2025년 초에 화면과 학습 기능을 크게 바꿨습니다. 이 글은 무엇이 달라졌고 어디에 쓰면 좋은지 정리합니다.목표 기업에 맞춘 실력 진단과 맞춤 학습 코스가 추가됐습니다. 디자인이 정리됐고 한국어와 영어를 지원합니다. 커리큘럼의 이름은 Trail로 바뀌었고, 예시 코드는 5개 언어로 제공합니다.기초 학습과 유형 정리는 코드트리가 낫고, 문제 수와 실제 시험 환경은 백준과 프로그래머스가 낫습니다. 세 서비스는 쓰임이 달라서 함께 쓰는 편이 좋습니다.이 글은 "코드트리 x 글또 블로그 챌린지 2기"에서 코드트리 체험권을 받아 쓴 후기입니다. 코딩테스트는 회사가 지원자의 프로그래밍 실력을 확인하려고 보는 시험입니다. 기능과 가격에 대한 내용은 202..
[ 42경산 & 알고리즘/자료구조 & 코테 ][알고리즘] 퀵 정렬(Quick Sort) 동작 원리와 시간 복잡도 분석: 피벗 선택과 분할 정복2025-02-02 20:27:41TL;DR (세 줄 요약)퀵 정렬은 평균 O(n log n)으로 빠른 정렬 알고리즘입니다. 하지만 피벗(기준 값)을 잘못 고르면 이미 정렬된 배열에서 O(n²)까지 느려집니다.피벗을 기준으로 작은 값과 큰 값을 나누고, 나뉜 두 구간에 같은 일을 반복합니다. 한쪽으로만 나뉘면 비교 횟수가 (n-1)+(n-2)+…+1이 되어 n의 제곱에 비례합니다.무작위 피벗, 미디언-오브-쓰리, 작은 구간의 삽입 정렬 전환, 재귀 깊이 줄이기, Introsort로 최악의 경우를 피합니다.한 기업의 필기 테스트에서 나온 문제를 계기로 퀵 정렬을 다시 정리했습니다. 정렬은 값을 크기 순서대로 늘어놓는 일입니다. 이 글은 퀵 정렬의 기본 개념, 동작 원리, 최악의 경우가 생기는 이유, 그것을 줄이는 방법을 순서대로 설명합니다..
[ 42경산 & 알고리즘/자료구조 & 코테 ]코딩테스트 학습 서비스, 코드트리 사용 후기2024-03-31 23:58:52TL;DR (세 줄 요약)코딩테스트 공부에서 가장 어려웠던 일은 무엇을 어떤 순서로 풀지 정하는 것이었습니다. 백준과 프로그래머스는 문제가 많지만 공부 순서를 정해 주지는 않습니다.코드트리는 기초 문법부터 자료구조, DP, DFS, BFS까지 단계별 문제집으로 나눠 두었습니다. 각 단계를 기본, 연습, 테스트로 나누어 스스로 확인하게 하고, 레벨 테스트로 지금 수준을 보여 줍니다.학습 설계는 코드트리가 가장 좋다고 느꼈습니다. 다만 사용자가 적어서 함께 푸는 사람을 찾기 어려웠고, 화면에 작은 버그가 있었습니다. 취업 준비를 본격적으로 할 때는 결제해서 쓸 생각입니다.이 글은 글또 9기에서 진행된 코드트리(CODE TREE) 후원을 바탕으로 쓴 후기입니다. 유료 이용권을 제공받았습니다. 좋았던 점과 아쉬..
[ 42경산 & 알고리즘/자료구조 & 코테 ][자료구조/C언어] 레드-블랙 트리(Red-Black Tree) 규칙·회전·삽입·삭제 정리2024-02-18 23:57:24TL;DR (세 줄 요약)레드-블랙 트리는 노드마다 빨강 또는 검정 색을 붙이고, 색에 대한 다섯 가지 규칙을 지키는 이진 탐색 트리입니다.이 규칙 덕분에 트리의 높이가 log n 수준으로 유지됩니다. 그래서 탐색, 삽입, 삭제가 최악의 경우에도 O(log n) 시간에 끝납니다.삽입이나 삭제로 규칙이 깨지면 색을 바꾸거나(재색칠) 회전으로 구조를 바꿔서 고칩니다. 삽입은 삼촌 노드의 색을, 삭제는 형제 노드의 색을 보고 처리 방법을 고릅니다.이 글은 크래프톤 정글 4기 Part 2 "탐험 준비" 4주차에 레드-블랙 트리를 공부하면서 정리한 기본 개념입니다. 먼저 알아야 하는 개념, 다섯 가지 규칙, 회전, 삽입, 삭제 순서로 설명합니다.1. 레드-블랙 트리는 무엇인가요?레드-블랙 트리(Red-Black ..
728x90
728x90