1. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: BINARY_SEARCH, PARAMETRIC_SEARCHN: 놀이기구 타는 아이 수, M: 놀이기구 수, rids[] = 놀이기구 별 걸리는 시간,minimum_time: 애들 전부 놀이기구에 태우는 최소 시간,remained_kid: (minimum_time -1 ) 시간에 아직 놀이기구 못 타고 남아있는 아이들의 수0️⃣ 사람 수 놀이기구 수 이면, 마지막 사람의 번호가 곧 놀이기구의 수 이므로 N 출력 후 프로그램 종료1️⃣ 아이들을 다 태울 수 있는 최소 시간 찾기 (minimum_time)2️⃣minimum_time 1분 전 시점까지 아직 놀이기구 못 탄 아이들이 몇 명인지 찾기 (remained_kid)3️⃣ rids[]를 ..

1. Parametric Search 란?최적화 문제를 여러 개의 결정 문제 + 이분 탐색으로 변환시키는 문제 접근 방법이다. 여기서 3가지 키워드가 나왔는데, 이분탐색이 뭔지는 많은 사람들이 알테니, 최적화 문제와 결정 문제에 대해 먼저 설명하고 가겠다.(1) 최적화 문제문제의 조건을 만족하는 해의 범주가 존재하고, 그 중에서 최적의 답(최소값, 최대값 등)을 구하는 문제를 말한다.Thread Knots라는 문제를 예시로 들어보면, 해당 문제는 'n개의 매듭을 성공적으로 놓았을 때, 가장 가까운 두 개의 매듭 사이의 최대 거리를 출력하라'고 요구한다.그렇다면, 여기서 가능한 해의 범주는 n 개의 매듭을 각 Thread에 성공적으로 놓는 모든 경우이고,최적의 해는 가장 가까운 두 매듭 사이의 최대 거리일..

들어올린 턱, 웃는 모습 등, 미술 선생님의 도움을 받긴 했다..^^ 여튼 내 아이디어다 ㅎ 다음엔 동화책을 써봐야겠다. 기존의 동화책들이 요즘의 가치관과 너무 멀다는 생각이 든다. 나무꾼과 선녀라던가, 그런 것들...

1. 합격 메일참여하게 되는 3번째 해커톤이었다. 지루한 취준 생활, 독서실에서 LED 빛만 세다가 합법적(?)으로 제주도에 갈 수 있는 기회를 받게 되어 너무 좋았다. 서류는 포트 폴리오, 제주도 사회에 도움되는 IT 아이디어, 내가 뽑혀야 하는 이유 3가지를 적어야 했다.구름톤에 관한 정보를 말하자면 30명만 뽑는다. 근데 여기에 지역인재 TO가 존재해서 제주도민이 아니라면, 확률이 더 낮아지는 듯 하다.프론트는 2배수, 나머지는 1배수로 6명씩 뽑는다.백엔드 개발자 6, 프론트 12명, 디자이너 6명, 기획자 6명 이렇게 온 것 같다. 그리고 현직자, 취준생, 대학생 비율도 1:1:1로 뽑은 듯 하다.2. 화요일 아침부터 시작... 부리나케 월요일 출발월요일 하루는 제주 라마단 시티 호텔에서 묶었다..

1. 벨만포드 알고리즘이란?음수인 가중치가 존재하는 그래프에서도 최단 경로를 구할 수 있게 해주는 알고리즘.1️⃣ ONE TO ALL 알고리즘: 시작점을 고르면, 해당 정점에서 모든 정점까지의 최단 경로를 구할 수 있다.2️⃣ 음수 가중치가 있어도 괜찮아: 다익스트라는 안되지?3️⃣ 음수 사이클이 존재하는지도 확인 가능: 음수 사이클이 존재한다면, 사실 하나 이상의 정점으로의 최단 경로가 $- \infty $가 되기 때문에, 최단경로를 구하는 게 무의미해짐. 따라서 최단 경로를 구하는 게 무의미한지 여부도 파악 가능!음수 사이클가중치 그래프에서 정점 A에서 시작해서 A로 돌아왔는데 가중치의 합이 음수인 경우, 해당 사이클을 음수 사이클이라고 한다.해당 예시에서는 사이클을 돌수록 출발지에서 A,B,C까지의..

