다익스트라 알고리즘최단 거리를 구하고자 하는데 거리가 일정하지 않다면 다익스트라를 생각하면 된다.또한 중요한 한가지는 음수 길이의 간선이 존재하지 않을 때 사용하면 좋다. 1. "최단 거리 개발 중"에서 최단 거리가 가장 작은 노드를 "최단 거리 확정"으로 옮긴다.2. 옮긴 노드와 연결 된 "최단 거리 개발 중"에 포함된 노드의 최단거리 연산 및 업데이트를 진행한다.=> 이때 "최단 거리 개발 중"은 우선순위 큐를 이용하여 weight의 최솟값을 뽑아내야한다. 다익스트라 알고리즘의 골조1. adj 생성(그래프 생성)2. Dijk[] 의 값을 INF로 초기화 한다. ( INT_MAX )3. 처음 시작 노드 pq(priority queue)에 삽입, Dijk[start] = 0으로 초기화4. while 문을..

그래프 탐색두 노드가 연결되어 있는지 여부를 확인하고 싶을 때 그래프 탐색을 활용하면 쉽게 해결이 가능하다. 그래프를 탐색하는 알고리즘은 1. 현재 노드를 방문 완료 체크하기(이 순서가 빠진다면 그래프 탐색 시 무한루프를 돌며 이미 방문한 노드를 무한정 재방문 하는 오류가 발생할 수 있다.)2. 현재 노드와 연결된 노드를 " 도달 가능한 노드 목록"에 추가한다.(" 도달 가능한 노드 목록"에 사용하는 알고리즘에 따라서 DFS/BFS로 알고리즘이 나뉜다.)3. "도달 가능한 노드들의 목록" 에 존재하는 노드 중 방문하지 않았던 노드를 찾아서 방문한다. BFS/DFS의 차이학교 수업 시간 혹은 알고리즘 강의를 들으며 수업이 두개의 차이를 많이 들었지만코딩 테스트에서 가장 직관적으로 와닿았던 내용을 정리하자면..

들어가기에 앞서 cost 계산 시 사용되는 변수 k, 즉 data entry를 정의하고자 한다.인덱스를 사용해서 data entry를 저장하는 방법에는 총 3가지가 존재한다. 1. 인덱스에 data record를 포함하는 방법    빠른 엑세스가 가능하지만 인덱스의 크기가 너무 커져서 비효율적이다.2. 인덱스의 키(k)를 찾고자 하는 data record의 rid(record id 혹은 실제 저장된 위치(페이지번호, offset))에 매칭하는 방법    인덱스 크기를 줄일 수 있지만 중복값이 여러개 발생할 수 있다.3. 인덱스의 키(k)에 rid를 list 형태로 저장하는 방법    중복값이 여러개 발생하는 문제를 해결하여 저장되는 크기를 더욱 줄일 수 있음 여기서 cost 계산 시에는 일반적인 데이터베..

기본 설정으로 데이터베이스는 UTC 시간대를 따르고 있다.국내에서 서비스하는 데이터베이스를 위해서는 KST로 시간대 변경이 필요하다. 보통 createdAt으로 데이터 입력 시간을 관리하고, updatedAt 으로 데이터 변경 시점을 관리하기 때문에 이 시간대 설정이 매우 중요하다!! 데이터베이스의 시간대를 변경하는 방법을 알아보자!    1) sql문으로 적용하기SET GLOBAL time_zone='Asia/Seoul';SET time_zone = 'Asia/Seoul'; 2) data grip에서 간단하게 적용하기 데이터베이스 명 > Properties > options에서 TimeZone을 설정하면 된다!! 그러면 기존에 현재 시간보다 9시간 빠르게 적용되던 데이터가 정상적인 한국시간으로 적용되는..

내가 원하는 환경은 local에서 돌릴 때는 local에 설치된 데이터베이스를 활용해서 테스트를 진행하고,이후 prod 환경에서는 private subnet에서 사용하고 있는 데이터베이스와의 연동을 통해 돌아가도록 개발환경을 수정하고자 했다. 이 환경분리가 가장 필요했던 이유 중 하나로는 데이터베이스가 현재 private subnet에 배포되어 있어서 같은 subnet에서 요청하는 connection만 인식이 가능했다.따라서 로컬 환경에서 테스트하고 실제 배포는 prod DB와 연동해서 배포할 수 있도록 환경을 구축하는 것의 필요성을 느껴 이 글을 작성한다.   문제 해결과정은 다음과 같다.1) root 역할을 하는 application.yml 파일 설정2) application-local.yml, ap..

