programmer life guidance 101

> 트라이(Trie) 여튼 또 문자열인데, 이번엔 매칭 문제가 아니라 여러 문자열을 저장하는 자료구조를 소개해드릴 겁니다. 바로 트라이(Trie)인데, 트리와 굉장히 스펠링이 비슷하면서 트리와도 유사합니다. 아니, 아예 트리의 한 종류라고 해도 될 겁니다. 래딕스 트리(radix tree)나 접두사 트리(prefix tree)라고도 합니다. 예를 들어 {"he", "she", "her", "him", "show"}라는 문자열 집합이 있다면, 그들을 담고 있는 트라이는 그림과 같습니다. 빨간색 겹선 노드가 여기서 끝나는 문자열이 있다는 뜻으로, output이 있다고 하거나 final state, accepting node라고도 하는 등... 그런 의미가 있습니다. 왜 트라이의 별칭 중 접두사 트리라는 것이..

www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다고 가정해도 좋다. x�� www.acmicpc.net 문제 다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다. 조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다. 2차원 평면에 N개의 점..

leetcode.com/problems/valid-sudoku/ Valid Sudoku - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each..

leetcode.com/problems/sudoku-solver/submissions/ Sudoku Solver - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exac..

leetcode.com/problems/majority-element/ Majority Element - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Given an array of size_n_, find the majority element. The majority element is the element that appearsmore than⌊ n/2 ⌋times. You may assume that the array is non-empty and ..

leetcode.com/problems/next-permutation/ Next Permutation - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Implementnext permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange i..

www.acmicpc.net/problem/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위� www.acmicpc.net 문제 농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다. 두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다. 예를 들어 용량이 5인 파이프가 용량이 3인 파이프와 ..

www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해� www.acmicpc.net 문제 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다. 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다. 농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오...

> 스위핑 기법(Sweeping Algorithm) 이번에 소개해 드릴 기법은 스위핑 알고리즘(sweeping algorithm)이라고 하는데, 기법 개념 자체는 굉장히 간단하고 범용적인 대신에, 대부분 겁나게 어렵습니다. 기본적으로 다른 기법이나 자료구조와 반드시 얽힙니다. 스위핑이라는 건 그냥 어떤 선이나 공간을 한쪽에서부터 싹 쓸어버린다는 건데 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 뭔가를 해 주면 정답이 구해지는 형태입니다. - BOJ[2170] : 선 긋기 https://www.acmicpc.net/problem/2170 [ 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1≤N≤1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점이 주어진다. 선택..

핸드세이크(Handshake) 통신의 양측 간에 조건에 합의해 가는 정보 교환 과정 - DTE, DCE DTE : Data Terminal Equipment DCE : Data Communications Equipment DTE 사용자 - 네트워크 인터페이스의 사용자측에서 데이터발신 장치나 수신 장치, 또는 두 가지 겸용으로 사용되는 장치 DTE는 반드시 모뎀과 같은 DCE 장치를 통해 데이터 네트워크에 연결되며, 일반적으로 DCE에 의해 생성된 클럭처리 신호를 말한다. DTE에는 컴퓨터, 멀티플렉서, 라우터 등과 같은 장치가 포함된다. DCE 사용자 - 네트워크 인터페이스의 네트워크 측으로 구성되는 통신 네트워크 장비의 연결 수단 DCE는 네트워크로 연결되는 물리적 수단이며, 트래픽을 전송하고, DCE..

SSL/TLS란? Secure Socket Layer, Transport Layer Security 전송 계층 상에서 클라이언트, 서버에 대한 인증 및 데이터 암호화 수행 클라이언트와 서버 양단 간 응용계층 및 TCP 전송계층 사이에서 안전한 보안 채널을 형성해 주는 역할을 수행하는 보안용 프로토콜 주요 응용 HTTP(HTTPS), FTP(FTPS), TELEMENT, SMTP, SIP, POP, IMAP 등에서 사용 가능 주로, 웹 브라우저와 웹 서버사이의 안전한 보안 채널을 제공하기 위해 많이 사용된다 OpenSSL *DTLS는 TLS프로토콜은 UDP에 적용가능하게 해주는 UDP를 위한 프로토콜이다. 그러므로 UDP기반의 애플리케이션들은 이 DTLS를 사용함으로 도청, 간섭, 메시지 변조 등 네트워크..