1. 문제 설명 📌문제 링크문제를 보며, 찾아낸 조건은 다음 3가지 였다.1️⃣ 최소 개수의 회선을 복구하라2️⃣ 모든 서로 다른 2 대의 컴퓨터가 교신이 가능해야 한다.3️⃣ 슈퍼 컴퓨터에서 다른 컴퓨터로의 통신 최소 비용은 복구 이전과 같아야 한다.문제를 풀며 느낀 점은,3️⃣ 때문에 1️⃣은 있으나 마나 한 조건이 되었다. 3️⃣을 만족시키려면 다익스트라를 활용해서, 최단 경로를 찾아야 하고, 그 최단 경로에 사용된 회선보다 개수를 더 줄일 수 없기 때문이다. (줄이면, 어떤 컴퓨터에는 슈퍼컴퓨터가 도달하지 못한다.) 2️⃣ 또한 다익스트라를 활용하면, 최소 슈퍼 컴퓨터를 매개로 모두 교신할 수 있기에 따로 구현해야 하는 조건이 아니다. 따라서 다익스트라를 하며 거쳐가 경로를 기억하는 문제이다...

1. 문제 설명 📌문제 링크지헌과 성하의 새로운 약속 장소를 찾아주는 문제로서, 다익스트라를 통해 각자의 출발점에서 모든 정점까지의 최소 도달 비용을 구하고, 이를 통해 4가지 조건을 만족하는 약속 장소를 찾으면 된다.하지만, 출제자가 지문을 되게 모호하게 적어서, 조건의 진의가 헷갈린다.약속 장소의 조건은 다음과 같다.1️⃣ 각자의 출발점은 약속 장소가 될 수 없다.2️⃣ 둘 다 최소 비용으로 닿을 수 있는 장소여야 한다.3️⃣ 지헌이가 성하보다 먼저 도착하는 장소여야 한다.4️⃣ 위의 조건을 모두 만족하는 장소가 복수라면, 그 중 지헌이가 빨리 도착하는 장소를 고른다. (이 마저도 복수이면, 정점 번호가 빠른 것을 고른다.)이 조건을 보면,각자의 출발점이 아니면서, 지헌이가 성하보다 먼저 도착하면서..

1. 문제 설명 📌문제 링크N개의 수가 주어지는데, 이 중 하나를 택해보자. (택한 수를 E라 부르겠다.)이 E를 나머지 N-1개 중 2개를 합해서 만들 수 있으면 좋은 수라고 부르겠다.이떄 좋은 수의 개수는 몇 개 인가?2. 구현 방법 🗃️KEY WORD: 마주보는 투 포인터1️⃣ N개의 수를 arr이란 배열에 입력 받아서 오름 차순 정렬한다.2️⃣ 포인터를 3개 두어보자. 각각의 의미는 다음과 같다.E = 좋은 수가 될지 안될지 확인하는 target을 가리키는 포인터 (0부터 점점 오른쪽으로 간다.)L = N개의 정렬된 수 중 제일 좌측을 가리키는 포인터 (점점 오른쪽으로 간다.)R = N개의 정렬된 수 중 제일 우측을 가리키는 포인터 (점점 왼쪽으로 간다.) 3️⃣L과 R이 서로 만날 때 까지 ..

