문제https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이모든 노드를 y좌표가 큰 순 - y좌표가 같다면 x좌표가 적은 순으로 정렬한다. - 트리를 이루는 순서대로 정렬정렬된 노드를 하나씩 트리에 삽입한다. 이 때, x좌표를 키로 하는 이진 검색 트리의 삽입 알고리즘을 따른다.완성된 트리를 전위순회, 후위순회하여 정답을 도출한다.트리를 이루는 순서대로 정렬한다는 의미는, nodeinfo로 주어지는 1-2-3-4-5-6-7-8-9 순서의 노드들을위 그림의 7-4-2-6-1-3-9-8-5 순서대로..

문제 상황현재 redux 모듈 디렉토리 구조입니다. 일단 보자마자 article 안에 왜 articles과 editor가 또 있는거지?..  싶고요 ㅎㅎ그리고 domain별로 디렉토리가 나누어져있지만 auth, user 디렉토리 안에는 ducks 패턴으로 작성된 파일이 있고, 나머지는 Type, Action, Reducer, Saga 파일이 전부 나누어져있는 짬뽕 구조입니다. (해맑게 웃는다)  이 외에도 파일 구조 상 정형화 되지 않은 부분들이 많아서 이를 좀 정리 해볼까 합니다.정리 좀 해볼까요 ..1. Redux 상태 사용, 기능별로? 데이터별로?현재 프로젝트에서는 글을 조회하여서 article 데이터를 받아오는 로직이 서로 다른 기능에서 중복 되고 있는 상황입니다. 즉, 같은 데이터 구조의 데이터..

