운영체제란 무엇인가?운영체제는 컴퓨터 프로그램이 하드웨어 자원을 이용할 수 있도록 하는 특수 소프트웨어 계층이다. 이는 컴퓨터 하드웨어와 사용자 응용 프로그램 사이에서 중개자 역할을 하며, 소프트웨어가 하드웨어와 일관되고 효율적으로 상호 작용할 수 있도록 한다. 운영 체제는 메모리 관리, 입력 및 출력 장치 처리와 같은 물리적인 인터페이스와 이를 추상화한 소프트웨어적인 인터페이스를 제공한다. 인기있는 운영 체제의 예로는 Windows, macOS, Linux 및 Android가 있다. 컴퓨터 게임을 하는 상황을 가정해보자. 키보드와 마우스를 통해 게임 캐릭터를 움직여주고 화면을 통해 출력되는 게임 화면을 본다. 내부적으로는 메모리에 게임 데이터가 적재된다. 게임을 플레이하다 저장 버튼을 누르면 디스크에 ..
C# Nullable 타입 소프트웨어 개발 세계에서 null 참조는 꽤나 골치아픈 문제로, 개발자들 사이에서 악명 높은 "NullReferenceException"으로 이어질 수 있다. 지속적으로 발전하고 있는 C# 언어는 이러한 문제를 해결하기 위해 안전성과 개발자의 생산성을 향상시키는 강력한 기능들을 도입하고 있다. C#의 최신 버전에서 주목할 만한 발전 중 하나는 nullability 기능의 도입 및 강화이다. 이번에는 C#에서 nullability의 중요성을 다루며, 코드 안전성과 명확성을 어떻게 향상시키는지 실용적인 예시와 함께 살펴본다. Nullable을 활용해 Non-Nullable 타입을 Nullable로 만들기 C#에서 타입 시스템은 변수가 null 값을 가질 수 있는지를 구분하는 데 큰..
C# 불변성 처리 소프트웨어 개발이 발전하는 과정 속에서, 불변성의 원칙은 견고하고 thread-safe한 애플리케이션을 만드는 기초로 자리잡았다. 불변성은 객체가 생성된 후 변경되지 않는 능력을 의미한다. 이 개념은 비록 간단해 보일지라도, 특히 동시성과 멀티 스레드 프로그래밍의 영역에서 많은 이점을 가져다 준다. 이 글에서는 불변성을 위한 C#의 새로운 기능들, 그리고 readonly 및 const와 같은 다른 C# 구문과의 차이점을 알아볼 것이다. 불변성의 장점 불변성의 주된 매력은 그 단순성과 예측 가능성에 있다. 한 번 초기화되면, 불변 객체는 그 상태가 변경되지 않을 것이라는 보장을 제공하여, 특히 여러 스레드가 동시에 데이터에 접근하는 환경에서 상태 관리와 관련된 다양한 버그의 가능성을 없앤..
C# 비동기 프로그래밍 C#의 async와 await 키워드는 비동기 작업을 다루는 과정을 간소화하여 비동기 코드를 더 읽기 쉽고 유지보수하기 쉽게 만드는 데 사용된다. 비동기 프로그래밍은 시간이 많이 걸리는 작업(예: I/O 작업, 웹 요청, 데이터베이스 트랜잭션 등)을 메인 스레드를 차단하지 않고 실행할 수 있게 해주므로, 사용자 인터페이스의 반응성을 유지하고 서버 측 응용 프로그램의 확장성을 향상시키는 데 필수적이다. async와 await async 키워드는 메소드, 람다 표현식 또는 익명 메소드를 비동기적으로 표시하는 데 사용된다. async 메소드는 호출자의 스레드를 차단하지 않고 잠재적으로 오래 걸리는 작업을 수행하는 편리한 방법을 제공한다. async 메소드는 await 표현식에 도달할 때..
힙 (Heap) 힙(Heap)은 완전 이진트리인 특별한 트리를 기반으로 한 자료구조이다. 힙에는 최대힙과 최소힙이 있는데, 최대힙은 최대값을 다루는데 특화되어 있고 최소힙은 최소값을 다루는데 특화되어 있다. 각 힙은 일련의 원소들이 주어졌을 때 최대 or 최소 원소를 빠르게 조회, 삭제할 수 있다. 또한 각 힙 모두 임의의 원소를 빠르게 삽입할 수 있다. 최대, 최소 원소를 다루는 특수적인 상황에 있어 효율적이고, 의외로 최대 최소 원소를 활용해야 하는 상황이 많이 발생하기 때문에 굉장히 중요한 자료구조에 속한다. (우선순위큐도 힙으로 제작된다.) 힙에서 제공하는 연산들을 배열과 비교해보자. 값 삽입 배열 : O(1) 힙 : O(log N) 최대값 or 최소값 삭제 배열 : O(N) 힙 : O(logN)..
Multithreading에 대해 컴퓨터에는 CPU라는 연산 장치가 존재한다. CPU의 코어에서는 명령 집합들을 빠른 속도로 처리하는데 이 처리되는 단위를 Thread라 부른다. 현대의 CPU는 여러 개의 코어들로 구성되어 있고, 여러 스레드가 동시에 여러 명령 집합들을 수행할 수 있다. 여러 개의 스레드를 동시에 사용한다면, 하나의 스레드만 사용하는 것보다 훨씬 CPU를 효율적으로 활용할 수 있다. 이처럼 두 개 이상의 스레드를 통해 동시에 실행하는 것을 멀티스레딩이라 부른다. 스레드에 대해 자주 혼동하는 것 중 하나가 있다. 처리되는 단위를 스레드라 부르는데, 이것이 스레드를 코어 개수만큼만 생성해야 한다는 의미는 아니다. 스레드는 1000개 10000개까지도 생성시킬 수 있다. 다만, 코어의 개수가..
Partial Class란? C#에서 Partial Class는 단일 클래스를 여러 소스 코드 파일에 나눠서 정의할 수 있는 기능이다. Partial Class의 각 부분은 동일한 클래스 정의에 기여하며 컴파일러는 컴파일 중에 해당 부분을 단일 클래스로 병합한다. Partial 클래스는 주로 구현 세부 사항을 분리하고 코드베이스를 보다 체계적이고 유지 관리하기 쉽게 유지하는 데 사용된다. 특히 코드 생성 도구나 여러 개발자가 관련된 시나리오에서 더욱 그렇다. 코드 생성 부분 클래스는 일반적으로 코드 생성 도구(예: Entity Framework)와 함께 사용되어 자동 생성 코드를 사용자 지정 코드와 분리한다. 이러한 분리를 통해 개발자는 생성된 코드에 영향을 주지 않고 사용자 지정 코드를 수정할 수 있다..
인터페이스란? Java나 C#과 같은 언어들을 보면 Interface라는 강력한 개념이 존재한다. 인터페이스는 객체에 대한 명세서만 나타내고 구체적인 구현은 각 파생 객체에서 작업하도록 한다. 명세서에는 메서드, 프로퍼티, 이벤트와 같은 것들이 포함될 수 있다. 겉으로만 보면 별로 대단할 것 없어 보이는 개념이지만, 인터페이스를 잘 활용한다면 객체지향 개발에 있어서 신세계를 경험할 수 있다. C++을 이용한 인터페이스 구현 C++은 언어 차원에서 인터페이스를 명시적으로 지원하지는 않는다. 하지만 C++ 자체에서 갖고 있는 개념인 추상 클래스와 순수 가상함수를 조합하여 인터페이스를 구현할 수 있다. class IPrintable { public: virtual void Print() = 0; // Pure..
C++ Casting C++에는 여러가지 캐스팅 방법들이 존재한다. C Style Casting C에서 계승받은 전통적인 캐스팅 방법으로 여러 캐스팅 작업을 복합적으로 사용한다. 편리할 수 있지만 덜 명확하고 예상치 못한 동작이 발생할 수 있다. 잠재적인 문제를 숨길 수 있으므로 최신 C++ 코드에서는 권장되지 않는다. double numDouble = (double)42; 최신 C++에서는 가능하면 static_cast, dynamic_cast, const_cast와 같은 보다 구체적인 형변환 연산자를 사용하는 것이 일반적으로 권장된다. 이러한 연산자는 더 나은 유형 안전성을 제공하고 코드를 보다 명확하게 구분할 수 있도록 해주기 때문이다. 그러나 하위 수준 작업에 reinterpret_cast를 사용..
그래프 간선의 분류 그래프의 구조와 특성을 파악하려면 어떤 방법을 이용해야 할까? 깊이우선탐색(DFS)은 그래프의 구조를 파악하는데 사용될 수 있다. 깊이우선탐색을 수행하면 그 과정에서 그래프의 모든 간선을 한번씩은 만나게 된다. 그중 일부 간선은 처음 발견한 정점으로 연결되어 있어서 우리가 따라갈 테고, 나머지는 무시하게 될 것이다. 하지만 이 간선들을 무시하지 않고 이들에 대한 정보를 수집하면 그래프의 구조에 대해 많은 것들을 알 수 있다. 어떤 그래프를 깊이 우선 탐색했을 때 탐색되는 간선들만 모아 보면 트리 형태를 띄게 된다. 예를들어 다음 왼쪽 그림에 있는 그래프를 0번 정점을 기준으로 깊이우선탐색을 했을 때, 오른쪽 그림의 굵은 검정색 간선들처럼 탐색이 될 것이다. 이처럼 깊이우선탐색으로 탐색..
백트래킹 백트래킹(Backtracking)은 컴퓨터 계산 문제, 특히 제약 충족 문제(Constraint Satisfaction Problem)에 대한 해결방법을 찾기 위한 일반적인 알고리즘으로, 솔루션에 대한 후보를 점진적으로 구축하고 후보가 유효하지 않다면 해당 후보를 포기하고 퇴각하여 이전 단계부터 다른 선택을 해나가는 방식으로 동작한다. 다음 문제들을 보자. 스도쿠 스도쿠는 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분된 3 x ..
유향 비순환 그래프 유향 비순환 그래프(Directed Acyclic Graph, DAG)는 수학, 컴퓨터 과학 분야의 용어의 하나로서 사이클이 없는 유향 그래프이다. 즉, 각 간선은 하나의 꼭짓점에서 다른 꼭짓점으로 방향을 잇는데 이처럼 어떠한 꼭짓점 v에서 시작하여 끝내 다시 v로 돌아가 순환 반복되는 일정한 방향의 일련한 간선을 따라가는 방법이 없는 그래프를 의미한다. 또한 사이클이 없는 방향그래프라는 정의를 통해 모든 트리는 DAG임을 알 수 있다. (어떤 그래프가 주어졌을 때 이 그래프가 DAG인지 판단하기 위해서는 사이클의 존재여부를 확인하면 된다.) 위상 정렬 위상 정렬(Topological Sort)은 모든 방향 모서리 u v에 대해 정점 u가 순서에서 v 앞에 오도록 정점들을 정렬하는 알..
최단 경로 최단 경로란 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제로, 그래프의 응용문제 가운데 가장 유용하고 널리 사용된다. 가중치가 없는 그래프에 대한 최단 경로는 너비 우선 탐색(Breadth First Search)을 통해 구할 수 있지만, 가중치가 있는 그래프에 대해서는 좀 더 복잡한 방법이 필요하다. 음수 사이클 최단 경로 문제를 해결하기 위해 가장 유의해야 하는 부분은 음수 가중치를 갖는 간선이 있는지다. 음수 간선이 존재하는 그래프에서 해당 간선을 지나가면 전체 경로의 길이가 짧아지게 된다. 이러한 특성에 더해 만약 가중치에 합이 음수인 사이클이 그래프에 존재한다면, 최단 경로의 길이는 음의 무한대까지 발산하게 된다. 그러므로 음수 사이클이 있는 그래프에서는 어..
오일러 경로 오일러 경로(Eulerian Trail)은 그래프에 존재하는 모든 간선을 정확히 한 번씩 방문하는 연속된 경로를 의미한다. 시작점을 어느 지점으로 하느냐에 따라 몇몇의 간선에 도달하지 못할수도 있다. 오일러 회로 오일러 회로(Eulerian Circuit)은 시작점과 끝점이 같은 오일러 경로를 의미한다. 다음과 같이 그래프가 오일러 회로를 갖지 않는 경우도 존재한다. 일반적으로 오일러 경로가 없는 경우거나 오일러 경로가 존재하지만, 시작과 끝점이 다른 경우이다. 오일러 경로는 오일러 회로일 수도 있지만, 시작 정점과 끝 정점이 다른 경우도 포함하므로 오일러 회로가 아닐 수도 있다. 오일러 회로를 이용한다면 정해진 단어 집합에서 모든 단어를 끝말잇기로 연결하는 예제나 가진 항공권을 모두 이용하..
부분합 다음과 같은 수열이 있다. v = {2, 3, 7, 5} 이 수열에서 구간 [1, 3]의 합은 3 + 7 + 5 = 15 이다. 이처럼 어떤 임의의 구간 [i, j]가 주어졌을 때, 구간의 합을 구하기 위해서는 해당 구간을 순회하며 값을 더하면 될 것이다. 하지만 만약 수열의 크기 N이 크고 이런 구간에 대한 질의 개수 Q도 많아진다면 어떻게 될까? 위와 같은 방식으로는 최악의 경우 O(N x Q) 의 시간복잡도를 갖게 될 것이다. 이러한 문제를 해결하기 위해 고안된 방법으로 부분합(Partial Sum or Prefix Sum)이 있다. 부분합은 배열 원소의 인덱스까지의 합으로 다음과 같이 정의된다. psum[i] = ∑ v[k] (0
그래프 그래프는 트리보다도 훨씬 더 일반적이고 강력한 자료구조로, 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현하기 위해 사용된다. 사람들 간의 관계, 도로와 도시들 사이의 관계, 네트워크로 연결된 컴퓨터들의 관계와 같은 것들을 연결 구조의 예로 들 수 있을 것이다. 그래프는 이러한 다양한 관계에 대해 표현할 수 있고, 현실세계의 문제를 그래프로 매핑시킨 후에는 여러 그래프 알고리즘들을 이용하여 그 문제들을 해결할 수 있다. 그래프는 객체들을 대응시키기 위한 개념인 정점(Vertex) 집합과, 관계들을 대응시키기 위한 개념인 간선(Edge) 집합 G(V, E)의 형태로 정의한다. 일반적으로 정점 집합은 각 정점에 대응되는 번호로 나타내고, 간선 집합은 정점번호 쌍의 집합으로 나타낸다. V =..
구간트리 구간 트리는 일차원 배열의 특정 구간에 대한 질의를 빠르게 대답하는데 사용된다. 예를 들어 어떤 숫자들이 주어진다고 가정해보자. S = {1, 2, 1, 2, 3, 1, 4, 2, 2} 이 숫자들에 특정 구간에 대한 질의가 들어온다고 생각해보자. 예를들면 [2, 4] 구간의 최소값은 1이고, [6, 8]구간의 최소값은 2이다. 물론 이 처리를 위해 순회를 하며 최소값을 찾을 수 있다. 하지만 이 방법은 O(N)의 수행시간을 갖는다. 만약 이러한 질의가 무수히 많이 들어온다면 어떨까? 기존의 방법대로라면 쿼리의 개수가 Q라고 했을 때, O(Q x N)의 수행시간을 갖게 될 것이다. 하지만 구간트리는 하나의 쿼리를 O(logN) 시간에 수행할 수 있고, 모든 쿼리에 대해서는 O(QlogN) 시간에 ..
트라이 (Trie) 문자열을 다루는 작업은 정수나 실수를 다르는 것과는 다르다. 정수나 실수는 고정된 크기만큼의 메모리만 이용하지만, 문자열의 경우에는 그 크기가 정해져 있지 않다. 그러므로 최악의 경우 문자열 길이에 비례하는만큼 시간을 소모하게 된다. 그렇기 때문에, 정수나 실수와 같은 타입에 대해서는 훌륭하게 동작하는 이진트리나 해시테이블 같은 자료구조도, 문자열을 저장하는데에 있어서는 취약하다. 이진트리에 일반적인 정수 타입을 검색, 삽입, 삭제 하는데에는 O(logN)의 시간이 걸린다. 하지만 이진트리에 길이 M의 문자열을 N개 저장한다고 했을 때, 이 문자열 타입에 대한 연산은 O(MlogN)이 걸린다. 즉, 문자열이 길어지게 되면 이진트리의 장점도 무용지물이 된다는 의미이다. 해시테이블도 마찬..
동적계획법 동적 계획법은 수학 이론에서 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 동적 계획법의 원리는 매우 간단하다. 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 부분 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다. 분할정복 vs 동적계획법 (부분문제의 중복) 전..
재귀 함수 컴퓨터가 수행하는 대부분의 작업들은 좀 더 작은 단위의 작업들로 나누어 볼 수 있다. 예를 들어 온라인으로 상품을 구매하는 작업은, 상품 정보 조회하기, 구매자 정보 조회하기, 구매자-상품 결제 처리하기, 데이터베이스 갱신하기, 문자 보내기 와 같은 더 작은 단위의 작업들로 나누어진다. 또 그 중에서 상품 정보 조회하기와 같은 작업은, 자료구조에 따라 다르겠지만, 상품 정보를 비교하는 작업을 반복적으로 수행하여 정보를 찾게 된다. 이렇게 어떤 작업들을 더 작은 작업들로 표현할 수 있는데, 이 범위가 작아지면 작아질수록 작업의 형태가 유사해지게 된다. 이런 상황을 코드로 구현할 때 유용하게 사용되는 개념이 바로 재귀 함수이다. 재귀적 정의 재귀 함수란 수행해야하는 목표 작업을 유사한 형태의 조각..
분할 정복 분할 정복(Divide ans Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로 큰 문제를 작은 문제로 분할하여 해결하는 전략이다. 이 전략을 활용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나누고 각 문제에 대한 답을 재귀 함수를 이용하여 계산한다. 그 후 부분 문제의 답을 이용하여 전체 문제의 답을 계산해낸다. 분할정복 전략이 일반적인 재귀함수와 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눈다는 것이다. 그렇다면 분할정복이 필요한 이유는 무엇일까? 분할 정복을 활용하면, 선형적인 방법보다 빠르게 문제를 해결할수도 있기 때문이다. 다음 예제를 보자. 어떤 수 N과 P가 주어졌을 때, N의 P승을 구하는 알고리즘을 작성하라. 일반적..
상태 공간 탐색 상태 공간 탐색은 인공지능을 포함한 컴퓨터공학에서 사용되는 전략으로 문제에서 정의될 수 있는 모든 상황을 상태로 정의한다. 그 후 각각의 상태에서 수행할 수 있는 모든 선택을 행동으로 정의하여 원하는 속성을 갖는 목표 상태에 도달하기까지 여러 가지 전략으로 행동들을 선택해나가는 탐색 과정이다. 일반적으로 가능한 해 중 가장 최적의 해를 찾는 형태인 최적화 문제(Optimization Problem)를 해결하기 위해 많이 사용된다. 문제는 굉장히 다양한 방법으로 정의될 수 있지만, 탐색 과정 중에 얻는 정보들을 적절하게 이용하여 각 문제를 해결할 수 있다. 먼저 틱택토(Tic-Tac-Toe) 게임을 예로 들어보자. 틱택토는 두 명이 번갈아 가며 O와 X를 3 x 3 게임판에 놓아서 같은 글..
시뮬레이션, 구현 시뮬레이션 및 구현 문제는 문제에서 제시한 상황을 알고리즘으로 수행해내도록 구현하는 문제이다. 일반적으로 게임 상황을 재현하는 문제들이 자주 등장한다. 예를들면 다음과 같은 문제들이다. https://programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 이런 형태의 문제들은 딱히 대단한 전략을 갖고있어야 하는것은 아니지만, 분석해야하는 요구사항이나, 구현해야하는 코드량과 예외처리들이 많기..
완전탐색 완전탐색 알고리즘은 문제는 해결하는 전략 중 하나로, 가능한 모든 경우의 수를 다 찾고, 그 중에서 답을 고르는 전략이다. 하지만, 가능한 모든 경우의 수를 다 나열해 보는것은 생각보다 어려운 일이다. 우리가 수학에서 배우는 단순한 경우의 수를 예로 들어보자. 1~4 까지의 숫자가 적힌 공들 중 임의의 두 공을 고르는 모든 경우의 수는 총 6가지이다. (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) 수학적으로는 조합이라는 개념으로 이를 표현한다. Combination(4, 2) = 6 이렇게 단순하게 모든 경우의수를 생각해낼 수 있는 문제도 물론 존재한다. 하지만 다음과 같은 문제는 어떨까? Queen은 가로, 세로, 양쪽 대각선 모두 공격이 가능하다. 8 x..
