JOHOONDAY
본문 바로가기

전체 글129

백준 No.1167 [트리의 지름] BOJ No.1167 [트리의 지름] 문제 1167번: 트리의 지름 (acmicpc.net) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 설명 * Tree * DFS 트리의 지름이란, 트리 상에서 가장 먼 거리를 가지는 두 정점 사이의 경로이다. 위 예시 트리에서 H 노드와 G 노드 사이의 거리는 23이며, 이 경로가 트리의 지름이 된다. 트리의 지름은 다음과 같은 순서로 구해진다. 1. DFS를 통해 임의의 정점(x)으로부터 가장 먼 정점(y)을 구한다. 2. DFS를 통해 구해진 (y).. 2022. 7. 13.
백준 No.10986 [나머지 합] BOJ No.10986 [나머지 합] 문제 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 설명 * 구간 합 (Prefix sum) 구간 합을 간단하게 활용 한 문제이다. 참고 Link : 2022.04.19 - [Algorithm (C++ based)/Algorithm 이론] - 구간 합 (Prefix sum) 만약 4번째 원소 (index == 3) 부터 19번째 원소 (index == 18) 까지 구간 합이 .. 2022. 4. 19.
구간 합 (Prefix sum) 구간 합 (Prefix sum) array 에서 누적 합을 통해 구간 합을 구할 수 있다. 정의 Array 에서 누적 합을 통해 원하는 구간의 합을 구할 수 있다. 설명 1차원 Array 에서의 구간 합 arr Array 는 1차원 배열이고, sum Array 는 0 번째 index 를 가지는 원소부터 그 index 값의 원소까지의 누적 합 배열이다. 위와 같이 3번째(index == 2) 원소 부터 7번째(index == 6) 원소 까지의 구간 합을 구하고 싶으면? sum[6] - sum[1] 을 하면 구할 수 있다 ;) 관련 Code sum[0] = arr[0]; for (int i = 1; i < n; i++) { sum[i] += sum[i - 1] + arr[i]; } // 6 ~ 17 번째 원.. 2022. 4. 19.
K-NN Study import numpy as np import matplotlib.pyplot as plt from sklearn.neighbors import KNeighborsClassifier from sklearn.model_selection import train_test_split fish_length = [25.4, 26.3, 26.5, 29.0, 29.0, 29.7, 29.7, 30.0, 30.0, 30.7, 31.0, 31.0, 31.5, 32.0, 32.0, 32.0, 33.0, 33.0, 33.5, 33.5, 34.0, 34.0, 34.5, 35.0, 35.0, 35.0, 35.0, 36.0, 36.0, 37.0, 38.5, 38.5, 39.5, 41.0, 41.0, 9.8, 10.5, 10.6, 1.. 2022. 4. 18.
Linear Regression Study import numpy as np import matplotlib.pyplot as plt import pandas as pd from sklearn.neighbors import KNeighborsClassifier from sklearn.neighbors import KNeighborsRegressor from sklearn.linear_model import LinearRegression from sklearn.model_selection import train_test_split perch_length = np.array( [8.4, 13.7, 15.0, 16.2, 17.4, 18.0, 18.7, 19.0, 19.6, 20.0, 21.0, 21.0, 21.0, 21.3, 22.0, 22.0, 22.. 2022. 4. 17.
백준 No.1019 [책 페이지] BOJ No.1019 [책 페이지] 문제 1019번: 책 페이지 (acmicpc.net) 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 설명 * 수학 숫자의 영역을 3개로 나누어 카운팅을 한다. 위 예시는 입력값이 8853 인 경우이다. 처음에 값을 입력 받으면, 위 예시처럼 입력된 숫자와 가장 가까운 9로만 이루어진 더 작은 숫자를 찾는다. 위 경우에는 999 가 이에 해당된다. 이 숫자를 기점으로 first area, second area 로 나뉘게 된다. 그리고, 9로 끝나는 가장 가까운 수를 찾는다. 이 숫자를 기점으로 second area, last area 로 나.. 2022. 4. 13.
Leetcode) No.262 [Trips and Users] Leetcode) No.262 [Trips and Users] 문제 (2) Trips and Users - LeetCode Trips and Users - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 설명 * GROUP BY * HAVING * WHERE * ROUND * IF * COUNT Request_at 날짜를 기준으로 그룹화를 한다. 이 때, 그 그룹에는 Banned 되지 않은 Client와 Driver 만 들어갈 수 있으며, 2013년 10월 1일 .. 2022. 4. 4.
백준 No.5670 [휴대폰 자판] BOJ No.5670 [휴대폰 자판] 문제 5670번: 휴대폰 자판 (acmicpc.net) 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 설명 * 자료 구조 * 트라이 (Trie) 문자열을 저장하는 자료구조 (Trie : 트라이 (Trie) : 문자열 저장 자료구조) 를 이용하는 문제이다. 각 Node 의 옆에 파란 숫자는 그 글자까지 나오기까지 키보드를 누른 횟수이다. 또한 빨간 테두리 Node 는 단어의 끝을 알리는 Node 이다. 키보드를 누르는 경우는 크게 세 가지가 있다. 1. 아직 아무 문자도 안 눌.. 2022. 4. 2.
트라이 (Trie) : 문자열 저장 자료구조 트라이 (Trie) 저장된 문자열 탐색에 용이한 자료구조 정의 트라이(Trie) 는 문자열들의 집합이 있을 때 문자열의 존재 여부를 쉽게 찾아낼 수 있도록 해 주는 자료구조 이다. 직관적인 예시를 통해 설명을 해 보았다. 설명 아래 문자열들을 저장 해 보려고 한다. [저장된 문자열들] key king hi hint day date 위 문자열들은 Trie 자료 구조에서 아래와 같이 저장된다. 만약 'king' 이라는 단어가 저장이 되어 있는지 찾아보고 싶으면 root Node 부터 차례대로 하위 Node로 이동하여 'k', 'i', 'n', 'g' 를 찾아가면 된다. 만약 저 자료구조에는 존재하지 않는 'keep' 이라는 단어를 찾아보려 한다면, root Node ⇒ 'k' Node ⇒ 'e' Node ⇒.. 2022. 4. 2.
백준 No.7420 [맹독 방벽] BOJ No.7420 [맹독 방벽] 문제 7420번: 맹독 방벽 (acmicpc.net) 7420번: 맹독 방벽 첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000, N과 L은 정수) 다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 좌 www.acmicpc.net 설명 * 볼록 껍질 (컨벡스 헐 : Convex hull) 볼록 껍질을 응용하여 풀 수 있는 문제이다. 아래 예시를 들어 보았다. 건물들의 좌표를 위와 같이 입력을 해 보았다. 또한 해당 좌표들을 좌표평면에 표시 해 보았다. 위 좌표들을 모두 감싸면서 건물들에선 최소 L 만큼 떨어져 있어야 하는 방벽을 세워야 한다. .. 2022. 3. 28.
볼록 껍질 (컨벡스 헐 : Convex hull) 볼록 껍질 (컨벡스 헐 : Convex hull) 점들을 통해 볼록 다각형을 형성 다각형에 포함되지 않는 점들은 다각형 내부에 존재 참고 링크 2022.03.26 - [Algorithm (C++ based)/BOJ] - 백준 No.1708 [볼록 껍질] 백준 No.1708 [볼록 껍질] BOJ No.1708 [볼록 껍질] 문제 1708번: 볼록 껍질 (acmicpc.net) 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이.. johoonday.tistory.com 볼록 껍질(컨벡스 헐)의 기본 개념을 다루는 문제이다. 볼록 껍질(컨벡스 헐) 의 개념이 설명되어 있다. 2022. 3. 27.
백준 No.1708 [볼록 껍질] BOJ No.1708 [볼록 껍질] 문제 1708번: 볼록 껍질 (acmicpc.net) 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 설명 * 볼록 껍질 / 컨벡스 헐 (Convex hull) 볼록 껍질 위와 같이 평면 좌표에 N개의 점이 있을 때 점들을 이어 볼록 다각형을 만들면서, 잇지 않은 나머지 점들은 볼록 다각형 내부에 있도록 하는 것 이다. 볼록 껍질을 구현하기 위한 전처리 과정은 아래와 같이 정리할 수 있다. 1. 점들 중 껍질을 만들기 시작하는 점을 찾는다. - 보통 y값.. 2022. 3. 26.
MySQL) 프로시저(PROCEDURE) 프로시저 (PROCEDURE) 어떠한 동작을 일괄 처리하기 위한 쿼리문의 집합 설명 DLIMITER $$ CREATE PROCEDURE ( ) BEGIN END $$ 프로시저(Procedure)란 MySQL 에서 제공이 되는 프로그래밍 기능이라고 생각을 하면 된다. 현재 프로시저의 입출력 파라미터(매개변수) 를 관리하는 부분이다. 입력 파라미터는 `IN ` 으로, 출력 파라미터는 `OUT `으로 선언이 된다. 그리고 입출력을 동시에 행하는 파라미터도 있으며 이는 `INOUT ` 으로 선언이 된다. 아래에 예시를 들어보았다. IN number INT OUT sum INT INOUT value INT 주황색 부분은 입력, 출력, 입출력 여부를 선언하는 부분이다. 초록색 부분은 그 파라미터의 이름이고 보라색 .. 2022. 1. 17.
HackerRank SQL) Binary Tree Nodes HackerRank SQL) Binary Tree Nodes 문제 Binary Tree Nodes | HackerRank Binary Tree Nodes | HackerRank Write a query to find the node type of BST ordered by the value of the node. www.hackerrank.com Code SELECT CUR.N, CASE WHEN CUR.P IS NULL THEN 'Root' WHEN CUR.N IN (SELECT DISTINCT NXT.P FROM BST AS NXT WHERE NXT.P IS NOT NULL) THEN 'Inner' ELSE 'Leaf' END FROM BST AS CUR ORDER BY CUR.N ASC; 설명 SE.. 2022. 1. 15.
MySQL) IF, IFNULL, NULLIF, CASE ~ WHEN ~ END IF, IFNULL, NULLIF, CASE ~ WHEN ~ END [제어 흐름 함수] 설명 * IF ( , , ) 이 참이면 이 반환이 되고, 이 거짓이면 이 반환이 된다. SELECT IF (100 > 200, 'True', 'False'); # False가 출력이 될 것 이다. SELECT IF (200 > 100, 'True', 'False'); # True가 출력이 될 것 이다. 이 100 > 200 인 선언문은 거짓 이므로 이 출력되어 'False'가 출력이 되었고, 수식이 200 > 100 인 선언문은 참 이므로 이 출력되어 'True'가 출력이 되었다. * IFNULL ( , ) 이 NULL이 아니면 이 반환이 되고, NULL이면 가 반환이 된다. SELECT IFNULL (NULL, 'T.. 2022. 1. 11.