플로이드-워셜(Floyd-Warchall) 알고리즘가중 그래프에서 모든 노드 쌍들에 대한 최단 경로를 구할 때 사용하는 알고리즘이다.가중치가 음/양수일 때 모두 사용 가능하다. 알고리즘 동작모든 vertex쌍 간의 최단 경로를 갱신하여야 하므로 인접 행렬을 사용한다.정점 A에서 B로 가는 경로에서 거칠 수 있는 모든 노드(K)을 확인하여 해당 노드(K)를 경유할 경우 경로 길이가 더 짧아진다면 그 값을 테이블에 갱신한다. (D[i,j] = min( D[i,j] , D[i,k]+D[k,j])3중 for문을 사용한다. (D[i,k]와 D[k,j] 에서 공통인 중간점 k를 가장 바깥 for문으로 둔다.)만일 dist[i][i] 음수 사이클이 존재한다는 의미로, 최단 거리 테이블을 확정할 수 없다.구현 방법인..

벨만-포드(Bellman-Ford) 알고리즘가중그래프에서 특정 하나의 노드에서 다른 모든 노드로의 최단 거리 정보를 알아내는 알고리즘이다. (단일 출발)모든 경우의 수를 고려하기 때문에, 다익스트라 알고리즘보다 시간복잡도가 높다.그렇지만 다익스트라 알고리즘과 달리 노드 간의 간선 가중치가 음수인 경우에도 사용할 수 있다. 알고리즘 동작 방식매 단계(cycle)마다 모든 노드(vertex)를 방문한다.하나의 노드를 방문할 때마다 이 노드와 인접한 다른 노드들을 확인하여, 최단 거리 테이블을 갱신한다. 단계는 최단 거리 테이블이 더이상 업데이트되지 않을 때까지, 최대 V-1번 반복된다. (V: vertex, 노드의 수)만일 V-1번의 단계를 거친 이후에도 최단 거리 테이블이 업데이트 된다면, 이는 음수 사이..

다익스트라(Dijkstra) 알고리즘가중그래프에서 특정 하나의 노드에서 다른 모든 노드로의 최단 거리 정보를 알아내는 알고리즘이다.음수 가중치를 갖는 간선을 포함한 그래프에서는 올바르게 동작하지 않는다. (음수 가중치가 있을 경우 최단 경로가 계속 갱신될 수 있기 때문에)구현 특징문제를 그래프로 표현하여 각 정점 연결 상황을 저장한다.정점 간 최단 거리 정보(distance)를 1차원 리스트에 저장하며 리스트를 계속해서 갱신한다.매 단계마다 아직 방문하지 않은 정점 중 최단 거리인 정점을 찾아 방문하여 최단거리를 확정하고, 이를 반복하는 방식이다.방문하지 않은 정점 중에서 최단 거리가 최소인 정점을 찾는 과정에서 Heap, Priority Queue를 이용한다.구현 방법출발 노드(s) 설정최단 거리 테이..

문제 상황Node.js(+express)에 AWS S3를 연결하면서 .env 파일에 다음과 같이 환경변수를 추가하였다. # AWS S3AWS_ACCESS_KEY=비밀AWS_ACCESS_SECRET_KEY=비밀AWS_REGION=ap-northeast-2AWS_S3_BUCKET_NAME=비밀 그리고 이 환경변수를 s3 configuration 파일에서 읽어와야 하는데, 제대로 읽어오지 못 해서 계속해서 undefined로 값이 들어가는 상황이 발생하였다. 문제의 파일 's3Client.js'import { S3Client } from '@aws-sdk/client-s3';const s3 = () => new S3Client({ region: process.env.AWS_REGION, credential..

배경프로젝트를 진행하면서 OAuth2를 사용하여 소셜 로그인(Naver, Kakao, Google)을 구현하게 되었다.이전 졸업 작품 등에서도 OAuth2로 소셜 로그인을 구현한 경험은 있지만, 전부 Java/Springboot를 이용하여 구현하여서 Express를 사용하여 구현한 것은 처음이었다!그치만 Springboot에서 Express로의 변경에 의해 야기된 큰 차이점은 없었다. 단, 이번에 OAuth2 로그인을 구현하면서 고려해야할 점은 다음과 같았다.닉네임(nickname) 정보가 반드시 필요하다.닉네임이 unique값이어야 한다. (즉, 겹치면 안 된다.)그런데, 다음과 같은 문제가 있었다.Provider로부터 얻어온 정보에 닉네임 정보가 없는 경우가 존재한다.얻어온 닉네임의 unique함이 ..

투포인터 알고리즘의 정의투포인터 알고리즘(Two Pointers Algorithm) 혹은 슬라이딩 윈도우(Sliding Window)라 부른다.알고리즘 문제 중 완전 탐색으로 풀면 시간초과가 나는 문제일 때, 투포인터 알고리즘을 떠올려 보아야 한다.투포인터 알고리즘에는 1차원 배열이 있고, 이 배열에서 서로 다른 두 개의 포인터를 이용해 원소에 접근하며 원하는 것을 얻는다. 원래 이중 for문으로 $O(N^2)$에 처리되는 작업을 2개의 포인터를 이용하여 $O(N)$에 해결하는 알고리즘이다.예시크기가 N인 1차원 배열 arr가 있다. 이 때 arr의 부분 배열 중 그 원소의 합이 M이 되는 경우의 수가 몇 개 인지를 구해보자.이를 완전 탐색으로 모든 경우의 수를 전부 테스트하는 것은,  $O(N^2)$의..

인접리스트로 구현된 그래프에서의 구현 package graph; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class ListGraph implements Graph{ int size; boolean directed; LinkedList[] adj; LinkedList[] inv; public ListGraph(int size, boolean directed) { this.size = size; // vertex의 수 this.directed = directed; // true: 방향성 그래프, false: 무방향성 그래프 adj = new ..

그래프의 정의그래프는 연결되어 있는 원소 간 관계를 표현하는 자료구조이다.실세계의 지하철 노선도, 컴퓨터 네트워크 등의 예를 생각하면 된다.그래프의 구성 요소 그래프는 vertex(정점)과 정점들을 잇는 edge(간선)으로 구성된다.위 사진에서 0,1,2,3,4가 정점에 해당하고, 정점을 잇는 선이 간선이다. 그래프 G가 있을 때, G에 포함된 모든 정점들의 집합을 V(G), 모든 간선들의 집합을 E(G)라고 표기한다.G = (V,E)라고 쓰기도 한다. 그래프의 종류그래프는 무방향성 그래프와 방향성 그래프로 나뉜다.무방향성 그래프무방향성 그래프는 각 vertex가 서로 연결됐음만을 나타내는 그래프이다.이 때 vertex 0과 1에 대해서 (0,1)과 (1,0)는 동일한 ..

누적합 알고리즘의 정의 누적합 알고리즘은 말 그대로 어떠한 구간의 누적된 합을 구하는 알고리즘이다. 수열 \(A_n\)에 대하여 특정 인덱스 a에서 b까지의 구간 합을 구하는 알고리즘이라고도 볼 수 있다. 예시 [ 1,2,3,4,5 ] 로 이루어진 크기가 5인 배열 arr가 있다. 이 때 arr[1] 부터 arr[3]의 구간 합을 구해보자. (방법 1) 가장 쉬운 방법으로, 2부터 4까지 인덱스를 하나씩 증가시키며 배열을 방문하여 요소들을 더한다. 1 1+2 1+2+3 = 6 만일 배열의 처음부터 해당 인덱스까지의 합을 나타내는 배열 [ 1,2,6,10,15 ]을 구하려고 하면 어떨까? 1 1+2 1+2+3 1+2+3+4 1+2+3+4+5 위를 보면 알 수 있듯이, 0을 제외한 모든 인덱스에서 자신 이전..

힙의 정의 A Heap is a special Tree-based data structure in which the tree is a complete binary tree. 힙은 트리, 그 중 완전 이진 트리를 기반으로 한 자료구조이다.힙이 되기 위해서는 완전 이진 트리이면서, 부모 노드가 가진 데이터 값은 자식 노드가 가진 데이터 값보다 무조건 크거나(이 경우 Max Heap), 혹은 작아야(이 경우 Min Heap) 한다.  위 사진을 보면, Max Heap의 경우 모든 부모 노드는 자식 노드보다 데이터의 값이 크고 Min Heap의 경우 모든 부모 노드가 자식 노드보다 데이터의 값이 작은 것을 확인할 수 있다. 따라서 루트 노드에 Min Heap의 경우 항상 트리의 최솟값이, Max Meap의 경우..