https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 오랜만에 그래프 문제를 풀었다. STL도 한동안 사용하지 않다가 사용하려니 실수가 많았다. 이 문제는 원래는 위상정렬이랑 DP 문제라는데, 위상 정렬로 풀기가 조금 애매해서 위상정렬 비스무리한 무언가로 풀게 되었다. 해결 방법은 이렇다. 맨 처음에 queue에(나는 그냥 vector를 사용했다) 처음부터 시작할 수 있는 건물들을 의 pair로 집어넣는다. 그 다음 각 iteration에서 q..

아주 멋진 닭 내가 그와 눈을 마주쳤을 때, 그는 나에게 다가왔다. 오, 아주 멋진 닭이여! '꼬끼오' 하고 울어다오. 직접 쓴 시이다.

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net divide and conquer 문제인데, 다소 까다로운 부분이 있다. 직접 2차원 배열을 돌면서 수를 일일이 입력하고 다니면 N>=15라는 조건 때문에 시간 초과가 발생한다. 따라서 4개의 사분면으로 분할하여 계산을 생략해주는 과정이 반드시 필요하다. 나는 sizeRec에 미리 작은 사분면의 넓이를 저장한 후에 어느쪽 사분면이냐에 따라서 0, 1, 2, 3을 곱해 주어 직접 계산하는 과..

https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net divide and conquer로 해결할 수 있는 문제이다. start에서 end까지의 부분 히스토그램을 보았을 때, 그 안에서 만들 수 있는 직사각형의 최대 넓이는 세 경우 중 하나에서 구할 수 있다. 편의상 mid = (start+end)/2 로 정의한다. 1. start ~ mid까지의 부분 히스토그램 중 최대 넓이 2. mid+1 ~ end까지의 부분 히스토그..

매우 간단한 greedy와 sort 문제이다. 입력받은 물이 새는 위치를 정렬하고, 정렬된 값을 앞에서부터 테이프를 가장 많이 남기는 방식으로 붙여나가면 된다. 이것의 정당성 증명은 간단하다. 특정 물이 새는 위치 leak[i]까지만 보았을 때, leak[i]가 이미 테이프로 cover되어 있다면 테이프를 붙이지 않는 것이 자원을 가장 아끼는 방법이고, 테이프가 cover되어 있지 않다면 테이프를 가장 많이 남기는 방식으로, 즉 leak[i]-0.5 지점부터 붙이는 것이 가장 자원을 아끼는 방법이다. leak[i]까지만 보았을 때는 이보다 효율적인 방법은 없고, leak[n]까지 이를 반복하면 된다. 시간복잡도는 NlogN + N = O(NlogN)이다. 1 2 3 4 5 6 7 8 9 10 11 12 ..

https://www.algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 www.algospot.com 재귀 연습 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 #i..

Multi-NIC System의 설정 multi channel LAN card를 가지고 컴퓨터 간 연결을 할 때 두 개의 컴퓨터 사이에 여러 개의 케이블을 연결하여도 모든 케이블이 정상적으로 동작하지 않고 일부 케이블으로만 통신을 하는 오류가 있었다. 이 문제를 해결하기 위한 방법을 ni.com에서 찾아서 정리해 보았다. 169.254. 아이피의 문제 처음으로 발견한 문제는 169.254로 시작하는 아이피들이 할당된 것이었다. IPv4주소는 multiple한 Network에서 reusable하다. 만약, private network를 사용하는 경우에는 10.x.x.x, 192.168.x.x 또는 172.x.x.x의 형태를 사용하는 경향이 있다. 왜냐하면 대부분의 OS에서는 DHCP server를 통해 T..

동기와 비동기 IO 동기(Synchronous) 요청을 보내면, 요청을 처리할 떄까지 대기한다. 즉, sender가 데이터를 보내는 시간과 receiver가 데이터를 수신하는 시간이 같아야 한다. 이 경우 모든 처리가 끝날 때까지 sender와 receiver가 기다려야 하기 때문에 비효율적이다. 비동기(Asynchronous) 요청을 처리할 때까지 기다리지 않고, 바로 다음 작업으로 넘어간다. sender가 데이터를 보내는 시간과 receiver가 데이터를 수신하는 시간이 같지 않다. sender가 처리를 요청하기 위해 함수를 호출했을 때, 호출된 함수는 바로 응답한다. 이떄의 응답은 결과에 대한 답이 아니라 확인을 했다는 결과를 리턴하는 것이다. 그 다음, 호출된 함수가 작업을 끝내면 callback..