지난 글에서는 시간 복잡도와 공간 복잡도에 대해서 알아보았습니다.오늘은 코딩 테스트 문제에서 빠지지 않고 등장하는 자료구조(Data Structure)와 그 복잡도에 대해 정리해보겠습니다. 자료구조는 데이터를 어떻게 저장하고, 어떻게 꺼내고, 어떻게 다룰지를 결정하는 핵심 개념입니다.각 자료구조는 장단점이 있고, 연산별 복잡도가 달라지기 때문에 어떤 문제에서 어떤 자료구조를 쓰는지 선택하는 게 중요합니다. 🤔 자료구조란?자료구조(Data Structure)는 데이터를 효율적으로 저장하고 관리하기 위한 방법을 의미단순히 데이터를 담는 그릇이 아니라, 어떻게 저장하고 → 어떻게 꺼내고 → 어떻게 다룰지를 정하는 규칙과 구조를 포함같은 데이터를 저장하더라도 자료구조에 따라 성능(시간·공간 복잡도)이 달라짐..

지난 글에서는 Big-O 표기법과 시간 복잡도에 대해서 알아봤습니다.오늘은 코딩 테스트 문제에서 시간 복잡도와 함께 자주 언급되는 공간 복잡도(Space Complexity)에 대해 정리해 보겠습니다. 공간 복잡도란? 프로그램이 실행될 때 필요로 하는 메모리 사용량입력 크기 n에 따라 메모리 사용량이 어떻게 변하는지 나타냄시간 복잡도가 얼마나 오래 걸리냐라면, 공간 복잡도는 얼마나 많은 메모리를 쓰냐 라는 관점 공간 복잡도도 Big-O 표기법을 사용? 시간 복잡도는 연산 횟수 증가율을 Big-O로 표현공간 복잡도는 메모리 사용량 증가율을 Big-O로 표현결국 입력 크기 n이 커질 때, 얼마나 많은 자원이 필요 해지는가를 같은 방식으로 표현 공간 복잡도 종류종류설명예시 / 복잡도Fixed Part (고정 ..

https://www.acmicpc.net/problem/2745 36진법이란? 10진법에서는 0 ~ 9까지만 한 자리로 표현하고, 36진법에서는 더 많은 숫자를 한 자리에 담기 위해 알파벳 대문자를 사용0 ~ 9 → 숫자 그대로 (0 ~ 9)A ~ Z → 10 ~ 35알파벳숫자알파벳숫자알파벳숫자알파벳숫자알파벳숫자알파벳숫자A10F15K20P25U30Z35B11G16L21Q26V31 C12H17M22R27W32 D13I18N23S28X33 E14J19O24T29Y34 문제 풀이표에서 Z = 35, "ZZZZZ" = 자리값 계산 방식대부분 “첫 번째 자리”를 오른쪽(일의 자리)로 생각하는데 실제 코드는 왼쪽부터 차례대로 읽어도 문제가 없음! 차이는 계산 순서일 뿐, 결과는 동일 코드에서는 ans ..

코딩 테스트 문제를 풀다 보면 빠지지 않고 등장하는 개념이 바로 시간 복잡도입니다.이번 글에서는 시간 복잡도가 무엇인지, 어떤 종류가 있는지, 그리고 실제 코드에서는 어떻게 표현되는지를 살펴보겠습니다. 이를 이해하기 위해 먼저 연산 횟수와 Big-O 표기법을 알아본 뒤,시간 복잡도의 종류와 예제 코드를 통해 구체적으로 정리해보겠습니다. 📌 연산 횟수란?알고리즘을 실행할 때 수행되는 기본 연산의 개수실제 컴퓨터가 처리하는 “한 단계 동작(step)”을 단순화해서 센 것초 단위로 시간 측정을 하면 컴퓨터 성능/환경에 따라 달라지므로, 기본 연산 횟수를 세어야 “입력 크기 n에 따른 실행 증가율”을 객관적으로 비교할 수 있음시간 복잡도는 이 연산 횟수를 단순화해서 “증가율(Big-O)”로 표현한 것기본 연..

문제 https://leetcode.com/problems/middle-of-the-linked-list 메서드 실행 코드 // 단일 연결 리스트 노드 정의class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; }}// 실행 테스트public class Main { public static void main(String[] args) { // 연결 리스트 [1,2,3,4,5] 만들기 ListNode head1 = ..

문제https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero 문제 내용 요약정수 num이 주어진다.목표: num을 0으로 줄이는 데 필요한 단계(step)의 수를 반환한다.단계 규칙:현재 숫자가 짝수라면 → 2로 나눈다.현재 숫자가 홀수라면 → 1을 뺀다 내가 작성한 답변 class Solution { public int numberOfSteps(int num) { int count = 0; while (num != 0) { if (num % 2 == 0) { // 짝수 num /= 2; } else { // 홀수 ..