1. 트라이란?트라이는 트리의 일종으로서 대량의 문자열을 빠른 시간 안에 삽입, 삭제, 조회 하기 위해 고안된 알고리즘이다.2. 트라이의 원리'선두의 문자가 같은 녀석들끼리 최대한 같은 가지에 밀어 넣는다.'1️⃣ 노드 하나 = 문자 하나, 수직적으로 문자열의 문자를 하나씩 저장함2️⃣ A의 길이 B의 길이 인데, $A\subset{B}$ 인 경우, A와 B는 직계존속 (A = 부모 노드, B = 자식 노드)3️⃣ $A\nsubseteq{B}$ 인데, 둘이 같은 선두 문자를 가질 때, A와 B는 방계임 (형제 관계 이거나, 삼촌-조카 관계)이를 기초로 한 트라이의 한 형태이다. 해당 트라이에 넣은 문자열은 다음과 같다.["frodo", "front", "frost", "frozen", "frame", "..

1. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: 트라이0️⃣ 중요한 처음 세팅!: Tri 구조를 만드는데 구성요소는 다음과 같다.(a) `기본적인 자식 노드`: HashMap로 구현 (자식 알파벳 이름, 그것의 객체)(b) `lenMap`: 현재 조회 중인 문자 뒤로 부터 전부 물음표라고 쳤을 때, 그 와일드카드를 만족하는 문자가 몇 개 있는지 세는 자료구조, HashMap로 구현 (문자열의 길이, 만족하는 문자 개수)1️⃣ 입력: 문자열 그대로 받는 Tri 하나, 문자열을 뒤집어서 받는 Tri 하나씩 만들어 각각 따로 따로 입력 받음입력받으면서, 매번 LenMap의 값을 갱신한다.2️⃣ 찾기: 와일드카드 ?를 만나기 전까지, 트라이를 깊게 들어간다. 반환값이 될..

1. 운영체제에서의 메모리 구조란?RAM(주 기억 장치)이란 물리적 메모리를 논리적(가상)으로 영역을 지어 나눈 것.(1) 하드웨어에서의 메모리 구조하드웨어 메모리 계층 구조├── 레지스터│ └─ CPU 내부에 위치 (가장 빠른 메모리)├── 캐시 (L1, L2, L3)│ └─ CPU와 RAM 사이에서 자주 사용되는 데이터를 저장├── 주기억장치 (RAM)│ ├── 사용자 영역 (User Space)│ │ │ │ │ │ │ │ │ └── 커널 영역 (Kernel Space)│ │ │ │ └── 보조기억장치 (HDD, SSD) ├── 스왑 공간 (Swap Space) └── 영구 데이터 저장소저장소라는 메모리의..

1. 문제 설명 📌문제 링크문제에서 원하는 것은 A의 전화번호를 치고 있던 와중에, B의 전화번호를 완성시켜서, B로 전화가 걸리는 일이 없으면 일관성이 TRUE, 전화가 한 번이라도 걸리면 FALSE라는 뜻이다.즉 '하나의 전화번호가 다른 전화번호의 접두어가 되는지?'를 확인하라는 문제이다.2. 구현 방법 🗃️KEY WORD: TRI기본적인 트라이를 그대로 사용한 문제라 따로 부연 설명할 것이 없다. 아직 트라이에 대한 개념이 없다면, 미리 학습 하고 오시길 바란다.0️⃣ HashMap을 활용하여 전형적인 트라이 구조 트리를 구현한다. + 문자열을 삽입하는 insert 매소드를 구현한다.1️⃣ 문자열 (이하 str)을 트라이에 삽입한다.2️⃣ 만약 str을 삽입하는 도중에, 현재 조회 중인 문자가 ..

0. 목표이번 스킨은 다 마음에 들었지만, 한 가지 아쉬웠던 점이 바로, 피드의 Summary 부분 이었다.Velog와 달리 요약문을 본문의 태그에 맞게 띄어쓰기 해주지 않는다. 따라서 위 그림 처럼 모든 내용이 한 줄로 쭉 주어져서 예쁘지도 않고 가독성도 떨어진다.RSS를 활용한다면, 본문 전문과 스크립트별 태그를 받을 수 있지만, 내부 치환자로 티스토리 서버에서 직접 내용을 받아오는 것보다 속도가 현저히 떨어질 것 같다. (+ 내가 귀찮아서 그리 못하겠다.)그래서 이번 목표는 글 요약부분을 해당 글의 TAG로 바꾸기 이다.1. 티스토리 치환자 살펴보기티스토리 공홈의 태그 클라우드 치환자를 살펴보면 태그 ..

1. 문제 설명 📌문제 링크벨만 포드 알고리즘 공부하고 한 번 써보라는 견본 문제이다.주어지는 간선 정보는 모두 단방향이다.2. 구현 방법 🗃️KEY WORD: BELLMAN-FORD ALGORITHM0️⃣ 형태로 모든 간선을 저장, 최소 비용 배열인 dist [] 선언.(N: 정점의 수, M: 간선의 수, dist 배열은 Long.MAX_VALUE로 초기화)1️⃣ 출발지를 1로 설정하고, N-1만큼 모든 간선을 돌면서 다음 구문을 실행한다.1️⃣-1) 현재 조회중인 간선의 출발지를 A, 도착지를 B, A➜B의 가중치를 C라고 할 때,dist[A] != ∞︎︎ && dist[B] > dist[A] + C이면, dist[B] = dist[A] + C로 최신화 해준다.2️⃣ 위 과정을 끝낸 후, 벨만 ..

