문제유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 ..
문제러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다.이 게임에서 유럽은 R행 C열로 나누어져 있다. 각 칸은 비어있거나, 아래 그림과 같은 일곱가지 기본 블록으로 이루어져 있다.파이프 라인의 설계를 마친 후 두 사람은 잠시 저녁을 먹으러 갔다. 그 사이 해커가 침임해 블록 하나를 지웠다. 지운 블록은 빈 칸이 되어있다.해커가 어떤 칸을 지웠고, 그 칸에는 원래 어떤 블록이 있었는지 구하는 프로그램을 작성하시오.입력첫째 줄에 유럽의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 25)다음 R개 줄에는 C개 글자가 주어지며, 다음과 같은 글자로 이루어져 있다.빈칸을 나타내는 ..
문제2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) 이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오. 입력첫째 줄에 보드의 크기 N..
풀이 백준의 2048문제와 다르게 상하좌우중에 한 방향으로 한번만 이동하면 되는 문제이다. 따라서 100개 케이스 2초 즉 1케이스당 200만 복잡도까지 사용가능하다. 방향을 입력받고 각 방향에 맞게 블럭을 이동시켜주면 된다. 이 과정을 투포인터로 할수도 있고 Queue를 사용할 수도 있다. 본인은 Deque을 사용해서 해당블록들이 합해지는 기록을 했다. 아래 이미지는 첫번째 케이스의 첫 열이 Queue에 들어오는과정을 설명한다. 중요한점은 3가지 조건을 생각해야한다.Queue가 비어있는가? -> 비어있다면 해당 칸값 바로 추가칸의 값이 0인가? -> 추가X바로 이전에 값이 합쳐졌는가?(이 조건을 안넣으면 계속해서 칸의 합이 합쳐진다.) -> 다음칸은 그냥 Queue에 추가 이후에는 Queue..
문제수열 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은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.이어지는 𝑚개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 𝑎, 𝑏, 𝑐가 포함되어 있다..
