Computer Sci.

지금까지 백준만 풀다가 올해 남은 기간동안에는 구글 킥스타트 문제들을 좀 풀어보기로 했다. 구글 킥스타트는 구글에서 매년 개최하는 알고리즘 대회이다. 전 세계의 수만명이 참가하여 코딩 실력을 겨룬다. 1년에 여러 차례 대회가 열리는데(2020년 기준 한 달에 한 번꼴) 매번 대회가 끝나면 등수가 공개되어서, 객관적인 나의 수준도 판단할 수 있다. 매년 조금씩 바뀌지만 올해는 각 라운드당 3시간동안 네 문제를 푸는 형식으로 진행이 되고 있다. 나는 올해 중반부터 시작했고, 처음이다보니 아직 문제를 막 잘 풀지는 못했다. 그래서 2020년에 출제된 기출문제를 하나씩 풀어보면서 연습하고 그 내용을 블로그에 정리해 보려고 한다. 총 4문제 중에 4번 문제는 못 풀었고, 1~3번 문제만 풀어서 이에 대한 간단한 ..

링크드인 러닝 네트워크 기초 강의를 듣고 공부한 내용을 정리해 보려고 한다. 토폴로지 (Topology) 토폴로지는 노드들과 연결된 회선들을 포함한 네트워크의 구성을 나타내는 개념이다. 크게 물리적 토폴로지와 논리적 토폴로지로 구분한다. 물리적 토폴로지(Physical Topology) : 노드, 링크와 같은 네트워크 구성 요소들에 의해 결정된다. 논리적 토폴로지(Logical Topology) : 노드 사이의 데이터 흐름에 의해 결정된다. 토폴로지는 그래프 이론에 따라 다음과 같은 종류들로 나누어 질 수 있다. 메시 토폴로지 (Mesh Topology) 메시 토폴로지는 망이나 그물 형태의 토폴로지를 의미한다. 완전 연결형(Full Mesh)과 부분 연결형(Partial Mesh)으로 나뉜다. 완전 연결..

지난 포스팅에서 디자인패턴에 대한 개관을 살펴보았다. 이번 포스팅부터는 디자인 패턴을 하나씩 자세하게 알아보려고 한다. 가장 먼저 살펴볼 패턴은 추상 팩토리 패턴이다. 추상 팩토리 패턴은 객체 생성(Object Creational)과 관련된 패턴이다. 추상 팩토리 패턴은 상세화된 서브 클래스를 정의하지 않고도 서로 관련성이 있거나 독립적인 여러 객체의 군을 생성하기 위한 인터페이스를 제공한다. 이름만 봐서는 팩토리 메서드 패턴과 비슷해 보이지만 추상 팩토리 패턴은 팩토리 메서드 패턴을 좀 더 캡슐화한 방식이라고 볼 수가 있다. 추상 팩토리는 주로 다음과 같은 경우에 사용한다. 객체가 생성되거나 구성, 표현되는 방식과 무관하게 시스템을 독립적으로 만들고자 할 때 여러 제품군 중 하나를 선택해서 시스템을 설..

오늘은 백준 3012번 문제를 풀어보려고 한다. 이 문제는 07/08 크로아티아 정보올림피아드 기출문제이다. https://www.acmicpc.net/problem/3012 3012번: 올바른 괄호 문자열 예제 1의 경우 다음이 가능하다. ({([()])}), ()([()]{}), ([([])]{}) www.acmicpc.net 크로아티아 정보올림피아드 기출 문제여서 그런지 문제에 대한 아이디어가 쉽게 떠오르지는 않았던 것 같다. (난이도도 심지어 플레티넘 3 ㄷㄷ...) 처음에는 ? 각각에 들어갈 수 있는 문자 "{", "[", "(" 등을 찾아서 경우의 수를 생각해 주어야 하나? 라고도 떠올려 봤는데 너무 생각해 주어야 할 케이스가 많았고 이 방법은 맞지 않다는 것을 깨달았다. 결국 DP를 통해 한..

오늘은 오랜만에 BFS 문제를 풀어보려 한다. 백준 2146번 다리 만들기 문제이다.https://www.acmicpc.net/problem/21462146번: 다리 만들기여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다www.acmicpc.net 이 문제는 엄청 어렵게 느껴지진 않았다. BFS를 익숙하게 쓸 수 있으면 큰 문제 없이 풀 수 있는 문제로 보인다. 다만 BFS를 여러 차례 써야 하는 풀이가 있어서 조금 복잡하게 느껴질 수도 있을 것 같다.BFS에 대해서 간단하게 설명을 하면, 너비 우선 탐색 방법으로 그래프나 트리를 완전 탐색할 수 있는 방법 중 하나이다..

오늘 살펴볼 문제는 백준 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를 만든다. 그리고 가방을 무게 순으로 오름차순으로 정렬한..