TCP 와 UDP 전송 계층에는 크게 TCP(Transmission Control Protocol) 와 UDP(User Datagram Protocol) 2가지 프로토콜이 있다. -TCP 연결지향적이며 오류제어, 흐름제어, 혼잡제어, 타이머재전송 등의 기능을 하며 연결지향이란말은 데이타를 전송하는 측과 데이타를 전송받는 측에서 전용의 데이타 전송 선로(Session)을 만든다는 의미이다. 데이타의 신뢰도가 중요하다고 판단될때 주로 사용된다.(가상회선 방식 패킷교환) -UDP 비연결지향이며, 최소한의 오류제어 기능만 수행한다. 단순히 데이타를 받거나, 던져주기만 하는 프로토콜이다. UDP는 특히 실시간 멀티미디어 정보를 처리하기 위해서 주로 사용한다.(데이터그램 방식 패킷교환) 여기서 딱 보이는 둘의 차이..

전송계층(Transport Layer) 먼저 네트워크란 데이터를 교환하기 위해 전송 매체를 매개로 서로 연결되어 있는 것이고 인터넷은 전세계 컴퓨터들이 서로 연결되어있는 거대한 네트워크를 뜻한다. 사람간의 대화에서 같은 언어를 이용해 의사소통 하듯 네트워크 상에서 데이터를 주고받기 위해서 일종의 정해진 규약이 있는데 이것을 프로토콜이라고 부른다. 네트워크 상에서 정보를 주고받으려면 어느 경로로 보낼지 어떤 방식으로 데이터를 보낼지 등등 고려해야할 사항이 많다. 만약 하나의 규약을 정해놓았다면 문제가 발생 하였을시 전체를 바꾸어야 하고 또 문제가 발생하기도 쉬울 것이다. 그래서 역할을 나누어 네트워크는 네트워크 계층 구조를 가지게 되었다. 각각의 계층은 모듈단위로 독립적이지만 서로 상호 유기적인 관계를 가..

> 레이지 프로퍼게이션(Lazy Propagation) 이번에도 트리에 관한 내용인데, 아마 다음엔 기하 관련 내용을 쓰지 않을까 싶습니다. 특히나 세그먼트 트리에 관한 내용입니다. 지금까지는 세그먼트 트리에는 2개의 연산이 있었습니다. 특정 인덱스의 값을 바꾸는 것과, 특정 구간의 합, 최댓값 등을 구하는 것. 그런데 레이지 프로퍼게이션(lazy propagation)이란 것을 사용하면 이런 연산도 가능합니다. 특정 구간 [a, b]에 값 c를 동시에 더한다 더한다는 연산은 다른 연산이 될 수도 있습니다. 보통은 구간합 트리가 많이 쓰이므로 더하는 연산이 됩니다. 저 연산을 naive하게 구현한다면 구간 [a, b] 안의 모든 인덱스에 c씩을 더하는 업데이트 연산을 할 것이므로 구간 길이가 K면 O(K..

> Convex Hull(볼록 껍질) 볼록 껍질(convex hull)이라는 개념은 2차원 평면상에 점이 여러 개가 있을 때 이 점들 중 일부를 골라서 만들 수 있는, 나머지 점들을 모두 포함하는 볼록다각형을 말합니다. 이때 포함한다는 말은 점이 다각형의 경계에 걸쳐 있는 것도 인정합니다. 즉, 변 위에 있어도 된다는 것. 이런 점들이 있다면, 이것이 바로 볼록 껍질입니다. 볼록 껍질에 속한 점 개수는 6개군요. 그럼 이러한 다각형이 왜 항상 볼록다각형으로 결정될 수 있을까요? 사실 그건 조금만 생각해 보면 직관적으로 당연합니다. 점을 모두 포함하는 어떤 오목다각형이 있다고 해도, 오목한 지점의 점을 다각형에서 제외시키고 전후의 점을 그냥 이어버려도 새 다각형에 그 점도 포함이 되니까요. 또한, 볼록다각..