연결 리스트(Linked List) 연결 리스트는 떨어진 공간에 있는 데이터들을 포인터를 이용하여 연결되어 있는 자료구조이다. 배열은 순차적으로 연결되어 있는 공간에 데이터를 넣는 자료구조여서 배열과는 다르다. 연결 리스트는 노드로 이루어져 있는데, 여기서 노드란 데이터와 포인터를 담고 있는 공간 단위이다. 포인터는 다음 노드의 주소 값을 저장하는 공간이다. 장점 미리 공간을 할당하지 않아도 됨 단점 연결을 위한 별도 공간이 필요하므로, 저장공간 효율이 좋지 않음 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림 중간 데이터 삭제 시, 앞 뒤 노드의 연결을 재구성해야 하는 부가적인 작업이 필요 연결 리스트를 직접 구현해보며 장,단점을 살펴보고 시간 복잡도에 대해서도 알아보자 구현 IList 인터페이스..
스택(Stack) 스택은 데이터를 제한적으로 접근할 수 있는 자료구조이다. 앞선 글에서 설명한 큐는 FIFO 방식을 사용하는 자료구조이다. 스택은 LIFO(Last-In, First-Out) 방식을 사용하는 자료구조이다. 즉, 가장 마지막에 넣은 데이터를 가장 먼저 꺼내는 자료구조라고 할 수 있다. 이 자료구조가 활용되는 대표적인 예시로는 우리가 지금 사용하고 있는 Java의 JVM이다. JVM에는 메서드 호출 시, 스택 메모리에 메서드가 담기는데 이 때 스택 자료구조가 활용된다. 예를 들어 A메서드 안에서 B메서드를 호출한다고 가정해보자. 그럼 A메서드가 스택 영역에 할당되고, 그 다음 B메서드를 호출하는 부분에서 B메서드가 할당될 것이다. 당연하게도 메서드의 흐름상 B메서드가 먼저 동작이 끝날테니 B..
객체지향 프로그래밍(OOP, Object-Oriented Programming) 객체지향 프로그래밍은 객체들의 집합으로 프로그램의 상호 작용을 표현하며 데이터를 객체로 취급하여 객체 내부에 선언된 메서드를 활용하는 방식을 말한다. 설계에 많은 시간이 소요되며 처리 속도가 다른 프로그래밍 패러다임에 비해 상대적으로 느리다. 특징 객체지향 프로그래밍은 추상화, 캡슐화, 상속성, 다형성이라는 4가지 특징이 있다. 1. 추상화 (abstraction) 추상화란 복잡한 시스템으로부터 핵심적인 개념 또는 기능을 간추려내는 것을 의미한다. 예를 들어 사람이라는 객체가 있다고 가정을 해보자. 사람은 모두 밥을 먹고, 잠을 잔다. 하지만 운전을 하는건 성인만 가능하다고 하면 추상화를 통해 밥을 먹는다, 잠을 잔다라는 기..
CS는 면접을 위한 CS 전공지식 노트 책을 학습하며 글을 올릴 예정이다. 오늘은 프로그래밍 패러다임에 관해 정리를 해보려고 한다. 자바를 처음 공부하면 객체 지향 프로그래밍이라는 단어를 많이 들을텐데 이것도 프로그래밍 패러다임 중 하나이다. 프로그래밍 패러다임 프로그래밍 패러다임은 개발자에게 프로그래밍의 관점을 갖게 해주는 개발 방법론이다. 객체 지향 프로그래밍은 프로그램을 상호 작용하는 객체들의 집합으로 볼 수 있게 한다. 즉 객체를 관점으로 개발하는 방법론이라고 할 수 있다. 자바는 객체지향 프로그래밍을 지원하는 대표적인 언어인데 1.8부터는 함수형 프로그래밍을 지원하기 위한 람다식, 선언형 프로그래밍을 위한 스트림 같은 기능이 추가되었다. 프로그래밍 패러다임은 크게 선언형, 명령형으로 나뉘고 선언..
큐(Queue) 큐는 먼저 입력한 데이터를 먼저 꺼내는 자료구조이다. FIFO(First-In, First-Out) 방식을 사용하는 자료구조라고도 할 수 있다. 이는 만약 우리가 식당에 줄을 서면 먼저 줄을 선 사람이 먼저 입장을 하는 것과 동일하다고 생각하면 될 것 같다. 위의 그림에 주요 용어들이 있는데, 설명하자면 아래와 같다. Enqueue : 큐에 값을 넣는 기능 Dequeue : 큐에서 값을 꺼내는 기능 head : 큐의 맨 앞 부분, front 라고도 함 tail : 큐의 맨 뒷 부분, rear 라고도 함 큐에 값이 추가된다면, tail 위치에 값이 Enqueue 될 것이다. 그리고 값을 지운다면 head의 값이 Dequeue 될 것이다. Enqueue 위의 그림처럼 큐는 선입선출 구조이고,..
배열(Array) 배열은 값을 나열하고, 각 값을 인덱스에 대응하도록 구성한 자료구조이다. 배열이 필요한 이유 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 같은 종유의 데이터를 순차적으로 저장 장점 값에 빠른 접근이 가능하다. (시간복잡도 O(1)) 단점 중간에 값을 추가, 삭제하기가 쉽지 않다. 미리 크기를 할당해야한다. 또는 배열의 크기를 가변할 수 없다. 위의 내용들을 자바로 예를 들어서 알아보려고 한다. 우선 먼저 배열을 만들어주는데, 위의 단점에 설명했듯이 배열은 선언할 때 미리 크기를 할당해야한다. 그래서 아래와 같이 크기가 7인 배열을 하나 만들어주자. int[] arr = new int[7]; 위의 그림처럼 크기가 7인 배열이 생성된다. int형의 배열을 생성했기 때문에 int 자..
리스트는 자바에서 제공하는 자료형 중 하나로, 가장 대표적인 클래스로는 ArrayList가 속해있다. 리스트는 배열과 동일하지만 배열은 크기가 고정되어있어 상당히 불편하다. 하지만 리스트는 동적으로 크기가 변하는 큰 장점이 있다. 리스트에 대해 자세히 알아보려고 한다. 위의 그림을 보면 List 인터페이스를 상속받는 여러 클래스들이 있다. List 인터페이스와 각 클래스들에 대해 알아보자. List List는 값들을 순차적으로 나열한 자료구조이다. 인덱스가 존재하고, 값의 중복이 허용된다. 주요 메서드 메서드 반환타입 설명 add(E e) boolean 요소를 맨 끝에 추가 add(int index, E element) void 요소를 지정된 위치에 추가 clear() void 모든 요소를 제거 get..
프록시 패턴이란? 대상 객체에 접근할때 직접 접근하지 않고 대상 객체를 대행하는 객체를 통해 간접적으로 접근하는 방식이다. 프록시의 사전적인 의미는 대리인이라는 뜻이다. 즉, 대상 객체의 대리인을 통해 접근하는 패턴이라고 이해하면 될 것이다. 프록시 서버를 생각하면 해당 패턴의 특징을 이해할 수 있을 것이다. 더보기 프록시 서버란? 서버와 클라이언트 사이에서 클라이언트가 다른 네트워크 서비스에 간접적으로 접속할 수 있게 해주는 시스템이다. 이제 프록시 패턴을 어떻게 구현하는지 확인해보자 public interface ISubject { void action(); } public class RealSubject implements ISubject { @Override public void action() ..
