문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이시간복잡도: O(nlogn), 약 2천만주어진 N의 크기가 100만이다. 따라서 최대 사용할수있는 복잡도는 O(nlogn)이다.기본적으로 DP, 다른 알고리즘으로는 시간복잡도 상 이 문제를 풀..
깃 명령어 동작원리 GIT INIT: 깃의 시작head: 현재 체크아웃된 브랜치를 가리키는 포인터refs: 브렌치, 태그와 같은 참조들을 저장하는 폴더index: 스태이징 영역, 즉 메타 데이터와 오브젝트 데이터 저장하는 파일git add시 생성objects(객체): 모든 데이터를 저장하는 폴더, 여러 객체 저장tree: 커밋 시점의 인덱스의 스냅샷commit: 커밋 정보가 들어있는 객체blob: 파일 정보가 들어있는 객체, 작성한 소스코드가 파일 내용이 됨 GIT ADD&COMMITgit add: 변경된 파일 스테이징 영역으로 올리기ADD시에 SHA-1 알고리즘을 통해 이러한 해시값을 얻을 수 있다 커밋 객체커밋 객체는 파일의 스냅샷을 포함하는 트리 객체를 참조커밋 객체는 이전 커밋과의 관계를 나타내는..
개념과 구조RDB개념IBM소속 Edgar F. “Ted” Codd가 1970년에 RDB 개념제시, 구조와 접근 방식을 테이블(릴레이션)로 정리한 관계형 DB데이터를 테이블 형식으로 저장하며, 행과 열로 구성테이블 간의 관계는 키(기본키 → 외래키)를 사용하여 정의구조- 주 구성요소SQL엔진: SQL 쿼리의 해석, 최적화, 실행을 담당하며, 데이터베이스의 논리적 데이터 구조를 관리스토리지 엔진: 데이터의 물리적 저장, 검색을 처리하며, 다양한 스토리지 엔진 옵션(My SQL의 경우 InnoDB, MyISAM 등)이 존재InnoDB: 트랜잭션 지원, ACID준수, 무결성 보장과 동시성 제어 중시MyISAM: 트랜잭션 지원x, 빠른 읽기 작업과 낮은 메모리 사용 중점HDD: 데이터를 실제로 저장하는 하드웨어 ..
문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다. 풀이두 문자열중 하나를 기준으로 잡고 다른 하나의 문자열을 반복문 돌리면서 기준으로 잡은 문자열에 최대 길이 LCS를 저장하도록 하는 dp를 ..
문제아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. 의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 와 같이 된다. 은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없..
문제봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 '𝑘번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작성해 보자. 입력첫째 줄에 𝑛, 𝑚, 𝑘가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 250,000, 1 ≤ k ≤ 100, mk ≤ 3,000,000) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.이어지는 𝑚개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 𝑎, 𝑏, 𝑐가 포함되어 있다..
문제두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자. 입력첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 1016)출력1의 개수를 세어 출력한다. 풀이10^16값을 다 저장하는게 메모리상 불가능하므로 누적합을 이용해서 저장해야한다ex. 12이면 2[2]까지의 누적합 12를 더해준다.근데 이제 8~12의 값을 규칙을 토대로 구해야하는데 이걸 타 블로그에서는 비트마스크 방식을 채택했다본인은 그방식과 다르게 2로 나눠서 남은 누적합을 구한 이후 추후 더하는 방식을 채택했다 이와같은 방법으로 ..
문제우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다.그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다..
https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 ..
출처https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 ret..
