들어가며 배낭 문제(Knapsack Problem)는 조합 최적화 문제의 기본적인 문제 유형으로 동적 계획법(DP)을 이용해 풀 수 있습니다. 코딩 테스트에서 배낭 문제 혹은 냅색이라고 하면 바로 이 유형이구나 생각하면 됩니다. 배낭 문제의 핵심은 각각 가중치(Weight)와 가치(Value)를 가진 집합이 주어졌을 때, 총 가중치의 한계 내에서 유지하면서 총 가치가 가장 커질 수 있도록 어떤 원소를 포함시킬 것인지 결정하는 것 입니다. 쉽게 말해 10kg 용량 배낭에 [5kg, 5만원, 신발], [6kg, 4만원, 패딩], [4kg, 3만원, 속옷]이 있을 때 어떤 것들을 가져가야 용량에 넘치지 않으면서 최대 가치를 챙길 수 있는지 찾는 것입니다. 위 예시에서는 신발과 속옷을 챙기는 것이 8만원으로

들어가며 Candy Splitting (Large) 솔브드에서 제공하는 랜덤 마라톤에서 나온 문제입니다. XOR 연산에 대한 이해가 있어야 풀 수 있는 문제였습니다. 문제설명 형제 Sean과 Patrick은 부모님으로부터 캔디가 든 가방을 받았습니다. 가방 안에는 값이 다른 여러 개의 캔디가 들어있는데, 이를 공정한 방법으로 나누려고 합니다. Sean이 두 더미로 나누면 Patrick이 둘 중 하나를 골라 가져가는 방식이죠. 불행하게도 Patrick은 너무 어려서 캔디의 값을 올바르게 더하는 방법을 모릅니다. 대신 이진법 덧셈을 거의 할 줄 아는데, 올림을 까먹었습니다. 예를 들어, 12(1100), 5(101)이 있을 때 올바른 덧셈 결과는 17(10001)이지만, Patrick의 방식으로는 9(1001)

들어가며 몇 번의 프로젝트에서 인프라를 맡아 리눅스를 어느 정도 다룰 줄은 알지만 체계적으로 공부해본 적이 없습니다. 이번 기회에 리눅스 개발 코드도 뜯어보면서 심도 깊게 이해해보겠습니다. 리눅스에 대해서 공부하기 전에 리눅스는 운영체제의 일종이므로 운영체제에 대해서 먼저 이해해야 합니다. 이번 글에서는 운영체제가 무엇인지 간단하게 공부하고, 리눅스를 입문해봅시다. 운영체제 개요 운영체제란? 운영체제의 정의 운영체제(Operating System; OS)는 컴퓨터의 CPU, 메모리와 같은 하드웨어 자원을 효율적으로 관리하는 시스템 소프트웨어입니다. 또한 응용 프로그램이 동작할 수 있는 환경을 제공하고, 사용자와 하드웨어 간의 상호작용을 위해 사용자 인터페이스 를 제공하는 역할을 하기도 합니다. 운영체제의

노션으로 쓴 포스트가 내 블로그에 자동으로 올라갈 수 있을까? 개발자가 되기로 결심하고 티스토리 블로그 를 운영한 지 2년이 지났어요. 포스트를 작성하기에 불편함이 거의 없고, SEO최적화 측면에서 거의 손대지 않아도 되는 등 많은 이점이 있었습니다. 또, 멋진 개발자 분들을 구독하면 그분들의 새로운 포스트도 볼 수 있었죠. 그러나 삼성 청년 SW 아카데미를 졸업하고 취업 준비를 하면서 한 가지 생각이 들었습니다. “개발자라면 나만의 기술 블로그를 가져야 하지 않을까?” 이 질문을 계기로 나는 어떤 개발자가 되고 싶은지에 대해 고민하기 시작했어요. 단순히 코드만 잘 짜는 개발자가 아니라, 지식과 경험을 기록하고 , 생각을 공유하며 , 더 나아가 끊임없이 성장할 수 있는 개발자가 되고 싶었습니다.

