본문 바로가기

분류 전체보기

 (48)
자료구조 - 그래프 그래프는 점과 선으로 이뤄진 자료구조다 보통은 순환이 가능하면 그래프라고 판단한다. 먼저의 그래프의 구성을 살펴보자면 그래프의 점은 '정점' 다른 말로 노드라고도 부르며 선은 '간선' 이라고 부른다. 순환은 특정 노드에서 출발해 다시 돌아올 수 있는 것을 뜻하며 순환되지 않아도 그래프인 경우도 존재한다. 아래 그림을 보자. 위와 같이 1 에서 출발해 1 로 가지 못하는 경우에는 비순환 그래프 이며 동시에 우측의 트리로 표현이 가능하다. 만약 저 상태에서 그림과 같이 간선이 추가 되면 순환이 가능한 상태가 되며 트리가 아닌 그래프가 된다. 또한 위와 같이 화살표가 없이 단순 선형태의 간선은 양방향 간선으로 판단하며 두 노드가 서로 접근이 가능하다. 마지막으로 간선에 숫자를 추가해 가중치를 넣을 수 도 있는..
자료구조 - 리스트 리스트는 자료구조에서도 다른 자료구조를 구현하는데 기반이 되는 선형 자료구조이자 추상적 자료형이다. 리스트는 크게 다음과 같이 배열로 구현된 순차리스트, 연결 리스트로 구현된 연결리스트로 나뉜다. 순차 리스트는 단순 배열로 구현된 리스트로 어느 위치에서든 입출력 가능하다. 하지만 위와 같이 밀어내는 연산을 해야하며 마찬가지로 삭제 시에도 동일한 연산을 수행하며 추가 연산 시간이 소모된다. 연결 리스트는 순차 리스트와 다르게 입출력 시 추가 연산을 소모하지 않는다 대신 원소들을 탐색하는 과정에서 인덱스를 명시해 빠르게 출력하지 않고 아래와 같이 타고 들어가 직접 원소를 찾는 추가 작업을 진행한다. 연결 리스트는 그림과 같이 노드라고 불리는 데이터 덩어리를 1개의 원소를 가지며 노드는 입력된 데이터인 데이터..
자료구조 - 덱(Deque) 덱은 스택과 큐의 장점만 합쳐둔 자료구조로 가장 최근, 가장 마지막 데이터를 입출력 할 수 있는 자료구조다. 이중 연결 리스트로 구현되어있으며 아래의 그림과 같이 입출력을 진행한다. 덱이 강력한 이유는 기존의 스택이나 큐는 한 방향에서만 입력 혹은 출력이 가능했지만, 덱은 양쪽에서 기존의 시간을 똑같이 소모하며 데이터를 입출력이 가능한 것이며 그로인해 프로그래머스나 백준 문제풀이에 종종 등장한다. 반대로 덱을 모르면 못푼다;
자료구조 - 큐(Queue) 데이터 삽입 시 가장 마지막에 저장하고 데이터 추출 시 가장 앞에 있는 원소를 출력하는 자료구조 흔히 식당에서 기다릴 때 먼저온 사람부터 들어가는 선착순을 생각하면된다. 위의 그림처럼 큐는 가장 앞의 원소를 가르키는 Front, 가장 뒤를 가르키는 Rear 로 위의 두 위치를 관리하며 큐에 원소를 삽입 혹은 추출 시 Front 와 Rear 의 값을 증가시키며 위의 동작을 수행한다. 하지만 큐는 정해진 크기 내에서는 결국 앞에 비어있는 공간으로 자료를 옮겨 주는(그만큼 시간을 소모) 작업을 해야 지속적으로 사용할 수 있는 단점이 있다. 그래서 개발자들은 단순 선형 큐의 단점을 개선해 아래 그림과 같은 원형 큐로 발전시켰다. 원형 큐 또한 정해진 길이 내에서 초과가 발생하면 오류가 발생하지만 빈 공간이 있을..
자료구조 - Stack 가장 최근에 들어온 데이터를 가장 먼저 출력하는 자료구조. 가장 최근에 들어왔던 데이터를 필요로 하는 기능에 사용하는 자료구조로 우리가 자주 사용하는 Ctrl + Z 나 웹 페이지의 뒤로가기 등을 예로 들 수 있다. 스택의 연산은 3가지로 다음과 같다. 1. push : 데이터 삽입 2. pop : 가장 최근 데이터를 추출 -> 스택에서 삭제됨. 3. peek : 가장 최근 데이터를 반환 -> 스택에서 삭제되지 않음 단, 가장 최근의 값 이전의 값들을 가져오려면 그만큼 까다로운 것이 단점이다. 다음과 같이 a > b > c > d > e 순으로 push 를 한 상태에서 a 값을 가져오려 한다면 pop 을 5번 해야 원하는 값인 a 를 가져올 수 있으며 이전에 저장된 값들은 삭제된다. 따라서 주 목적이 가..
자료구조 개요 자료구조는 데이터를 관리하는 방법이다. 흔히 우리는 프로그래머스나 백준에서 문제의 솔루션을 구현할 때 배열, 큐, 스택 등의 클래스를 활용한다. 하지만 더 큰 관점에서 보면 저 클래스들은 자료구조라고 하는 이론을 기반으로 자바 프레임워크에서 제공하는 클래스이며 오늘은 그 기반인 자료구조를 알아보려고 한다. 그럼 자료구조에서 말하는 자료는 무엇일까? 필자는 개인적으로 기본 자료형이라고 생각한다. 기본 자료형 또한 입력한 값을 가지고 있는 가장 작은 단위의 자료구조라고 볼 수 있지만, 자료구조에서 말하는 자료는 이 기본 자료형들을 일렬로 세워서 순서를 매기거나 하나의 객체가 다른 객체를 가르키는 것 같은 구조로 저장하는 것이라고 생각한다. 대부분의 언어에서 지원하는 공통 기본 자료형은 다음과 같다. 다음으로..
파일명 정렬 https://school.programmers.co.kr/learn/courses/30/lessons/17686 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Level 2 사실 상 3 에 가까운 자바 내장 함수형 인터페이스 Comparator 를 사용해 푸는 문제였다... 나는 이걸 장장 2시간에 걸쳐 직접 정렬 로직을 구현했는데 다른 사람들 풀이를 보고 새로운 영역에 발을 디뎠다. Comparator 는 Java 에서 제공하는 특정 기능을 가진 인터페이스 객체 중 하나로 이런 인터페이스를 함수형 인터페이스 라고 한다. (쉽게 말해 그냥 자바에 들어있..
객체 지향 프로그래밍, 절차 지향 프로그래밍 Java 는 객체 지향 프로그래밍 언어다. 개발에 조금이라도 관심이 있는 사람은 누구나 한 번쯤은 들어본 문장. 객체 지향 프로그래밍 언어라는 건 결국 Java 는 객체 지향 프로그래밍을 하기 위한 언어라는 뜻인데, 그렇다면 여기서 말하는 객체 지향 프로그래밍이란 뭘까? 컴퓨터는 명령을 수행하려면 명령어를 받아야하고 프로그램은 이러한 명령어들을 코드로 가진다. 하지만 기본 명령어 코드로만 구성된 프로그램을 짜게 되면 하나의 코드에 방대한 양의 코드가 들어가야 할 것이고 개발하기도 힘들며 이후 다른 개발자가 해당 프로그램 수정을 하기도 힘들다. 그래서 초기 개발자들이 명령어가 아닌 프로그램의 기능과 속성으로 다시 재정의한 것이 객체라고 볼 수 있다. 예를 들어 Java 로 코딩할 때 우리는 Java 에서 ..

티스토리툴바