1. 문제 설명 📌문제 링크가중치 양방향 그래프가 주어질 때, 출발지에서 도착지 까지 한번의 이동으로 가져갈 수 있는 물건의 최대 중량을 구하여라.2. 접근 방식 🗃️KEY WORD: Parametric Search, Binary_Search,DFS(1) 가중치 양방향 그래프를 인접리스트로 구현한다.(2) 이분탐색을 활용해, 한번에 옮길 수 있는 물건의 최대 중량을 구한다. (이분 탐색은 다음과 같이 진행 된다.)a. 문제에서 주어진 최대 중량과 최소 중량을 활용해 중앙값을 구한다.b. 해당 중앙값을 한 번에 옮길 수 있는 최대 중량이라 쳤을 때, 도착지까지 옮기는 게 가능한지 확인한다.c-1. 가능하다면 최소 중량을 현 중앙값 + 1 올려서, 다음에 구할 중앙값을 상향 조정 한다.c-2 .불가능하다..

1. 문제 설명 📌문제 설명2. 접근 방식 🗃️KEY WORD: BLACK-RED TREE, BST(Binary_Search_Tree)(0) BLACK-RED TREE 로 구현된 TreeSet을 활용한다.일반 BST일 때의 Depth를 저장하는 int [] depth 배열도 만든다.(1) TreeSet에 0과 N-1을 넣는다. (Null Pointer Exception 방지)depth[0]과 depth[N-1] 의 값은 -1을 넣는다. (계산에 영향을 주지 않기 위함)(2) TreeSet에 root 노드부터 끝노드까지 차례로 조회한다.조회했을 당시의 해당 노드보다 작으면서 최대값과 크면서 최소값인 노드가 무엇인지 구한다.(3) depth[현재 노드] = (2)에서 구한 둘 중 depth 값이 더 큰 ..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD : Binary Search, Parametric Search, Greedy Algorithm(1) 집 간의 최소 거리와 최대거리를 활용해, 임의의 거리 d를 산정한다.(2) '모든 공유기 사이의 거리가 최소한 d 이상인가?'를 boolean 값으로 계산한다.(3) (2)번이 true면, start = mid + 1로 거리를 상향 조정, false면 end = mid - 1로 하향 조정한다.(4) start와 end가 엇갈렸을 때, start - 1이 답이다.(1) Parametric Search 이용해당 문제는 가장 인접한 두 공유기 사이의 최대 거리 즉 최소값 중에서 최대값을 구하는 최적화 문제이다. 최적화 문제는 바로 풀기 어렵기 때..

