정리하기 위한 블로그 정리하기 위한 블로그

외판원 순회 문제 - 여러 도시가 있고 도시 간 이동 비용이 있을 때 모든 도시를 한 번씩만 방문하여 시작 위치로 돌아오는 경로의 최소 비용을 구하는 문제. 각 도시가 20개라하면 20개의 도시를 모두 방문하는 경우의 수는 20! 이 된다. 모두 계산하지 않고 bitmask + memoization을 이용한다. https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 왜 dp[12 의 경로를 탐색하고 dp[101]의..

LIS 구현 1. lower bound 사용하여, 2. 새로운 값 x가 기존 lower bound 배열의 가장 큰 값보다 크면 뒤에 추가 기존 lower bound 배열에서 x보다 같거나 큰 값 중 첫 번째를 찾아 업데이트 해준다. 즉 F, F, ... F, T, .. T 인 분포에서 x

https://www.acmicpc.net/blog/view/109 이분 탐색(Binary Search) 헷갈리지 않게 구현하기개요 이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다. 이분 탐색 문제를 풀다보면 탈출 조건으로 lo www.acmicpc.net 이분 탐색 구현할 때마다 항상 헷갈려서 시간이 걸리게 되는데, 위의 글 읽고 정리해본다. 구현 방법 먼저 결정 문제 설정과 분포 파악해야한다. 문제마다 결정 문제가 다른데 이를 먼저 설정하고, 결정 문제에 따른 True, False 결과의 분포를 생각해본다. 예를 들면 1~50번의 카드 중 28번 카드를 찾는다고 하자. 1~50번의 카드를 v[i] 찾는 카드를 val 이라 할 때, 결정 문제는 val  lo+1 동안 범위를..

내가 직접 풀진 못 했지만 다른 사람의 풀이를 보고 너무 처음보는 방식이라 정리라도 해본다.1. 문제https://leetcode.com/problems/modify-graph-edge-weights/ 그래프에서 src 출발지와 dest 목적지와 target 비용이 주어졌을 때cost가 -1인 길을 고쳐 target의 비용과 같게 만들어 return 해라. 단 -1인 길을 제외하고 이미 target보다 짧은 경로가 존재하면 실패 (빈값 리턴)-1을 고친 후에도 하나라도 target보다 짧은 경로가 존재하면 안 된다. 2. 풀이1. -1 을 경로를 처음부터 제외하고 dijkstra 돌린다.2. target 보다 짧은 경로가 있으면 빈값, target과 같은 경로가 있으면 -1을 전부 MAX로 만들고 ret..

1

흔히 사용되는 소켓 옵션을 정리한다. SO_KEEPALIVE 이 옵션을 활성화하면 상대방에게 약 2시간 간격으로 TCP 패킷을 보낸다. 이 패킷에 대해 상대가 ACK 패킷으로 응답하면 응용 프로그램에 통보 없이 커널 선에서 살아 있음 확인하고 마무리한다. 아무런 응답이 없거나 RST 패킷을 받으면 자동으로 소켓을 닫는다. TCP 연결에서는 데이터 교환이 없는 건지, 상대 시스템이 다운되거나 네트워크 연결이 불가능한지 알 수 없다. 소켓 생성이 늘어나면 시스템 자원 소모도 비례해서 늘어나므로 연결이 끊어진 소켓을 닫아줄 필요가 있다. 이때 SO_KEEPALIVE를 설정하여 주기적으로 불필요하게 열린 소켓을 닫을 수 있다. 하지만 커널에서 주기가 보통 2시간으로 되어 있기 때문에 비정상적인 종료를 빠른 시간..

풀이를 안 보고 풀진 못 했다. 해답이 많이 올라와 있지만 스스로 정리를 하며 기억하기 위해 작성해본다. 1. 문제 https://www.acmicpc.net/problem/11025 11025번: 요세푸스 문제 3 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000,000) www.acmicpc.net 1번부터 N번까지 원형으로 앉아있고 K번째 마다 제거 할 때, 마지막에 남은 번호를 구하는 문제. 1 > n >> k; int ans = 1; for(int i=2; i

1. 문제 https://leetcode.com/problems/letter-combinations-of-a-phone-number/ Letter Combinations of a Phone Number - LeetCode Letter Combinations of a Phone Number - Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digits to letters (just like on the telephone leetcode.com 번호가 ..