CPU 스케줄링이란 CPU 스케줄링은 운영체제가 CPU를 효율적으로 활용하기 위한 방법입니다. 이는 여러 프로세스들 중에서 어떤 프로세스를 먼저 실행할지, 얼마나 오랫동안 실행할지 등을 결정하는 일련의 과정을 말합니다. CPU 스케줄링은 시스템 성능을 높이고, 시스템 자원을 효율적으로 사용하여, 다양한 작업을 보다 빠르게 처리할 수 있도록 도와줍니다. CPU 스케줄링은 규모에 따라 장기, 중기, 단기 스케줄링으로 구분된다. CPU 스케줄링은 프로세스들의 우선순위와 요구사항에 따라 CPU 자원을 할당하는 방법입니다. 이러한 CPU 스케줄링 방법은 프로세스의 규모와 적용 시기에 따라 장기, 중기, 단기 스케줄링으로 구분됩니다. 장기 스케줄링: 시스템에 새로운 프로세스가 들어올 때, 어떤 프로세스를 메모리에 ..
플로이드 와샬이란 모든 최단 경로를 구하는 알고리즘이다. 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이라고 한다면, 플로이드-와샬은 한번 실행하여 모든 노드간 최단 경로를 구할 수 있는 것이다. 다익스트라 알고리즘이 가장 적은 비용을 하나씩 선택했다면 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있다. 플로이드 와샬 알고리즘의 과정 예시로 모든 노드간의 최단거리를 구해야하므로 2차원 인접 행렬을 구성한다. 알고리즘은 여러 라운드로 구성됩니다. 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복한다. 초기 그래프를 인접행렬로 나타내면 다음과 같습니다..
그리디 알고리즘이란 탐욕법 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해준다. 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그렇기에 많은 연습이 필요하다. 코딩테스트에서는 바로 문제의 유형을 파악하기 어렵다. 우선 그리디알고리즘을 의심하고, 문제를 해결할 수 있는 해결법이 존재하는지 고민한 이후에 해결방..
객체 지향 설계 원칙 SOLID라고 부르는 5가지의 설계 원칙이 존재한다. SRP(Single Responsibility Principle): 단일 책임 원칙 OCP(Open Closed Priciple): 개방 폐쇄 원칙 LSP(Listov Substitution Priciple): 리스코프 치환 원칙 ISP(Interface Segregation Principle): 인터페이스 분리 원칙 DIP(Dependency Inversion Principle): 의존 역전 원칙 앞 글자에 철자를 따서 SOLID라고 부르는데, 하나씩 정리를 해보자. SRP(Single Responsibility) - 단일 책임 원칙 어떤 클래스를 변경해야 하는 이유는 오직 하나뿐이어야 한다. 클래스는 단 한개의 책임을 가져야한..
디자인 패턴이란 디자인 패턴은 소프트웨어 디자인에서 일상적으로 발생하는 문제에 대한 일반적인 해결책을 말한다. 기존에 존재하는 함수나 라이브러리들로 패턴을 찾아서 프로그램에 복사한다고 하여 패턴이 되는 것은 아니다. 패턴은 특정 코드 족각이 아닌, 특정 문제를 해결하는 일반적인 개념이다. 패턴 세부 사항을 따라 자신의 프로그램에 맞는 솔루션을 구현할 수 있다. 디자인 패턴의 목적 SW의 재사용성과 호환성 그리고 유지 보수성을 보장하기 위함이다. 패턴의 구성 대부분의 패턴들은 사람들이 많은 맥락에서 재현할 수 있도록 형식적으로 설명된다. 패턴의 의도(Intent)는 문제와 해결책을 간략하게 설명한다. 동기(Motivation)는 패턴의 가능성과 문제를 더 설명한다. 클래스의 구조(Structure)는 패턴..
브루트 포스 알고리즘이란? 쉽게 말하면 모든 경우의 수를 무식하게 전부 다 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고 한다. 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다. 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다. 브루트 포스의 장단점 브루트 포스의 장점 알고리즘을 설계하고 구현하기 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 브루트 포스의 단점 알고리즘의 실행 시간이 매우 오래 걸린다. 메모리 효율면에서 매울..
Array (배열) 배열이란 같은 데이터 타입의 변수들로 이루어진 자료구조로, 자바에서 기본적으로 지원하는 자료 구조이다. 배열을 구성하는 각각의 값은 요수 혹은 원소(element)라고 부릅니다. 배열에서의 위치를 가리키는 숫자는 인덱스(Index)라고 부릅니다. 대부분의 언어에서 배열의 인데스는 0부터 시작하며, 자바에서도 0부터 시작한다. 대부분의 언어에서 배열의 인덱스는 0부터 시작하며, 자바에서도 0부터 시작한다. 참고로 파이썬의 경우 배열과 비슷한 list에서 리스트 맨 끝의 원소를 가리키는 인데스 -1도 존재하는데, Java에서는 배열의 인덱스는 0을 포함한 양의 정수만 가질 수 있다. 배열은 참조 객체이므로 배열을 가리키는 참조 변수는 스택영역에 할당되며, 이 참조 변수가 가리키고 있는 주..
Hash 란? 해시란 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것이다. 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array이다. 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 한다. 이때 사용하는 함수(알고리즘)를 해시함수라고 한다. 해시 값 자체를 index로 사용하기 때문에 평균 시간복잡도가 O(1)로 매우 빠르다. Hash 함수란? 위에서 설명한 것과 같이 키에 대한 해시값을 만드는 함수(알고리즘)이라고 한다. 계산이 복잡하지않고 키값에 대한 중복이 없고 해시값을 고르게 만들어 내는 함수가 좋은 함수이다. 특징 입력값이 일부만 변경되어도 전혀 다른 해시값을 출력한다...
