1. 배열(Array)특징 : 크기가 고정됨. ( new int[10] ).메모리가 연속적으로 할당되는 것이 특징이다.시간 복잡도 : 조회 O(1) , 검색 O(N)메서드/속성설명비고arr.length배열의 길이 (메서드 x, 필드)() 안붙인다. 메서드 아니다.Arrays.sort(arr)오름차순 정렬O(N log N) 시간 복잡도Arrays.fill(arr, 0)배열을 특정 값으로 초기화반복문보다 빠르다.Arrays.toString(arr)배열의 내용을 문자열로 바르게 출력한다.디버깅 시 필수 2. 문자열 (String , StirngBuilder)특징 : String은 불변이며, StringBuilder는 변경이 잦을 때 사용해야한다.메서드/속성설명비고str.length()문자열 길이배열과 다르게 ..
1. 지금까지 학습한 부분 정리 (자료구조)스택 : 프링글스 통 (마지막에 넣은 게 먼저 나옴)큐 : 놀이공원 줄 (먼저 온 사람이 먼저 나옴)덱 : 양쪽이 뚫린 터널 (양방향 큐)스택과 큐가 도구였다면, 이분 탐색은 그 도구를 효율적으로 다루는 지능이라고 할 수 있다. 2. 업-다운(Up-Down) 게임의 필승법이분 탐색(Binary Search)은 술자리 게임인 업-다운 게임과 완벽하게 똑같다. 상황 : 1부터 100까지 숫자 중, 술래가 생각한 숫자(70)를 맞춰야한다.하수 (순차 탐색, O(N)) : 1 -> 2 -> 3 ...고수 (이분 탐색, O(log N)) : 중간을 찌름 (질문 한 번에 후보가 절반씩 소거된다.) 3. 조건 : 반드시 숫자가 순서대로 정렬이 되어야 한다.이분 탐색 코드를 ..
1. 숫자 합산은 long 타입으로 진행한다. (int로 합산하다가 overflow 날 수도 있기 때문)2. Stack을 구현할 때에는 Stack 클래스를 쓰지 않는다.옛날에 구현된 Stack 클래스는 동기화 강제, Vector 상속으로 무거운 클래스와 필요없는 기능까지 있어 속도가 매우 느리다.Deque stack = new ArrayDeque();위 와같이 덱 클래스를 쓰면 매우 빠른 속도를 낼 수 있다.3. 문자열 연결은 StringBuilder를 쓰자. (특히 반복문!)단순 연결: String str = "A" + "B"는 괜찮음.반복 연결: for문 안에서 str += "A"를 하면 매번 새로운 객체가 생성되어 메모리와 시간이 폭발적으로 낭비됨.출력: System.out.println을 여러 ..
1. 무한 동력, 원형 큐(Circular Queue)큐를 구현할 때 배열의 끝에 다다르면, 다시 처음으로 돌아가라 라는 규칙이 필요하다.이때 등장하는 것이 바로 "나머지 연산자(Modulo, %)"다. 공식 : (인덱스 + 1) % 배열 크기 이 공식 하나면 인덱스가 0, 1, 2, 3, 4 -> 0, 1, 2 .. 식으로 빙글빙글 돈다.나머지 연산자를 이용해서 배열 크기보다 작은 값의 포인터를 이용하여 1씩 늘어나는 반복적인 작업을 진행 할 수 있는 것이다.package step03;public class MyCircularQueue { private int[] queue; private int front; private int rear; private int maxBufferS..
1. 줄 서기의 미학, 큐(Queue)큐의 핵심 규칙은 선입선출(First-In, First-Out)이다. 먼저 온 사람이 먼저 업무를 본다는 원칙이다.예시 : 맛집 웨이팅, 고속도로 톨게이트, 은행 창구또 다른 예시 : 프린터 인쇄 대기열, 키보드 입력 버퍼(먼저 친 글자가 먼저 찍혀야 하기에)2. 큐를 지키는 두 문지기 : Front와 Rear스택은 구멍이 하나이기 때문에 Top이라는 포인터만 있으면 됐지만, 큐(터널)는 입구와 출구가 달라서 두 개의 포인터를 관리해야 한다. 이게 스택보다 구현이 조금 더 까다로운 이유이기도 하다.Rear (꼬리) : 데이터가 들어오는 곳 (가장 최근 데이터)"새로운 데이터가 들어오면 어디에 줄을 세울까?"를 가리킨다.데이터가 들어올 때마다 (Enqueue) 뒤로 한..
1. 스택(Stack)이란 무엇인가?스택(Stack)이란 사전적 의미는 '무더기', '쌓다'라는 뜻이다.가장 중요한 핵심은 'LIFO (Last-In, First-Out) 후입 선출' 이다. 예를 들면, 프링글스 통이나 막혀있는 골목길과 같다.입구와 출구는 하나뿐이다. (위쪽 구멍)가장 먼저 넣은 감자칩(맨 아래)을 먹으려면, 그 위에 쌓인 감자칩을 다 꺼내 먹어야한다.중간에 있는 감자칩(데이터)을 쏙 뺄 수 없다. 무조건 맨 위(Top)에서만 꺼낼 수 있다.2. 스택의 3대 동작 (용어 정리)스택을 다룰 때 사용하는 명령어는 전 세계 공통으로 딱 3가지만 기억하면 된다.Push (밀어 넣기): 데이터를 맨 위에 쌓는다.Pop (터뜨리기/꺼내기): 맨 위에 있는 데이터를 꺼내면서 삭제한다.Peek (살짝..
1. 자료구조를 배우는 이유 (냉장고 정리의 법칙)개발자가 하는 일은 요리사와 비슷하다고 보면 된다.알고리즘: 요리 레시피 (어떻게 조리를 할 것인가?)자료구조: 냉장고 정리법 (재료를 어디에다가 어떻게 보관할 것인가?)아무리 칼질(알고리즘)을 잘해도, 냉장고가 엉망이라 파 하나를 찾는데에 10분 이상이 걸리면 그 요리는 망한다.반대로 재료를 넣고 꺼내기 좋은 위치에 정리를 해두면(자료구조), 그 요리의 속도는 매우 빨라져 효율적으로 요리를 할 수 있다. 코딩테스트 레벨 3, 4의 문제는 이런 상황을 제시한다고 한다. 데이터가 100만 개가 쏟아질 때, 1초 안에 가장 큰 숫자를 찾으시오. 그냥 아무 데나 마구잡이로 넣어두면, 찾는 데에는 1시간이 걸리지만, 특정한 형태로 정리를 해두면 0.1초만에 찾..
[코딩테스트] 시간복잡도와 O(1) 완벽 정리 - 초보자도 이해하는 Big O 표기법코딩테스트를 준비하면서 가장 많이 듣는 말이 "시간복잡도를 고려해야 한다"이다. 오늘은 시간복잡도가 무엇인지, 특히 O(1)이 왜 중요한지 아주 쉽게 설명할 예정이다.📌 시간복잡도란?시간복잡도(Time Complexity)는 간단히 말해서 "프로그램이 얼마나 오래 걸리는가?"를 나타내는 방법이다.좀 더 정확히 말하면, 데이터의 양이 늘어날 때 실행 시간이 어떻게 변하는지를 수학적으로 표현한 것이다.예를 들어보자. 이름이 적힌 카드 더미가 있다고 가정하자.카드가 10장일 때: 찾는데 1초 걸림카드가 100장일 때: 찾는데 10초? 100초? 아니면 여전히 1초?이렇게 데이터의 양(카드 수)에 따라 시간이 어떻게 증가하는지..
