Computer Sci.

오늘 살펴볼 문제는 백준 1701 문제이다. https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고�� www.acmicpc.net 이 문제는 문자열 처리 관련된 유형으로 KMP 알고리즘을 사용하여 문제를 풀어야 시간 내에 맞힐 수 있다. ACM-ICPC 서울 리지널 기출문제이며, 난이도는 골드 2이다. 쉬운 문제는 아니지만 KMP 알고리즘에 대한 이해가 있다면 아이디어를 떠올리는데 도움을 받을 수 있을 것이다. 먼저 문제를 풀기 앞서서 K..

요즘에 실무에서 프론트엔드 개발을 하기 시작하면서, 과거에 혼자서 프로젝트를 할 때와 다른 점들이 몇 가지가 보이기 시작했다. 그 중에 하나가 디자인 패턴인데, 아직도 나는 디자인 패턴을 왜 써야 하고 또 잘 쓰려면 어떻게 써야 하는지에 대해서 잘 모른다. 그래서 주말에 조금씩 디자인 패턴을 공부해 보기로 했다. 교재는 이고 디자인 패턴 관련된 책 중에서 오랫동안 많은 사람들한테 읽혀진 책 중 하나이다. 책의 내용을 정리하면서, 최근에 추가되거나 수정된 내용들을 적절하게 업데이트 하는 식으로 공부 및 포스팅을 작성해 보려고 한다. 개발자들은 혼자서 프로젝트를 하는 경우보다 여럿이 함께 하는 경우가 훨씬 더 많다. 그리고 혼자 하더라도 그 사람이 처음부터 끝까지 프로젝트를 책임지고 한다는 보장은 없다. 그..

오늘 살펴볼 문제는 백준 1202번 문제이다. https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 이 문제는 전형적인 그리디 알고리즘 문제이다. 각각의 주머니에 대해서 넣을 수 있는 최대 가격의 보석을 적절하게 넣어주면 풀 수 있는 문제이다. 처음에 내가 했던 접근은 다음과 같다. 보석을 1. 가격이 비싼 순으로 2. 같은 가격이면 무게가 가벼운 순으로 정렬되는 PriortyQueue를 만든다. 그리고 가방을 무게 순으로 오름차순으로 정렬한..

이번에 살펴볼 문제는 백준 1507번 궁금한 민호 문제이다. https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 이 문제는 플로이드 와셜 알고리즘을 통해 모든 경로를 탐색하여 푸는 문제이다. 모든 쌍의 최단 경로를 다 확인하는 문제로 이 알고리즘이 익숙하지 않으면 조금 생각하기 어려울 수도 있다. 먼저 플로이드 와셜 알고리즘에 대해 간단하게 설명한 후에 문제를 풀어 보도록 하겠다. 플로이드 와셜 알고리즘(Floyd Warshall Algorit..

오늘은 백준 2352번 '반도체 설계' 문제를 보려고 한다. https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 난이도는 그렇게 어렵지 않았다.(골드 3) 이 문제는 LIS(최장 증가 수열)와 DP로 풀 수 있는 문제이다. 먼저 LIS에 대해서 간단하게 설명을 해 보려고 한다. LIS는 어떤 수열이 주어졌을 때 그 수열의 부분 수열 중에서 가장 길이가 긴 수열을 의미한다. 여러가지 방법으로 이 수열을 구할 수 있겠지만, 가장 일..

이번에 살펴볼 문제는 프로그래머스의 문제이다. https://programmers.co.kr/learn/courses/30/lessons/62049 코딩테스트 연습 - 종이접기 직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다. 먼저 오른쪽 절반을 왼쪽으로 접습니다. 다시 오른쪽 절반을 왼쪽�� programmers.co.kr 종이를 계속 반으로 접어서 안으로 파인 부분(∨)은 0, 밖으로 볼록 튀어나온 부분(∧)은 1로 순서대로 출력하면 되는 문제이다. 이 문제는 규칙성을 찾고 적절한 자료구조를 찾아서 탐색하면 그렇게 어렵지 않게 풀 수 있는 문제이다. 다만, 개인적으로 처음에 생각하기가 조금 쉽지 않았던 것 같다. 한 번 ..

이전 포스팅 Network #1. Intro 오늘은 IP 주소에 대해서 내용을 정리해보려고 한다. TCP/IP라는 프로토콜을 만들 때 이 프로토콜에서 사용하는 모든 장비들을 구분해 주기 위해서 만들어 낸 것이 IP 주소이다. 우리는 현재 IPv4라는 인터넷 프로토콜을 사용한다. 물론 오늘날에는 IPv6도 있지만, 아무래도 대중화된 프로토콜은 IPv4일 것이다. IPv4는 32 bit로 이루어진 숫자이며 총 네 구간으로 나누어져 있는데 각 구간은 8bit 이므로 0에서 255까지 숫자가 가능하다. 따라서 0.0.0.0 ~ 255.255.255.255까지 IP 주소로 사용할 수 있는 것이다. 산술적으로 보았을 때 2^32 = 약 40억 정도 되는데 실제로 전 세계에 존재하는 IP 주소는 그보다는 약간 적다...

오늘 살펴볼 문제는 백준 3176번 '도로 네트워크' 라는 문제이다. https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 문제 N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. 총 K www.acmicpc.net 이 문제는 꽤 어렵다. https://solved.ac/ 라는 알고리즘 문제 난이도 측정 사이트에서는 이 문제를 플레티넘 4 레벨로 분류했다. 플레티넘 레벨은 상당수가 쉽게 해결책을 찾기 어려운 고난이도 문제이다.(나에게는) 이 문제도 그래서 사실 풀다가 다른 사람의 소스를 어느 정도 참고하였고, 천천히 상세하게 풀이를 정리..