자료구조

    [프로그래머스] 올바른 괄호 (Java)
    알고리즘/프로그래머스

    [프로그래머스] 올바른 괄호 (Java)

    프로그래머스 Level 2 올바른 괄호 (자바) 출처 programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 ()() 또는 (())() 는 올바른 괄호입니다. )()( 또는 (()( 는 올바르지 않은 괄호 programmers.co.kr 문제 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 ()() 또는 (())() 는 올바른 괄호입니다. )()( 또는 (()( 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때..

    [백준 1715] 카드 정렬하기 (자바)
    알고리즘/백준

    [백준 1715] 카드 정렬하기 (자바)

    백준 1715번 카드 정렬하기 (자바) 출처 www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간..

    [자료구조] 스택, 큐, 힙
    CS/자료구조

    [자료구조] 스택, 큐, 힙

    스택 스택의 개념 선형 자료구조의 일종 Last In First out(LIFO) 구조 차곡차곡 쌓이는 구조 나중에 들어간 원소가 먼저 나온다. 스택의 특징 같은 구조의 같은 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근 가능하다. 삭제는 top을 통해서만 가능하다. 스택의 연산 삭제 (pop()) : 스택에서 가장 위에 있는 항목을 제거한다. [O(1)] 삽입 (push(item)) : item 하나를 스택의 가장 윗부분에 추가한다. [O(1)] 읽기 (peek()) : 스택의 가장 위에 있는 항목을 반환한다. [O(1)] 스택 포인터(SP, Stack Pointer) push나 pop을 할 때 해당 값의 위치를 알고 있어야 하는데 스택 포인터가 위치를 기억한다. ..

    CS/자료구조

    [자료구조] Array vs List, ArrayList vs LinkedList

    배열(Array) → 크기를 정해서 사용할 수 있는 연속적인 저장 공간 Array 선언 시 같은 자료형으로 메모리 상에 연속적으로 데이터를 저장할 수 있는 공간이 확보된다. 배열 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르다. 시간 복잡도는 O(1) 단점 크기가 고정적이므로 고정된 크기보다 더 많은 데이터를 받으려는 경우 새로운 공간을 만들어 기존 데이터를 복사해주어야 한다. 효율적인 탐색을 위해 Array 데이터 사이에 비는 공간을 없이 만든다면 Array 중간에 데이터를 추가하거나 삭제할 때 빈 공간이 없도록 다수의 데이터를 옮겨야 한다. List(Linear List) → 데이터의 크기가 정해져 있지 않고, 삽입 삭제가 많이 일어나며, 검색이 적은 경우 유리. 항목들은 순서 또는 ..

    [프로그래머스] 힙(Heap) - 더 맵게 (Java)
    알고리즘/프로그래머스

    [프로그래머스] 힙(Heap) - 더 맵게 (Java)

    프로그래머스 Level 2 힙(Heap) - 더 맵게 (자바) 출처 https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같�� programmers.co.kr 문제 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 =..

    알고리즘

    [Heap Sort] 힙 정렬

    ※ 참고자료 - 유튜브(동빈나) https://www.youtube.com/watch?v=iyl9bfp_8ag&t=331s 힙 정렬이란? 완전 이진트리의 일종이다. 현재 완전히 정렬된 상태가 아니며, 중복 값을 허용한다. 병합 정렬과 퀵 정렬만큼 빠른 속도를 가지고 있다. 힙의 정의를 알아야 한다. 힙이란? 힙을 알기 위해선 이진트리를 먼저 알아야 한다. 이진트리 : 모든 노드의 자식 노드가 2개 이하인 트리 완전 이진트리 : 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리. 즉, 이진트리의 노드가 중간이 비지 않고 빽빽이 가득 찬 구조 힙 : 최솟값이나 최댓값을 빠르게 찾아내는 이진트리를 기반한 트리 최대 힙 : 부모 노드가 자식 노드보다 큰 힙 최소 힙 : 부모 노드가 자식 노드보다 작은 힙 문제에..

티스토리툴바