1. 문제 설명 📌문제 설명2. 접근 방식 🗃️KEY WORD : Binary Search, Parametric Search(1) 모든 지방 예산의 합 총 예산, 그대로 예산 책정 하고, 제일 컸던 지방 예산을 출력(2) 모든 지방 예산의 합 > 총 예산: 예산 최소값과 최대값 사이에서 이분 탐색을 통해, 모든 예산을 처리하면서 최대인 값을 찾아서 출력 (1) Parametric Search 쓰인 곳모든 예산을 처리할 수 있는 최대값 구하기 ➜f(d) = 예산 상한액이 d일 때, 이걸로 총 예산 M 내에서 전부 처리 가능한가? 여러 개위와 같이 최적화 문제를 결정 문제 여러개로 바꾸어 푼다.f(d) = true가 나오는 값 중 최대한 오른쪽에 있는 값을 구하면 답이다. (즉 f(d) = true가..

1. 문제 설명 📌문제 링크문제x 중심선 위에 n개의 Thread가 존재한다. $T_{i}$라 불리는 i번째 Thread의 길이는 $l_{i}$와 해당 Thread의 시작 지점 위치인 $x_{i}$로 나타내어 진다. 두 변수 모두 Integer 이다. 우리는 각각의 Thread 마다 매듭을 짓고 싶어 한다. 매듭의 위치 또한 반드시 Integer여야 한다. 매듭은 Thread 안의 어느 지점에서든 상관 없이 만들어질 수 있고, Thread의 길이가 매듭에 의해 줄어들지 않는다고 가정한다. 당신은 또한 어떠한 Thread도 또 다른 Thread에 의해 완전히 포함되어지지 않는다고 가정한다. 어떤 의미냐면, $x_j$ 우리는 가장 가깝게 인접한 두 매듭 사이의 거리를 가능한 한 크게 만들기 위해서 각 Th..

1. 슬라이딩 단조 큐란 무엇인가요?슬라이딩 단조 큐란, DECK을 활용해 구현한 슬라이딩 윈도우로, 슬라이딩 윈도우 구간 내의 최소값, 최대값을 O(1)에 찾기 위해 고안한 구현체이다. 단조라는 이름이 붙은 이유는, 구간 내 최소값을 찾고 싶을 경우, Deck 내부 원소들이 오름차순으로 유지되고, 구간 내 최대값이 찾고 싶은 경우 내림차순으로 유지되기 때문이다.사실 내가 만든 이름이다...😂슬라이딩 윈도우 심화 문제를 풀면서, 슬라이딩 윈도우를 Deck으로 구현한 형태가 꾸준히 나오는데, 인터넷 여기 저기 찾아봐도, 형태만 있을 뿐 이것의 제대로 된 이름이 없었다.따라서 정식 명칭은 아니지만! 설명의 편의를 위해 앞으로 현 구간 내의 최소값과 최대값을 찾기 위해 Deck으로 구현한 슬라이딩 윈도우를 ..

0. 그래프 탐색의 기본인 DFS와 BFS그래프 탐색이란 무엇인가?그래프 탐색이란, 정점과 간선으로 이루어진 그래프에서 특정 정점을 선택하고, 해당 정점에서 인접한 정점을 방문하는 것을 말한다. 이러한 정점 방문 방법에는 크게 2가지가 있는데, 이것이 앞으로 살펴볼 DFS와 BFS이다.우리는 위의 그래프를 예시로 사용하며 하나씩 이해해 보겠다.1. DFSDFS는 Depth First Search의 약자로 깊이 우선 탐색을 뜻한다. 말 그대로 방문하기로 정한 인접 정점의 최대 깊이까지 탐색을 마친 후, 다음 인접 정점을 확인하는 것이다.알고리즘 논리는 다음과 같다.(1) 현재 정점과 인접한 정점을 방문한다.(2) 방문한 정점에서 아직 방문하지 않은 정점이 있다면 방문하지 않은 정점을 모두 방문할 때까지 (..