리프 노드에서 시작해 올라가면서 생각하면 된다. 리프 노드는 하나의 노드와 연결되어 있고, 리프노드를 켜는 것보다는 부모 노드를 켜는것이 유리하므로 리프 노드의 부모 노드는 반드시 켜져야 한다. 같은 원리로 불이 켜진 노드의 부모 노드는 가능하면 꺼져 있어야 켜진 등대

2중 for문과 누적합 배열을 통해 해결해보려 하였는데 cookie의 사이즈가 최대 2천이므로 시간초과가 날것이 분명했다.그다음 생각한 방법은 이분탐색이었다. 다만 cookie 배열 내의 값은 정렬이 되지 않은 형태라 이분탐색을 바로 적용할 수 없었다.하지만 누적합 배

분할 정복을 이용해서 풀었다.핵심은 처음 (n^s)\*(n^s) 크기의 사각형에서 n\*n등분으로 쪼개가며 쪼개진 사각형 안에 (r1,c1) ~(r2,c2) 의 범위가 속하는지 체크하며 진행하는 것이다. 쪼개진 사각형의 왼쪽 위 좌표를 (x1,y1) 오른쪽 아래 좌표를

ㅎㅎ..;;

BFS + 우선순위 큐로 해결했다.(0,0) 에서 시작해 사다리 설치 없이 방문할 수 있는 모든 지역을 방문한다.방문할 수 없는 지역은 필요한 비용과 함께 우선순위 큐에 넣어준다.사다리 설치 없이 방문할 수 있는 지역을 모두 방문하고 나면 우선순위 큐에서 비용을 가장

문제 풀이 무작위 두 사람의 순위 관계가 주어지고, 전체 사람의 순위에 대한 질문을 묻는 문제. 플로이드 와샬로 해결할 수 있는 대표적인 문제이다. 플로이드 와샬 알고리즘은 3중 반복문을 통해 각각 x번 노드가 y번 노드를 거쳐서 z번 노드로 갈 수 있는지에 대한

문제 풀이 좌표(말뚝)의 최대 개수가 5000이므로 이중 반복문을 통해 개수를 세어도 시간초과가 나지 않을 것이라 생각했다. 텐트 설치를 위해서는 다음 조건을 지켜야 한다. 조건 1. x좌표가 같거나 y좌표가 같으면 설치 X 조건 2. x좌표와 y좌표로 만든 직사각형 내부에 다른 말뚝 X 이 조건들을 지키기 위해 먼저 좌표를 정렬해 주었다. 그 후 이...

문제 풀이 나는 세그먼트 트리를 이용해 풀었다. 세그먼트 트리의 a~b구간에 있는 모든 노드가 false 라면 false를 리턴하도록 구성하였다. 일반적인 세그먼트 트리의 Sum 연산은 left 와 right 안에 start, end 범위가 포함되면 바로 return을 해주지만 이 문제에선 start ~ end 사이의 모든 노드가 false인 경우만 ...

문제 풀이 두 썩은 사과를 잘라내기 위해 가지를 잘라내되, 떨어지는 사과의 개수를 최소로 한다는 것은 두 썩은 사과의 최소 공통 조상을 찾아내라는 의미이다. 즉, LCA 알고리즘을 적용시키면 된다. 단, 이 문제에서는 문자열을 가지고 Tree를 생성하는 과정을 요구하고 있다. Tree 생성 1) 스택 사용 0인 경우 level이 더 높아지고, 1인 ...

1. 정규 표현식 정규 표현식은 문자열 처리를 위한 문법이다. 패턴에 따라 문자열을 검색하거나 교체할 수 있으므로 문자열을 효율적으로 처리할 수 있다. 2. 사용법 ( C++ ) c++에서 정규표현식을 사용하기 위해서는 헤더를 불러와서 사용해야 한다. 2-1. 정

