목록전체 글 (344)
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/bhalTq/btsBKjjfc4Y/brFClNLgaCSJUPfC37pNf0/img.jpg)
이것도 시리즈 문제인 듯하다. 가장 긴 증가하는 부분 수열의 알고리즘을 이용하면 된다. dp로 하면 메모리 초과 나서 이분탐색으로 풀어주어야 한다. 제거해야 할 전깃줄 개수는 쉽게 구할 수 있었으나 요소를 구하는데 고민을 많이 했다. lis 리스트를 하나 만들어서 최장길이 값을 넣어주고 역순으로 탐색을 해서 제거대상을 뽑아 주었다. def bs_func(target): l,r = 0,len(bs) t = 0 while l
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/byFlFz/btsBQn57yJT/4KIf01iqtIKGwrkKvQYGz0/img.jpg)
딱히 어려운 부분은 없었으나 멀티탭 크기가 넘을 때 빠질 애를 선정하는 방법에 대해서 고민을 좀 했다. 가장 멀리 떨어진 애가 먼저 빠지도록 코드를 짰다. 어케야 효율적으로 짤 수 있을까 고민했으나 그냥 index를 사용해서 판별하는 게 내가 생각할 수 있는 최선이었다. import heapq n, k = map(int, input().split()) data = list(map(int, input().split())) list_data = [] answer = 0 for i in range(k): if data[i] in list_data: continue if len(list_data) < n: list_data.append(data[i]) continue temp_list = data[i:] idx..
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/cSChj8/btsBOhk1igR/gVZJH0UTrjgU4khHcrAkOk/img.jpg)
시리즈가 꽤 많은 문제다 이게 푼 지 좀 오래돼서 기억이 가물가물하다. LIS가 DP로 푸는 방법이 있는데 이 문제는 메모리 제한이 걸리므로 이분탐색으로 풀어주어야 한다. 이분 탐색으로 LIS 길이를 구할 수 있다. 하지만 문제에서는 LIS 요소까지 출력을 해주어야 한다. 나는 이분탐색으로 도출한 최장 길이 값을 이용해서 LIS를 역순으로 탐색해서 값을 저장해 주었다. def bs_func(target): l,r=0,len(bs) t = 0 while l
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/EqEk9/btsBOeICwqJ/XDY3UzWZzD2SBCWU1BwUM1/img.jpg)
올해 푼 문제 중에 가장 어려웠다. 수학적 지식이 필요한 문제인지라 과거 공부에 뜻이 없었던 나에게 상당히 어려웠다. 이 문제의 핵심은 ccw 알고리즘이다. 벡터의 외적을 이용해서 선분이 교차하는지 판단할 수 있다. 게임에서도 ccw 알고리즘이 많이 쓰인다고 한다. 위치 판별 및 물체 부딪힘 등등 신기하다.... 선분 (A, B), (C, D)가 있을 경우 CCW(A, B, C)*CCW(A, B, D) < 0 and CCW(C, D, A)*CCW(C, D, A) < 0 가 둘다 -1이 나올 경우 접점이다. 예외는 둘다 일직선 상으로 겹치는 경우이다. 둘 다 0일 경우 좌표 위치를 계산해서 겹치는지 판단한다. 그리고 그룹을 구해야 하기 때문에 union find를 사용했다. from collections ..
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/1CT0M/btsBKidt0Fq/Uw1p3QmyZ6tNuGNTFNWBO1/img.jpg)
얘는 규칙성만 찾으면 그리 어렵진?? 않다. 그 규칙성 찾느라 하루가 걸렸다. case. 1 홀수 홀수일 경우 그냥 지그재그로 더하면서 내려온다. case. 2 홀수 짝수일 경우도 지그재그로 더하면서 내려오면 된다. case. 3 짝수 짝수일 경우가 골치 아프다. 일단 빠져야 할 칸을 찾아야 하는데 하나씩 해보니깐 체스판 형식으로 빠져야 할 애들이 정해져 있었다. 그중에서 가장 값이 작은 애를 빼준다. 그리고 빠진 값의 위치 값을 저장해 두었다가. 그 라인만 피해서 지그재그로 움직여 준다. 빠진 칸의 라인은 적절히 피해 주는 코드를 짜준다. 하나씩 노가다로 통해 얻은 결과이다. n,m = map(int, input().split()) data = [] for _ in range(n): data.appen..
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/bZ8DXN/btsBMQHxnWv/h5HNe2kDKbscQLT3QahR71/img.jpg)
apiVersion: apps/v1 kind: Deployment metadata: name: deploy-nginx labels: app: deploy-nginx spec: replicas: 3 selector: matchLabels: app: deploy-nginx template: metadata: labels: app: deploy-nginx spec: containers: - name: nginx image: nginx --- apiVersion: v1 kind: Service metadata: name: cl-nginx spec: selector: app: deploy-nginx ports: - name: http port: 80 targetPort: 80 type: ClusterIP Clus..
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/cztNyI/btsBGE1Mc5W/nOdfQed3bsSuQGJqTLfJLk/img.png)
배포 방법에 대해 알아본다. 먼저 포트포워딩이다. 해당 yaml을 배포한다. 포트포워딩 명령어이다. 마스터노드에 들어온 ip를 워커노드 80 포트로 보낸다는 뜻이다. 로컬에서 curl을 날려본다. 포트포워딩은 많이 쓰지 않고 그냥 테스트용으로 쓰인다. 그다음 hostport와 hostNetwork는 사용자가 어디 노드로 배포했는지 알아야 접속할 수 있다. 비현실적이기에 사용하지 않는다. NodePort에 대해 알아본다. apiVersion: apps/v1 kind: Deployment metadata: name: deploy-nginx labels: app: deploy-nginx spec: replicas: 3 selector: matchLabels: app: deploy-nginx template: ..
![](http://i1.daumcdn.net/thumb/C200x200/?fname=https://blog.kakaocdn.net/dn/crzj1P/btsBDRmAMyK/CUVkwiLEA3XkkbuVdgalg0/img.png)
union find를 이용해서 부모 노드를 계속 갱신해 주고 나중에 set로 출력해 준다. def find_(start): if cost[start] == start: return start cost[start] = find_(cost[start]) return cost[start] def union_(a,b): data_a = find_(a) data_b = find_(b) if data_a < data_b: cost[data_b] = data_a else: cost[data_a] = data_b n = int(input()) data = [] cost = [i for i in range(n+1)] for _ in range(n-2): a,b= list(map(int, input().split())) ..