KBW's cosmos

처음에는 백트래킹으로 접근하려고 했다. """ 1. 아이디어 - 백트래킹으로 탐색하며 벽을 뚫을 때와 안뚫을 떄를 구분하여 전체 가지수를 탐색한다. 2. 시간 복잡도 - O(N * M) : 1000 * 1000 = 1,000,000 -> 가능 3. 변수 - N, M : int - map : int[][] - visit : bool[][] """ import sys sys.setrecursionlimit(10 ** 6) INF = sys.maxsize input = sys.stdin.readline N, M = map(int, input().split()) map = [list(map(int, input().rstrip())) for _ in range(N)] visit = [[False] * M for ..

처음에는 플로이드로 풀었다. """ 1. 아이디어 - 플로이드로 전체 마을 사이의 최단 경로를 구한다. - 이중 for문으로 도로의 길이의 합이 가장 작은 사이클을 찾는다. 2. 시간 복잡도 - O(V^3 + V^2) : 400 ^ 3 ~= 6억 3. 변수 - V, E : int - dist : int[][] - min_dist : int """ import sys INF = sys.maxsize input = sys.stdin.readline V, E = map(int, input().split()) dist = [[INF] * (V + 1) for _ in range(V + 1)] for l in range(1, V + 1): dist[l][l] = 0 for _ in range(E): a, b, c..

최초의 풀이는 조금 복잡하게 접근하였다. """ 1. 아이디어 - 백트래킹으로 전수를 조사한다. - for문을 돌릴 때 마지막으로 선택한 선수보다 높은 번호의 선수들을 대상으로 한다. - 전체를 대상으로 돌리는게 아니라 N/2만큼 돌린다. (대칭이므로) - 깊이가 N/2에 도달하면 선택한 팀 구성을 대상으로 각각 팀의 능력치를 구한다. - 비교하여 현재 갖고 있는 최소값보다 작으면 교체한다. 2. 시간 복잡도 - NCN/2 * (N ** 2) = (N! / ((N - N/2)! * (N/2)!)) * (N/2 ** 2) ~= 70,000,000 -> 가능 3. 변수 - N : int - S : int[][] - 선택한 팀원 리스트 : int[] - 능력치 차이 최소값 : int """ import sys..

""" 1. 아이디어 - 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간 -> 다익스트라 2. 시간 복잡도 - O(ElgV) : 6000 * lg(500) ~= 16000 -> 가능 3. 변수 - N, M : int - 인접 리스트 : (이동 시간, 도착 도시)[][] - 최단 거리 배열 : int[] - 갈 수 있는 도시들 : heap """ import sys import heapq INF = sys.maxsize input = sys.stdin.readline N, M = map(int, input().split()) edge = [[] for _ in range(N + 1)] for _ in range(M): A, B, C = map(int, input().split()) edge[A]..

사실 이 문제를 볼 때 부분 수열을 만들 때 기존 수열의 순서를 그대로 따라야하는지가 헷갈렸다. 하지만 그렇다면 그냥 set으로 중복을 제거하고 수를 구하면 될 것이다... 그래서 아마 이것은 아니겠지 하고 풀었다. 처음에는 완전 탐색으로 풀 생각을 했다.. """ 1. 아이디어 - 가장 작은 수 하나를 구한다 - 이후 뒤 수열을 for문으로 돌며 큰 수를 찾는다. 2. 시간 복잡도 - 두개의 포인터 : O(N) - 전체 조회 : O(N^2) = 1,000,000 -> 가능 3. 변수 - N : int - A : int[] """ import sys input = sys.stdin.readline N = int(input()) A = list(map(int, input().split())) max_len..

""" 1. 아이디어 - 우선 반드시 지나야 하는 두 정점 사이의 최소 거리를 구한다. (다익스트라) - 그리고 1번 정점과 v1, v2 / N번 정점과 v1, v2 사이의 거리를 구한 뒤 더 짧은 거리를 선택한다. 2. 시간 복잡도 - O(3 * ElgV) = 5 * 200000 * lg(800) =~ 2,903,089 -> 가능 3. 변수 - 정점의 개수, 간선의 개수 : int - 힙 : (비용, 노드번호) - 거리배열 : int[] - 인접 간선 리스트 : (비용, 노드번호)[] """ import sys import heapq INF = sys.maxsize input = sys.stdin.readline N, E = map(int, input().split()) edge = [[] for _ ..

CDN, CDN 자주 들어봤는데 간단하게만 이해하고 명확히 그 개념을 알지 못했다. 이번 포스팅을 통해 CDN에 대해 자세히 알아보도록 하겠다! CDN (Content Delivery Network) CDN은 Content Delivery Network의 준말로 직역하면 콘텐츠를 전달하는 네트워크라는 의미이다. CDN은 웹페이지, 이미지, 동영상 등의 콘텐츠를 서버에서 사용자로 전달한다. 그런데, 그런 것들은 이미 인터넷망을 통해 이미 전달되고 있지 않은가? 그렇다면 CDN은 왜 필요한 것일까? CDN은 왜 필요할까? 분명히 CDN 없이도 서비스들은 동작한다. 먼저 일반적인 클라이언트와 서버의 통신을 생각해보자. 누군가 어떠한 사이트에 접속한다는 건 해당 사이트를 제공하는 서버 컴퓨터에 방문자의 컴퓨터가..

로그인을 구현한다면 꼭 알아야 할 개념들이다. 이번에 프로젝트를 진행하면서 Next-Auth를 사용해 소셜 로그인을 구현했는데, 이때 공부한 내용들과 실제 프로젝트에서 사용한 인증, 인가 방법에 대해 소개하겠다. 쿠키(Cookie)란? 먼저 쿠키다. 쿠키는 사용자를 기억하기 위해 서버가 사용자의 브라우저에 저장하는 데이터(작은 기록 정보 파일)라고 할 수 있다. 사용자가 사이트에 방문하면, 1. 브라우저는 서버에 요청(request)을 보내고 2. 서버는 응답(response)한다. 이 응답에는 사용자가 찾던 페이지 정보, 데이터뿐만 아니라 브라우저에 저장하고자 하는 쿠키가 있을 수 있다. 이 쿠키를 브라우저에 저장하게 되면, 사용자가 해당 웹 사이트를 방문할 때마다 브라우저가 자동으로 해당 쿠키를 요청..

개발하면서 자주 사용하였지만 개념적으로 잡힌 느낌은 아니여서 포스팅하며 정리하고자 한다. 콜백함수 정의 : 함수에 파라미터로 들어가는 함수 콜백함수 용도 : 순차적으로 코드를 실행하고 싶을 때 사용 먼저 addEventListener를 보겠다. document.querySelector('.button').addEventListener('click', function(){ }) 해당 함수를 사용할 때 콜백함수를 집어넣게 되어있다. addEventListener도 함수인데 파라미터 자리에 또 하나의 함수를 집어넣고 있다. 이것을 콜백함수라고 한다. setTimeout에서도 마찬가지다. setTimeout(function(){ }, 1000) 안에 콜백함수를 집어넣게 한다. 그렇다면 함수안에 함수를 넣으려면 ..

디자인 패턴이란? - 과거 소프트웨어 개발 과정에서 발견한 설계 노하우를 패턴으로 정리한 것을 말한다. 장점 1. 코드 스타일이 비슷해진다 -> 의사소통을 효율적으로 할 수 있다. 2. 이미 검증된 구조이므로 설계를 빠르게 할 수 있다. 디자인 패턴은 목적에 따라 크게 세 가지로 나뉜다. 1. 생성 패턴 2. 구조 패턴 3. 행동 패턴 이 중 생성 패턴에서는 싱글턴, 팩토리 메서드, 구조 패턴에서는 어댑터, 행위 패턴에스는 템플릿 메서드를 알아보겠다. 1. 싱글톤 패턴 (생성 패턴) - 인스턴스를 오직 1개만 생성하는 패턴 A, B, C라는 클래스가 있다고 하자. 이때 A, B, C 클래스에서 각각 D라는 클래스가 필요해 가져다 쓴다면 메모리에 같은 객체가 3개 생기게 된다. 만약 각각이 다른 정보, 다..