1. 동적 계획법(DP)에 대해 설명해주세요. 동적 계획법: 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법 DP를 적용하기 위해서는 2가지 조건을 만족해야 합니다. 첫째, 중복 문제 동일한 작은 문제들이 반복되어야, 부분 문제의 결과를 저장하여 재활용하여 전체의 답을 구할 수 있기 때문입니다. 둘째, 최적 부분 구조 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있어야 합니다. 구현 방법 1. Bottom-Up 작은 부분 문제부터 반복문을 통해 문제를 해결하고 값을 저장합니다.(메모이제이션) 2. Top-Down 큰 문제를 재귀 함수를 사용해 작은 부분 문제로 나누고, 중복 계산을 피하기 위해 메모이제이션을 활용합니다. 대표적으로 피보나치 문제, 배낭 문제가..
1. 스택과 큐의 차이점을 설명해주세요. 스택은 나중에 들어온 데이터가 가장 먼저 나가는 후입선출 방식의 선형 데이터 구조입니다. 반면, 큐는 먼저 들어간 데이터가 먼저 나오는 선입선출 방식의 선형 데이터 구조입니다. 스택은 재귀 알고리즘 같이 호출이 끝난 뒤 돌아갈 주소를 반환하는 용도에서 주로 사용됩니다. 예를 들어 뒤로 가기와 문자열 뒤집기 등이 있습니다. 큐는 프린터의 출력 처리, BFS 알고리즘 등과 같이 먼저 들어오는 것을 먼저 실행하는 작업에 주로 사용됩니다. 2. Array와 LinkedList의 차이점을 설명해주세요. Array(배열)은 정적 자료구조로 선언한 크기 만큼의 연속된 메모리 주소를 할당 받습니다. 연속된 메모리 주소를 할당 받기 때문에 인덱스에 해당하는 데이터의 탐색이 용이..
1. 키의 종류 5가지와 각각 특징을 설명하세요. 우선, 데이터베이스에서 키란 조건에 맞는 튜플을 찾거나, 순서대로 정렬할 때 다른 튜플과 구별할 수 있는 기준입니다. 또한 키의 특징에 들어가기 전 유일성과 최소성 개념에 대해 알아봅시다. 유일성 : 하나의 키값으로 튜플을 유일하게 식별할 수 있는 성질 최소성 : 키를 구성하는 속성들 중 꼭 필요한 최소한의 속성들로만 키를 구성하는 성질 슈퍼키 : 유일성 O, 최소성 X. 키 값이 같은 튜플에 존재할 수 없음, 나이+이름이면 성립X 후보키: 유일성 O, 최소성 O. 기본키가 될 수 있는 후보이기 때문에 후보키라고 불린다. 예를 들면, 주민등록번호, 학번 등 기본키: 후보 키에서 선택된 키. NULL값이 들어갈 수 없으며, 기본키로 선택된 속성(Attrib..
문제 링크 1090번: 체커 N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 www.acmicpc.net 문제 설명 N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 움직이는 것이다. 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 체커의 x좌표와 y좌표가 주어진다. 이 값은 1,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄..
문제 링크 14400번: 편의점 2 영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고 www.acmicpc.net 문제 설명 영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고객들이 어느 위치에 존재하는지 파악을 하였고, 모든 고객들의 거리의 합을 최소로 하려한다. 두 위치의 거리는 |x1-x2|+|y1-y2|로 정의한다. n명의 주요 고객들의 위치 (xi,yi)이 주어질 때, 모든 고객들의 거리 합을 최소로 하는 위치에 편의점을 ..
문제 링크 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 문제 설명 일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다. 집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 수 N이 자연수로 주어진다. ..
문제 링크 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 문제 설명 1~V 정점과 양방향 간선이 주어지고, 1->V 최단 경로에 건우의 위치인 P를 거치면 "SAVE HIM" 을 아니면 "GOOD BYE"을 출력한다. 입력 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 a,b,c가..
문제 링크 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 설명 n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다. 시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다..
