Computer Sci.

이번에 살펴볼 문제는 백준 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 레벨로 분류했다. 플레티넘 레벨은 상당수가 쉽게 해결책을 찾기 어려운 고난이도 문제이다.(나에게는) 이 문제도 그래서 사실 풀다가 다른 사람의 소스를 어느 정도 참고하였고, 천천히 상세하게 풀이를 정리..

나는 요즘 네트워크 공부를 하고 있다. 학부에서 배우지 않았지만 업무를 하면서 필요성을 많이 느꼈고, 기본적인 지식은 알고 있어야 겠다는 생각으로 공부를 시작하게 되었다. 나는 Udacity에서 라는 무료 강의를 통해 공부 중이며, 강의 수가 많지 않아서 빠르게 완강할 수 있다. 공부를 하면서 기본적인 개념들을 이렇게 블로그에 정리를 해 놓으려고 한다. https://www.udacity.com/course/networking-for-web-developers--ud256 Networking for Web Developers You've used the Internet. Now find out more about how it works. www.udacity.com 우선, 이 강의에서 간단한 실습들을 하..

오늘 살펴볼 문제는 카카오 19년 겨울인턴 코딩테스트 4번 문제이다. https://programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카카오는 매번 코딩테스트마다 문제 해설을 자사 블로그에 공개한다. 관심있는 분들은 읽어 보아도 좋을 것 같다. 2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설 2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설 – tech.kakao.com “2019년 카카오 개발자 겨울 인턴십” 공개 채용을 위한 1차 코딩 테스트가 지난..

오늘 살펴볼 문제는 백준 9202번 문제이다. https://www.acmicpc.net/problem/9202 9202번: Boggle 문제 상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다. Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지 www.acmicpc.net 사실 이 문제는 굉장히 어려웠다. 그래서 나는 다른 분의 코드를 어느정도 참고해서 풀었다..