삼성 알고리즘에서 배웠던 것들 조금 고급이나 많이 접해보지 못한 것들 알고리즘이랑 자료구조들 공부해봅시다. 그래프란? 그래프는 노드랑 간선으로 이루어진 자료구조이고 순환 구조가 없는 걸 트리 자료구조라고 할 수 있음. 간선에 방향이 존재하는지 여부가 중요하니까 잘 파악할 것. 기본적인 DFS나 BFS는 많이 접해봤으니까 덜 접해본 알고리즘들을 공부해보자. 서로소 집합 (Union-Find) 오늘 풀었던 문제에서도 나왔는데 집합을 이루는지 확인하고 하나의 집합으로 만들 수 있는 그런 알고리즘. Union 연산 (합집합) 어떤 두 원소 a, b에 대해서 각 원소가 속한 집합을 하나로 합치는 연산임. def union(a, b): parentA = find(a) parentB = find(b) if paren..

💡https://www.acmicpc.net/problem/1300 문제 설명 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 입력 첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다. 출력 B[k]를 출력한다. 문제 풀이 해당 문제를 처음 보고 든 생각은 n의 값이 너무 크기 때문에 직접 정렬을 하는 방식을 이용할 수 없을 것 같다라는 생각이 들었습니다. 정렬을 한다면 메모리와 시간적으로 모..

💡https://school.programmers.co.kr/learn/courses/30/lessons/152995 문제 설명 ※ 문제에 대한 자세한 설명은 위 링크를 참조해주세요! 일단 해당 문제에서 찾아야 하는 것은 완호의 랭킹입니다. 그리고 이 랭킹을 알기 위해선 인센티브를 받을 수 있는지 여부가 모든 값들에 대해서 알아야 합니다. 현 시점에서 가장 간단하게 생각하면 모든 노드를 돌면서 해당 노드가 인센티브를 받을 수 있는지 여부를 체크하고 완호가 인센티브를 못받는 사람을 제외하고 자기보다 더 큰 사람의 수를 센다면 랭킹을 구할 수 있겠죠. 하지만 주어진 scores의 크기가 10만이기에 O(N^2)에 해당하는 알고리즘을 사용할 수 없습니다. 최대 O(NlogN) 정도로 풀어줘야합니다. 이때 잘 ..

💡https://gnuoyus.tistory.com/103 에서 발생했던 문제의 이유에 대해서 그냥 내 생각을 써보고 어떻게 해결할 수 있었는지도 생각해보기. HTTP 1.1 vs HTTP 2.0 앞선 글에서 설명했던 HTTP 2.0은 1.1의 성능을 향상 시키고 개선한 프로토콜입니다. HTTP 1.1의 문제점은 아래와 같습니다. 1. HOL Blocking 2. Header가 너무 무겁다. HOL Blocking HTTP 1.1을 이용할 때 HOL Blocking이라는 문제가 발생한 이유는 하나의 연결에서 더 많은 데이터를 주고 받고 싶은데 이를 해결하기 위해서 pipelining을 이용했기 때문입니다. 그럼 pipelining이 뭘까요?? 특정 명령어를 여러 개로 나누어서 단계별로 나누고 중첩적으로 ..

💡https://www.acmicpc.net/problem/17484 문제 설명 ※ 문제에 대한 세부 내용은 위 링크를 통해 확인해주세요! 지구와 달 사이의 격자형 루트를 따라서 움직였을 때, 최소한의 연료를 쓰는 루트가는 경우 얼마의 연료가 소모되는지에 대해 알아야 하는 문제입니다. 일단 문제에서 볼 수 있는 부분이 입력 값 제한이 굉장히 작다는 생각이 들고 그래서 어떻게 풀어도 시간 제한으로 틀리는 경우는 드물 것 같다는 생각이 듭니다. 먼저, 제가 한 생각은 DP로 풀자는 생각이 들었습니다. 최소한의 연료 소모량을 구해야 한다는 부분과 이전까지 이동한 최소 연료 소모량을 이용해서 그 다음 위치에서의 최소 연료 소모량을 구할 수 있을 것 같다는 부분에서 DP를 생각했습니다. 방향이라는 제한이 없었으면..

HTTP 1.1과 HTTP 2.0 비교하기 HTTP 1.1은 HTTP 2.0의 등장 전까지 무려 15년 동안이나 유지되었습니다. 하지만 시간이 지나감에 따라 멀티미디어 리소스나 비동기 요청들이 하나의 웹 사이트에서도 굉장히 많이 발생하게 되면서 더 이상 HTTP 1.1이 버티기가 힘들었고 HTTP 2.0이 등장하게 됩니다. 그럼 HTTP 1.1에서의 문제점을 알아보고 HTTP 2.0에서 이를 어떻게 개선했는지에 대해서 알아보겠습니다. HTTP 1.1 알아보기 일단 HTTP 1.0에서는 하나의 connection을 이용해서 하나의 요청을 처리할 수 있었고 이렇게 되면 멀티미디어 리소스가 많은 상황에서 네트워크 지연이 발생하게 됩니다. 그래서 HTTP 1.1에서는 이를 해결하기 위한 하나의 방법으로 HTTP..