문제 풀이 큐를 이용한 구현 문제 4개의 큐를 만들고 각 큐에 차량의 진입 시간과 교차로 정보를 모두 넣어둔다. cur 이라는 시간변수를 가지고 시간의 흐름에 따라 시뮬레이션 하면서 움직일 수 있는 차들을 움직여준다. t의 범위가 10억이므로 모든 교차로에서 차가 아직 들어오지 않은 경우는 시간을 4개의 교차로중 가장 빨리 들어오는 차의 시간으로 당...

풀이 냅색 알고리즘을 이용해 해결했다. 화살의 개수 = 무게 과녁의 점수 = 가치 에 대입해보면 냅색 알고리즘을 적용할 수 있다. 하지만, 주의할점은 이미 피치가 맞춘 과녁의 점수는 점수의 가치가 두배라는 점이다. (피치는 얻을 점수를 얻지 못하고 라이언이 그 만큼의 점수를 얻기 때문) 또, 냅색에 경로 추적까지 필요하다. 최종 점수가 어떤 과녁을 맞...

문제 풀이 크게 두 가지 작업으로 나뉜다. 정규식을 통한 문자열 체크 백트래킹을 통한 유저아이디와 차단아이디의 매칭 나누어서 살펴보면 먼저 차단당한 아이디들의 * 문자를 . 문자로 바꾸고 ^와 $를 앞뒤에 붙여줌으로써 정규식에 사용하기 편한 형태로 바꿔준다. 그 후 백트래킹 과정에서 match를 통해 사용자의 아이디와 차단당한 아이디

풀이 크게 두 가지 작업으로 나뉜다. 백트래킹을 이용한 팀 나누기 나눠진 팀에 대해 각각 포인트 계산 및 반환 백트래킹 알고리즘에 대해 이해하고 있다면 큰 어려움 없이 해결할 수 있는 문제이다. 소스코드 후기 team2 의 멤버를 구하기 위해 사용한 indexOf의 시간복잡도가 O(N) 인데 모든 멤버에 대해 사용하므로 최악의 경우 대략 20*20 ...

https://www.acmicpc.net/submit/2141/42113933정렬+그리디마을에 대해서가 아니라 각 마을에 존재하는 사람들에 대해 우체국이 최적의 위치에 있어야 한다는 점을 유의하자. 따라서 마을마다 가중치가 서로 다르다.최적의 우체국 거리는

1. Promise.all Promise.all() 메서드는 순회 가능한 객체에 주어진 모든 프로미스가 이행한 후, 혹은 프로미스가 주어지지 않았을 때 이행하는 Promise를 반환한다. 주어진 프로미스 중 하나가 거부하는 경우, 첫 번째로 거절한 프로미스의 이유를 사

실전프로젝트 5주차 실전 프로젝트 5주차가 마무리 되었다. 이번주는 기능 구현을 마무리하고 서비스를 런칭하는 주차였다. 또, API 개선 작업을 계속해서 진행했다. 랭킹 API 개선 작업이 이루어졌다. 원래 redis를 통해 캐싱을 하려고 했는데 redis 를 바로 적용하기에 시간이 부족해 다른 방법으로 성능 개선을 시켰다. User 컬렉션에 착용한 아...

0. 사전 준비 1) IAM 사용자 권한 설정 AWS Lambda 서비스를 사용하기 위해 해당 사용자에게 Lambda 권한을 주어야 한다. 사용자 -> 권한추가 -> AWSLambdaFullAccess 를 추가해야 한다. 사진 업로드도 해야 하므로 S3FullAc

Nginx + https 적용해보기 1. Nginx 설치 2. nginx 서버 블록 설정 nginx 설정 파일 수정 http {} 블록 끝에 구문 추가 include /etc/nginx/sites-enabled/*.conf; // sites-enabled 디렉

1. 실전프로젝트 3주차 실전 프로젝트 3주차가 마무리 되었다. 이번주에는 Jest 공부를 끝내고 테스트 코드를 본격적으로 작성했다. 32개의 API 에 대해 성공하는 케이스만 작성했는데도 천줄이 훌쩍 넘는 분량이 나왔다.. 실패 케이스에 대한 부분도 작성하고 싶지만