문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/81302?language=cpp 카카오 기출문제 중 Level 2 난이도, 그림만 많지 문제를 이해하기에는 어렵지 않다. X는 칸막이로 치고, 그냥 5x5 맵에 P와 P 사이에 맨해튼 거리를 계산하면 된다. 문제 핵심 및 풀이 키포인트는 5 x 5 맵이 5개 있다는 점. 탐색 범위가 작아 완전 탐색이든 뭐든 시간적인 제약은 없다. 또한 핵심 아이디어는 이 문제가 그래프 탐색을 할 수 있다는 것. 그중에서 편한 방법은 BFS인데, 왜냐하면 BFS를 통해 최단거리를 쉽게 구할 수 있기 때문이다. 이 문제를 왜 BFS로 풀 수 있을까? 맨해튼 거리를 계산하는 것이기 때문이다. 두 점 A와 B의 ..

네트워크 애플리케이션 개발의 중심 다른 종단 시스템에서 동작하고 네트워크를 통해 서로 통신하는 프로그램을 작성하는 것 예시 웹 어플레케이션의 서버와 클라이언트로 구별되는 두 가지 프로그램 클라이언트 프로그램 : 사용자 호스트에서 실행되는 브라우저 프로그램 사용자 호스트 → 데스크톱, 랩톱, 태블릿, 스마트폰 서버 프로그램 : 웹 서버 호스트에서 실행되는 웹 서버 프로그램 이러한 서버는 종종 데이터 센터에 위치 종단 시스템에만 애플리케이션 소프트웨어가 존재 → 기본 설계 방식 새로운 애플리케이션 개발 여러 종단 시스템에서 실행되는 소프트웨어를 작성해야 함 C, Java, Python 등으로 작성됨 네트워크 코어 장비에서 실행되는 소프트웨어까지 작성할 필요가 없다. 네트워크 코어 장비는 네트워크 계층 및 그..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/72412?language=cpp 카카오 코딩테스트에 나온 문제. 문제 이해 자체는 어렵지 않다. 문제 핵심 및 풀이 1. 효율성 검사도 하기 때문에 시간복잡도가 중요하다. info의 크기가 50,000까지이고, query의 크기는 100,000까지이다. 이를 O(N)으로 계산한다고 했을 때, 5* 10^5 * 10^4 = 5억 정도라서 O(N)으로 탐색하기에는 아슬아슬하다. 그래서 최적화를 해야 하는 문제이다. 실제로 O(N)으로 푸니까 시간초과가 나온다. O(N)으로 풀었을 때의 시간 복잡도가 얼마인지 모르겠긴 하다. 2. 문자열 분리 해당 문제에서 info는 띄어쓰기를 통해 구분되어 있..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/92342? 카카오 코딩테스트로 나오면 문제인데, 자주 풀어보긴 해야겠다. 문제 핵심 및 풀이 해당 문제의 유형은 제한사항을 보면 알 수 있다. 최대 10발까지 가능하고, 점수도 11개가 끝이다. 충분히 완전탐색으로 풀 수 있는 문제다. 라이언 점수 경우의 수 완전 탐색으로 풀면 되기 때문에, 백트래킹을 떠올렸다. n개의 화살을 11개의 점수에 각각 넣어보면 된다. 여기서 중요한 것은 맞추는 순서는 상관없다는 것이다. 어차피 해당 점수에 맞은 화살 개수만을 따지기 때문에 백트래킹할 때 중복 조합으로 구현해 주면 된다. 점수 계산 점수를 구하는 방법은 간단하다. 모든 점수를 확인해 주면서 어피..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/60062# 카카오 코딩 테스트에 나왔던 문제다. 확실히 문제 이해하기도 복잡하다. 문제 핵심 및 풀이 유형 유추 제한 조건에 보면 외벽의 최대 길이(n)는 200까지이다. 인원을 배치할 수 있는 경우의 수는 200가지이다. 인원은 최대 8명까지 가능하다. 그리고 결함이 있는 외벽도 15개까지밖에 주어지지 않는다. 계산에 필요한 인원, 외벽, 최대 길이가 굉장히 짧다. O(n^2)을 하더라도 충분하고 O(n^3)도 가능하다. 그래서 완전 탐색이 사용가능하다고 생각했다. 어떻게 하면 외벽 점검을 최소의 인원만 사용할 수 있을까 해당 문제에서 키워드는 외벽이 원형 모양이라는 것이다. 이 말은 외..

식사하는 철학자들(The Dining-Philosophers) 문제 규칙 가정 5명의 철학자가 원형 테이블을 공유하는 상황 테이블 중앙에는 밥이 있고, 테이블에는 5개의 젓가락이 존재 철학자가 생각(행동) 할 때, 다른 동료들과 상호작용하지 않음 밥을 먹을 때의 규칙 자신에게 가장 가까이 있는 2개의 젓가락을 집으려고 시도 옆 사람이 들고 있는 젓가락은 집을 수 없다. 가까이 있는 2개의 젓가락 → 자신과 자신의 왼쪽 철학자, 그리고 오른쪽 철학자 사이에 있는 젓가락을 뜻함 철학자는 한 번에 한 개의 젓가락만 집을 수 있음 배고픈 철학자가 동시에 젓가락 2개를 집는 경우 젓가락을 놓지 않고 식사를 한다. 식사를 마치면 2개의 젓가락 모두 내려놓고 다시 대기한다. 식사하는 철학자 문제의 의의 고전적인 동기..

고전적인 동기화 문제 많은 클래스의 병행 제어(concurrency control) 문제에 대한 것 해당 문제들로 새로운 동기화 방법을 검증할 수 있음 유한 버퍼 문제(The Bounded-Buffer Problem) 해당 문제는 동기화 프리미티브(primitive)들의 능력을 설명하기 위해 사용 프리미티브 : 프로그래밍 관점에서 해석 이용 가능한 가장 작은 processing의 단위 언어에서 표현의 원자 요소 예 : 덧셈, 뺄셈 → 가장 단순하기 때문에 primitive operation라고 함 소비자와 생산자가 공유하는 자료구조 int n; // n개의 버퍼로 구성된 풀(pool) semaphore mutex = 1; // 상호배제 기능 제공 semaphore emtpy = n; // 비어 있는 버퍼..

인터넷이란 무엇인가? 2가지 방법이 존재 인터넷의 구성요소를 기술하는 것 인터넷을 구성하는 기본적인 하드웨어와 소프트웨어 구성요소 기술 분산 애플리케이션에서 서비스를 제공하는 네트워킹 인프라스트럭처 관점에서 서술 인프라스터럭처(infrastructure) 컴퓨터와 사용자들을 연결하는 데 사용되는 물리적인 하드웨어를 말한다. ← 정보 기술과 인터넷의 관점으로 본 인프라스럭처 줄여서 “인프라”라고 많이 부름 구성요소로 본 인터넷 중요한 3가지 키워드 인터넷(network of networks) : 네트워크들이 모인 네트워크 프로토콜(protocol) : 네트워크에서 메시지 송수신을 제어하는 일련의 규칙 표준화(Internet standards) : 네트워크는 표준화가 굉장히 중요 종단 시스템(end Syst..