천천히 빛나는

LCS (Longest Common Subsequence)문자열 x, y가 있을 때 x와 y에서 공통으로 나타나는 부분 문자 수열 중 최대 길이를 갖는 문자 수열예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다 재귀적으로 정의c(i, j) : 수열 xi와 yj의 LCS의 길이 기저조건 (종료조건)i =0 또는 j = 0이면 c(i, j) = 0이 된다재귀조건xi = yj이면 c(i, j) = c(i-1, j-1) + 1xi != yj이면 c(i,j) = max(c(i, j-1), c(i-1, j))int lcs (String x, String y){ int m = x.length(); int n = y.length(); if(m == 0 || n == 0){ re..

위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 위와 같이 나열하는 것을 위상 정렬이라고 한다. 위상정렬을 알기 전 다뤄야 하는 용어에 진입차수와 진출차수가 존재한다. 진입차수 (Indegree) 특정한 노드로 들어오는 간선의 개수 진출차수 (Outdegree) 특정한 노드에서 나가는 간선의 개수 동작 과정 진입차수가 0인 모든 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다 새롭게 진입차수가 0이 된 노드를 큐에 넣는다 예시 진입차수가 0인 노드가 존재하기 위해서는 사이클이 없는 그래프가 필요하다 [초기단계] 진압차수가 0인 모든 노드를 큐에 넣는다. [1] 큐에서 노드 ..

전보 통로 = 방향성이 있는 간선 일정 시간 = 간선 가중치 핵심 아이디어 : 한 도시에서 다른 도시까지의 최단 거리 문제 N과 M의 범위가 충분히 크기 때문에 우선순위 큐를 활용한 다익스트라 알고리즘을 구현해야 한다. import java.util.*; class Node implements Comparable { private int index; private int distance; public Node(int index, int distance) { this.index = index; this.distance = distance; } public int getIndex() { return this.index; } public int getDistance() { return this.distance..

플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드 워셜은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다익스트라 알고리즘이란? https://shine-slowly.tistory.com/85 알고리즘 : 다익스트라(Dijkstra) 최단 경로 알고리즘 (Java로 구현) 다익스트라 최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 최단 경로 알고리즘 중 다익스트라 알고리즘은 다음과 같은 특징을 가지고 있다. 특정한 노 shine-slowly.tistory.com 다익스트라 알고리즘과 다른게 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다...

다익스트라 최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 최단 경로 알고리즘 중 다익스트라 알고리즘은 다음과 같은 특징을 가지고 있다. 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 사용할 수 있다 다익스트라 최단 경로 알고리즘은 그리디 알고리즘 중 하나이다. 매 상황에서 가장 비용이 적게 드는 노드를 선택하기 때문이다. 다음은 다익스트라 최단 경로 알고리즘의 동작 과정을 간단히 서술한 내용이다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 이 때, 다른 노드까지의 거리를 무한으로 설정하고 자기 자신까지의 거리는 0으로 설정한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은..

1. 폰켓몬 #include #include using namespace std; set s; int solution(vector nums) { int answer = 0; for(int i=0; i= nums.size()/2) return nums.size()/2; return s.size(); } 여기서는 set을 사용하여 구현하였다 #include set s; 원소가 삽입되면 자동으로 오름차순(less) 정렬이 되며 원소값은 중복이 되지 않는다. s.insert(k); s.insert(iter, k); 벡터처럼 사용이 가능하나 push_back이 아닌 insert로 값을 삽입한다. #include #include using namespace std; int solution(vector nums) {..

프로그래머스 SQL 고득점 Kit의 String, Date 문제입니다. https://school.programmers.co.kr/learn/challenges?tab=sql_practice_kit 1. 자동차 대여 기록에서 장기/단기 대여 구분하기 SELECT HISTORY_ID, CAR_ID, DATE_FORMAT(START_DATE, '%Y-%m-%d') AS START_DATE, DATE_FORMAT(END_DATE, '%Y-%m-%d') AS END_DATE, IF(DATEDIFF(END_DATE, START_DATE) >=29, '장기 대여', '단기 대여') AS RENT_TYPE FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY WHERE YEAR(START_DATE) ..

프로그래머스 SQL 고득점 Kit의 JOIN 문제입니다. https://school.programmers.co.kr/learn/challenges?tab=sql_practice_kit 1. 주문량이 많은 아이스크림 조회하기 SELECT F.FLAVOR FROM FIRST_HALF AS F, JULY AS J WHERE F.FLAVOR = J.FLAVOR GROUP BY F.FLAVOR ORDER BY (SUM(J.TOTAL_ORDER) + F.TOTAL_ORDER) DESC LIMIT 3; INNER JOIN이기 때문에 WHERE 대신 JOIN JULY AS J ON F.FLAVOR = J.FLAVOR 해도 된다 2. 특정 기간동안 대여 가능한 자동차들의 대여비용 구하기 SELECT DISTINCT C...

Join 연산 - 내부 조인 (Inner Join) 1) 동등 조인 (Equi Join) 내부 조인이라고 하면 동등 조인을 생각하면 된다. SELECT 속성 FROM 테이블 1 INNER JOIN 테이블 2 ON 조인 조건 WHERE 조건 SELECT NAME, ID FROM EMPLOYEE INNER JOIN PROJECT ON EMPLOYEE.ID = PROJECT.eID 내부 조인은 WHERE 만 가지고도 충분히 구현 가능하다. WHERE 안에 조인 조건을 넣어줘도 구현이 된다. SELECT * FROM EMPLOYEE, DEPARTMENT WHERE DNUMBER=DNO; SELECT * FROM EMPLOYEE INNER JOIN DEPARTMENT ON employee.dno = departm..

프로그래머스 SQL 고득점 Kit의 IS NULL 문제입니다. https://school.programmers.co.kr/learn/challenges?tab=sql_practice_kit 1. 경기도에 위치한 식품창고 목록 출력하기 SELECT WAREHOUSE_ID,WAREHOUSE_NAME,ADDRESS,IFNULL(FREEZER_YN,'N') FROM FOOD_WAREHOUSE WHERE ADDRESS LIKE '경기도%' ORDER BY WAREHOUSE_ID; IFNULL : NULL값이라면 다른 값으로 대체 2. 이름이 없는 동물의 아이디 SELECT ANIMAL_ID FROM ANIMAL_INS WHERE NAME IS NULL ORDER BY ANIMAL_ID; 이름이 있는 동물은 IS ..