오구리의 DevLog

▶70 - Climbing Stairs ▶문제 You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? ▶예제 Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1..

▶931 - Minimum Falling Path Sum ▶문제 Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix. A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1,..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 2022.12.10 - [컴퓨터공학/수치해석] - [수치해석] Ch14. Directed Methods - Multidimensional Gradient method은 최적을 찾기 위한 효율적인 algorithm을 생성하기 위해 derivative 정보를 명시적으로 사용한다. ▶Gradients and Hessians 첫 번째 도함수가 0이 되면 최적의 값에 도달한 것이다. 두 번째 도함수의 부호는 양수면 최소, 음수면 최대에 도달한 것이다. 즉, 갈 수 있는 공간 360도 전체 중에서, 가장 경사가 급한 쪽으로 간다. (특히 ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 13장에서 one-dimentional search는 롤러코스터와 같았다. two-dimensional의 경우, 산과 계곡의 이미지가 된다. 미분 평가를 필요로 하지 않는 접근법을 nongradient 방법 또는 direct 방법이라고 한다. 도함수를 필요로 하는 것들을 경사법(gradient) 또는 하강법(또는 상승법)이라고 한다. ▶Random Search brute force 접근의 간단한 예는 random search method이다. 독립 변수의 랜덤하게 선택된 값에서 함수를 반복적으로 평가한다. 충분한 수의 샘플이 수..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Optimization 근 찾기와 최적화는 함수의 점을 추측하고 검색하는 것과 관련이 있다. • 근 찾기는 함수의 0을 검색하는 것이다. • 최적화는 여러 변수의 함수의 최솟값 또는 최댓값을 찾는 것이다. f'(x)를 분석적으로 사용할 수 없기 때문에 종종 복잡해진다. 따라서, 때때로 미분을 추정하기 위해 finite-difference approximation을 사용해야 한다. (a) 1차원 최적화 f(x)의 최소화가 -f(x)의 최대화와 어떻게 동일한지를 보여준다. (b) 2차원 최적화 최대화(최대 고도까지 상승) 또는 최..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 다항식의 근은 세가지 규칙을 따른다.1. n차 방정식의 경우, n개의 실근과 허근을 가진다.(근들이 반드시 구별되는 것은 아니다.)2. n이 홀수면, 적어도 하나의 실근을 가진다.(complex root(허근)은 +- 한쌍을 가지기 때문에 남는 하나는 실근이 된다.)3. 허근이 존재하면, 한 쌍으로 존재한다.(λ + μi와 λ - μi, i는 root(-1)) ▶Synthetic division 연산을 수행하기 위해 여러 컴퓨터 알고리즘(합성 분할 및 기타 방법에 기반)을 사용할 수 있습니다. n차 다항식을 단항 인자 (x - ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Max Flow Ford-Fulkerson 알고리즘 Min cut Maxflow-mincut - baseball elimination ▶Max Flow Edge-weighted Digraph 간선의 weight : (거리 아닌) flow 흐를 수 있는 최대량 capacity를 나타낸다. (>= 0) flow의 출발지 s, 도착지 t Max Flow는 출발지에서 도착지로 흐를 수 있는 flow의 최대량 꼭 지켜야 하는 물리적 법칙 1. flow는 간선 방향 따라서 흐른다. 2. 0 > V라면 -> EU P의 mi..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 2022.12.09 - [컴퓨터공학/알고리즘2] - [알고리즘2] Shortest Paths on Weighted Digraphs [알고리즘2] Shortest Paths on Weighted Digraphs 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Content dhalsdl12.tistory.com ▶Seam Carving 이미지의 크기 조절 시 중요한 부분 자동 인식해 최대한 보존하며 ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents 최단경로 Bellman-Ford algorithm Dijkstra algorithm Acyclic Shortest Path Seam Carving ▶Shortest Path(Edge-Weighted Digraph) 간선에 weight가 있는 directed graph G s에서 t까지 연결하는 경로 중 (연결된 간선의 집합) 간선의 weight 합이 최소인 경로 weight 합이 0보다 작은 사이클이 있는 그래프는 최단 경로로 존재하지 않는다. 사이클이 있어도 최단 경로는 존재한다. weight가 0보다 작은 ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 2022.12.08 - [컴퓨터공학/알고리즘2] - [알고리즘2] Minimum Spanning Tree(MST) [알고리즘2] Minimum Spanning Tree(MST) 복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Content dhalsdl12.tistory.com ▶구현 API 정리 # 이미 구현된 기능 class Edge: # Weight 있는 방향성 없는 간선 나타내는 클래스 (예..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents MST Greedy algorithm Kruskal's algorithm Prim's algorithm lazy version Prim's algorithm eager version ▶MST Minimum Spanning Tree : Wegiht 합이 최소인 spanning tree 1. Tree (connected and acyclic subgraph of G) 2. Spanning tree (모든 정점 포함) 3. 간선의 weight 합이 최소 Brute-force 알고리즘 : 모든 가능한 spannign ..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. 중간을 쳤을 때, 이대로 가다간 B+을 받을 거 같아서, 새롭게 마무리 정리의 필요성을 느꼈다. 키포인트나, 중요한 부분을 정리해서 올려야겠다. ▶10장. SQL(Structured Query Language) 1. SQL 데이터 정의어 테이블 생성/제거, 애트리뷰트 추가/제거, 뷰 생성/제거, 인덱스 생성/제거 2. SQL 데이터 조작어 검색(select) select [all|distinct] 열_리스트 from 테이블_리스트 [where 조건] [group by 열_리스트 [having 조건]] [order by 열_리스트..

▶14786 - Ax+Bsin(x)=C ② ▶문제 A, B, C가 주어졌을 때, Ax+Bsin(x)=C를 만족하는 x를 찾는 프로그램을 작성하시오. ▶입력 첫째 줄에 정수 A, B, C가 주어진다. (0 < B ≤ A ≤ 100,000, 0 < C ≤ 100,000) ▶출력 첫째 줄에 x를 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다. ▶풀이 start와 end를 각각 0과 2c로 두고 풀었다. end를 2c로 둔 이유는 그냥이다... 죄송합니다. 아무튼 기준으로 잡은 start와 end를 가지고 이분 탐색을 돌렸다. 기준이 되는 오차가 있기에, start와 end의 차이가 오차보다 작아지면 반복문을 종료하였다. 또한 f(mid) 값이 바로 0이 될 수도 있기에 그때도 종료시켜 주었다. i..

▶11003 - 최솟값 찾기 ▶문제 N개의 수 A1, A2,..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. ▶입력 첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000) 둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109) ▶출력 첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다. ▶풀이 deque를 이용해서 값을 구했다. 기존에 deque에 존재하는 값이 새로 들어오는 값보다 큰 경우에는 그냥 빼주었다. 그다음에 index와 그 arr값을 넣어주었다. 만약에 새로운 값이 들어왔는데 가장 앞에 있는 값과의 차이가 L..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Services Packet Switching Performance Internet Protocol Version 4 Next Generation (IPV6) Transition from IPV4 To IPV6 ▶Performance 네트워크 계층의 서비스를 사용하는 상위 계층 프로토콜은 이상적인 서비스를 받기를 기대한다. 하지만 네트워크 계층은 완벽하지 않다. 네트워크의 성능은 delay, throughput, packet loss로 측정할 수 있다. 혼잡 제어는 성능을 향상시킬 수 있는 문제이다. ▶Dela..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Services Packet Switching Performance Internet Protocol Version 4 Next Generation (IPV6) Transition from IPV4 To IPV6 ▶Services Packetizing 네트워크 계층의 첫 번째 의무는 패킷화이다. source에서 네트워크 계층 패킷의 페이로드 캡슐화 및 destination에서 네트워크 계층 패킷의 페이로드 캡슐화 해제이다. 즉, 네트워크 계층의 한 가지 의무는 페이로드를 변경하거나 사용하지 않고 ★source에서..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶트랜잭션 ex. A 계좌에서 100원을 B계좌로 이체하는 트랜잭션 T:Read(A) A = A - 100 Write(A) Read(B) B = B + 100 Write(B) 실행 도중 장애 발생 A 계좌 100원 인출, B계좌 입금 실패 시 모순 상태(inconsistent state) 발생 둘 다 수행되거나, 하나라도 수행되지 않아야 한다. DBMS는 어느 부분이 트랜잭션인지 알 수 없다. 사용자가 트랜잭션을 명시적으로 표시해야 한다. 트랜잭션이란? 일련의 연산들의 집합니다. 하나의 논리적 기능을 수행하기 위한 작업의 단위로..

복습하기 위해 학부 수업 내용을 필기한 내용입니다. 이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다. 그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다. ▶Contents Ethernet Wifi, IEEE 802.11 Project Bluetooth ▶Bluetooth 블루투스 LAN은 애드혹 네트워크(기기끼리 바로 연결 가능한 network)이다. (네트워크가 자발적으로 형성된다.)\ 때때로 가젯이라고 불리는 장치는 서로를 찾고 피코넷이라고 불리는 네트워크를 만든다. 블루투스 랜은 가젯 중 하나에 이러한 기능이 있으면 인터넷에 연결할 수도 있다.\ 용도 : 무선 마우스/키보드, 헬스케어 센서, 가정용 보안장치 등 IEEE 802.15 WPAN (WLAN보다 조금 더 근거리에서..

▶1517 - 버블 소트 ▶문제 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오. 버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다. ▶입력 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. ..

▶11000 - 강의실 배정 ▶문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충 한 게 찔리면, 선생님을 도와드리자! ▶입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) ▶출력 강의실의 개수를 출력하라. ▶풀이 heapq를 만들어서 문제를 풀었다. 그때그때 강의실 중 가장 빨리 끝나는 강의실을 찾아 그 강의실이 끝..