분류 전체보기
[BaekJoon] 백준 2352번 반도체 설계
[BaekJoon] 백준 2352번 반도체 설계 🎈문제 https://www.acmicpc.net/problem/2352 💬설명 LIS 문제인데 DP로 풀게되면 시간초과가 난다. 이분탐색으로 문제를 풀어줘야 한다. 👩💻코드 # BaekJoon 2352.py N = int(input()) arr = list(map(int, input().split())) lst = [] # 이분 탐색으로 lower bound 찾아주기 def find(s, e, v): global lst while s < e: m = (s + e) // 2 if lst[m] < v: s = m + 1 else: e = m return e for i in range(N): # 첫번째 숫자인 경우 if i == 0: lst.append(ar..
[Algorithm] 최장 증가 수열 (LIS)
최장 증가 수열(LIS) 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 푸는 방법 DP dp[x] : x번째 수를 마지막 원소로 가지는 list의 길이 라고 점화식을 두면 O(N^2)의 시간복잡도로 구현할 수 있음 하지만 N이 10만이 넘으면 이걸로 풀수 없음 -> 이분탐색으로 시간을 단축시키자 for (int k = 0; k < n; k++){ length[k] = 1; for (int i = 0; i < k; i++){ if(arr[i] < arr[k]){ length[k] = max(length[k], length[i] + 1); } } } 이분탐색 시간 복잡도: O(..
[Algorithm] 이분 탐색
정렬되어 있는 배열에서 데이터를 찾으려고 할 때 O(N)이 걸리는 순차탐색에서 시간을 줄여 O(logN)의 시간으로 값을 찾는 탐색 방법 특징 및 과정 이분 탐색을 하고자 하는 배열이 이미 정렬되어 있어야함 과정 left, right로 가운데롤 mid로 잡아줌 mid과 구하고자 하는 값을 비교 mid left = mid + 1 mid > 구하고자 하는 값 -> right = mid - 1 left > right이 될때까지 2-4번을 반복
[Network] Top Down Approach 3장: Transport Layer
Transport Layer Transport Layer는 Application layer와 Network layer 사이에 존재하는 layer로 서로 다른 host에서 동작하는 application 프로세스들 간의 논리적 통신을 제공함 Transport-layer services 특징 Transport protocol은 host에서만 존재한다. Send side: 보내는 App messages를 segment로 나눠서 network layer로 전달함 Receive side: segment를 다시 message로 재구성해서 app layer로 전달함 하나 이상의 transport protocol이 app에 존재함 ex) Internet: TCP, UDP Transport vs Network layer ..
[OS] Memory Management
Background - 프로그램은 실행을 위해 디스크에서 메모리로 적재되어야 함 - 메인 메모리와 레지스터들이 CPU가 접근할 수 있는 유일한 저장소임 - 레지스터에 접근하는 것은 1 CPU clock cycle 이하로 소요됨 - 메인 메모리에 접근하는 것은 수많은 cycle들을 소요할 수 있음 - Cache 접근은 메인 메모리에 접근하는 것과 CPU 레지스터에 접근하는 것 사이만큼의 시간이 소요됨 - 올바른 작동을 보장하기 위해 메모리 보안이 필요함 Memory Address Binding Memory Address Symbolic Address: 코드 단에서 설정하는 address (ex. a = 10) Virtual(Logical) Address: 프로그램이 이상적으로 사용하는 주소 체계 Physi..
[BaekJoon] 백준 17144번 미세먼지 안녕!
[BaekJoon] 백준 17144번 미세먼지 안녕! 🎈문제 https://www.acmicpc.net/problem/17144 💬설명 - 단순한 구현문제였다. - 다만 python3로 채점하니 시간초과가 나서 pypy로 채점했다. 👩💻코드 # BaekJoon17144.py import copy # 변수 및 배열 초기화 R, C, T = map(int, input().split()) dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] A = [[] for _ in range(R)] cleaner = [] for i in range(R): A[i] = list(map(int, input().split())) for _ in range(T): # 확산 new_A = copy.deepcopy..
[BaekJoon] 백준 2098번 외판원 순회
[BaekJoon] 백준 2098번 외판원 순회 🎈문제 https://www.acmicpc.net/problem/2098 💬설명 간단하게 말하자면, 해당 문제는 사이클을 구하는데 그 사이클을 돌 때 가장 적은 비용이 드는 사이클을 구하는 것이다. 즉, 1->0->2->3->1 이렇게 돌아서 오는 경우와 2->3->1->0->2 이렇게 돌아서 오는 경우가 드는 비용이 같다는 것을 우선 염두에 두고 생각을 해보자. (편의상 0번 도시부터 있다고 가정하자.) 그렇게 되면, 우리는 모든 경우를 돌 때 0번 도시에서 출발한다고 가정해도 무방하다. 0->...->0 에서 ("..." 에 들어가는 도시들의 순서 + 모든 도시들을 돌았는지)만 고려해주면 되니까! 다시 말해서, 0번 도시에서 시작하는 경우만 생각하더라도..
[Network] Top Down Approach 2장: Application Layer
Application Layer Application Layer는 서로 다른 Host의 application이 서로의 message(data packet)을 교환하는데 사용됨 ex) HTTP, SMTP, FPT Principles of network applications Application Architectures (가능한 application 구조) Client - Server 구조: 서버와 클라이언트 간 통신 Server 항상 연결되어 있어야 한다. always-on 영구적인 IP 주소를 가진다. 규모에 따라 바뀌는 데이터 센터를 가진다. Client 서버를 통해서만 소통한다. 가끔 연결된다. always-on 유동적인 IP 주소를 갖는다. Peer to Peer (P2P) 구조: 호스트끼리 직접..