총 3가지의 step으로 문제를 해결하고자 했다. 1) 벽을 세울 수 있는 모든 경우의 수 탐색 - 3개의 벽을 세우는 것이므로 combination 을 활용하자2) 벽을 세웠을 때 바이러스 퍼트리기 - dfs를 활용해보자3) 맵을 전체적으로 훑으면서 바이러스가 퍼지지 않은 안전 지역을 찾자 trouble shooting2 단계를 구현할 때 처음에는 바이러스가 퍼진다면 이걸 Map에 반영하여 2로 바꿔주도록 코드를 구현하였으나다시 map을 초기화하는 과정이 한번 더 들어가면서 코드가 복잡해짐과 동시에 오래걸린다는 것을 알게되었다.(그래서 temp_map을 두고 할당 받는 방식을 생각했으나 결국 같은 메모리를  참조하는 것이지 복사하는게 아니라서 동일한 문제가 발생함!) 따라서 바이러스가 퍼진다면 isVi..

오늘의 문제는 이분 탐색!! import sys#sys.stdin = open("input.txt", "r")n = int(input())arr = list(map(int, input().split(" ")))target = int(input())arr.sort()answer = -1start = 1end = arr[-1]while start target: end = mid - 1print(answer)

1편에 이어서 카카오톡 소셜로그인을 구현하려고 한다. Frontend : html Backend : Spring (✅) frontend 편으로 Client에서 kakao Server에 카카오 로그인을 요청하는 것까지 html을 이용해서 구현해두었다.이제 kakao Server에서 redirect url을 보내는 단계부터 차근차근 처리하는 로직을 소개하겠다!    이 그림이 내 서버 구조도, 다이어그램이 되고 단계별로 진행하려고 한다. 기본적인 api 서버의 동작 순서는 아래와 같다.Request -> Route ->  Controller -> Service/Provider -> DAO ->  DB redirect uri로 kakao server는 code를 전달해준다.이때 redirect uri 는 ka..

오늘 해결한 문제도 정말정말 간단하게 pop 연산을 활용해서 온전한 괄호의 매칭 여부를 확인해주기만 하면 되는 문제였다!! import sysfrom collections import deque#sys.stdin = open("input.txt", "r")while True: s = input() if s == ".": break s = list(s) flag = 0 q1 = deque() q2 = deque() for ss in s: if ss == "(" or ss == ")" or ss == "[" or ss == "]": q1.append(ss) while q1: ns = q1.pop() ..

오늘의 문제 완료!~!import sys#sys.stdin = open("input.txt", "r")N = int(input())mapp = [list(map(str, input())) for _ in range(N)]def quard(y, x, size): tmp = mapp[y][x] if size == 1: return tmp ret = "" for i in range(y, y+size): for j in range(x, x+size): if tmp != mapp[i][j]: ret += "(" ret += quard(y, x, size//2) ret ..

오늘 해결한 문제는 DFS를 이용하면 간단히 해결할 수 있는 문제였다! def solution(n, computers): isVisited = [False] * n answer = 0 def DFS(computers, n, point): isVisited[point] = True for i in range(n): if computers[point][i] == 1 and isVisited[i] == False: DFS(computers, n, i) for i in range(n): if isVisited[i] == False: DFS(compute..

오공완!!이 문제를 보면서 컴파일러 수업 때 배웠던 정규식의 악몽이 떠올랐는데... import sys#sys.stdin = open("input.txt", "r")n = int(input())pattern = input()isFront = 0pos = 0for i in range(len(pattern)):    if pattern[i] == "*":        pos = ifront_s = pattern[0:pos:]back_s = pattern[pos+1::]len_s = len(front_s)len_b = len(back_s)# front_s = "".join(s for s in front)# back_s = "".join(s for s in back)for i in range(n):    ss ..