외판원 문제란? 외판원 문제(Traveling Salesman Problem; TSP)는 컴퓨터 과학 및 수학 분야에서 잘 알려진 조합 최적화 문제입니다. 이 문제의 핵심은 주어진 각 도시(노드)를 정확히 한 번만 방문하고 시작 도시로 돌아가는 가능한 최단 경로를 찾는 것 입니다. 이때, A도시에서 B도시로 가는 거리(d)는 가중치가 존재합니다. 문제의 경우에 따라서 시작점으로 돌아가지 않을 수도 있는데, 이 제약 조건이 없다고 해도 계산 복잡도는 변하지 않습니다. 어쨌든 TSP는 대표적인 NP-난해(NP-hard) 문제로 모든 문제에 대해서 다항식 시간에 해결할 수 있는 알려진 알고리즘은 없습니다. 대신 작은 N의 경우(일반적으로 N ≤ 16) 에는 분기한정법(Branch and Bound; B&B

들어가며 알고리즘 문제를 풀다보면 boolean집합을 공간적으로 압축하기 위해 비트마스킹을 사용할 때가 종종 있습니다. [True, False, False, True, True, False, True, False]와 같은 배열을 10011010₂와 같이 표현하면 정수 하나로 표현 가능하기 때문이죠. 문제 중에는 정수의 특정 비트가 0인지 1인지 확인 해야 하거나 1의 개수를 세어야 할 경우 도 있습니다. 전자의 경우, 즉 특정 비트의 ON/OFF를 판단해야 하는 문제라면, ((임의의 정수) & (1 << n)) > 0와 같이 간단히 구할 수 있습니다. 오른쪽에서 n번째 비트가 1인 정수를 생성하고 임의의 정수와 AND 비트 연산을 하면, 다음과 같이 해당 비트가 1이라면 2^n, 아니라면 0을 결과로 산

삼성 청년 SW아카데미(이하 ‘싸피’) 마지막 프로젝트였던 파이프워치 프로젝트입니다. 프로젝트에서 인프라를 맡아 자율 1위, 전국 결선 3위에 올랐었던 경험을 바탕으로 포스트를 써내려 가겠습니다. 왜 하게 됐을까? 싸피에서는 2학기 때 세 번의 프로젝트를 합니다. 각각 공통 프로젝트, 특화 프로젝트, 그리고 자율 프로젝트입니다. 각 프로젝트마다 주제가 다르지만 어쨌거나 지난 두 번의 프로젝트에서는 SpringBoot와 React를 다루면서 백엔드와 프론트엔드 전반을 맡아서 수행했습니다. 하지만 아쉽게 수상하지는 못했습니다. 마지막 팀은 스마트 팩토리에 관심을 갖고 있는 사람들이 모여서 만들어진 팀이었습니다. 싸피에서는 마지막 프로젝트인 자율 프로젝트를 하기 전에 기업 연계 프로젝트를 지원할 수 있는데요. 기

LAN을 넘어서는 네트워크 계층 LAN을 넘어서 다른 네트워크와 통신하기 위해서는 네트워크 계층이 필요합니다. 네트워크 계층에서는 IP 주소를 이용해 송수신지 대상을 지정하고, 다른 네트워크에 이르는 경로를 결정하는 라우팅을 통해 다른 네트워크와 통신합니다. 물리 계층과 데이터 링크 계층만으로는 다른 네트워크까지의 도달 경로를 파악하기 어렵습니다. 다른 네트워크와 빠르게 통신하기 위해 패킷이 이동한 최적의 경로를 결정하는 것을 라우팅(Routing) 이라고 하며, 네트워크 계층의 장비 중 라우팅을 수행하는 대표적인 장비가 라우터(Router) 입니다. 인터넷 프로토콜(Internet Protocol; IP) 네트워크 계층의 가장 핵심적인 프로토콜은 인터넷 프로토콜입니다. IP에는 IPv4 , IPv6

운영체제란 무엇인가? 운영체제 (Operating System, OS) 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층 커널 운영체제의 핵심 부분으로 메모리에 상주하는 부분 좁은 의미의 운영체제 : 커널 넓은 의미의 운영체제 : 커널 + 각종 주변 시스템 운영체제의 목적 컴퓨터 시스템의 자원을 효율적으로 관리 컴퓨터 시스템을 편리하게 사용할 수 있는 환경 을 제공 운영체제의 분류 동시 작업 가능 여부 단일 작업(Single Tasking) - 한 번에 하나의 작업만 처리 다중 작업(Multi Tasking) - 동시에 두 개 이상의 작업을 처리 사용자의 수 단일 사용자(Single User) 다중 사용자(Multi User) 처리 방식 일괄 처리(

컴퓨터 네트워크를 알아야 하는 이유 컴퓨터 네트워크는 우리 일상을 지탱하는 주요 기반 기술입니다. 컴퓨터 네트워크 줄여서 네트워크 란 여러 개의 장치가 마치 그물처럼 서로 연결되어 정보를 주고 받을 수 있는 통신망 입니다. 인터넷(Internet) 네트워크를 통해 주변의 장치와 정보를 주고받는 것을 넘어서 네트워크와 연결된 지구 반대편의 다른 장치와도 정보를 주고 받을 수 있도록 하는 기술을 인터넷 이라고 합니다. 즉 여러 네트워크를 연결한 ‘네트워크의 네트워크’ 를 인터넷이라고 합니다. 네트워크 거시적으로 살펴보기 네트워크는 거시적으로 그래프의 형태를 띠고 있습니다. 그래프(Graph)란 노드(Node)와 노드를 연결하는 간선(Edge)로 이루어진 자료구조입니다. 네트워크의 기본 구조 모든 네트워크