문제 링크 28278번: 스택 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net 문제 설명 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. 1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000) 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다. 3: 스택에 들어있는 정수의 개수를 출력한다. 4: 스택이 비어있으면 1, 아니면 0을 출력한다. 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다. 입력 첫째 ..
문제 링크 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 문제 설명 태수가 즐겨하는 디제이맥스 게임은 각각의 노래마다 랭킹 리스트가 있다. 이것은 매번 게임할 때 마다 얻는 점수가 비오름차순으로 저장되어 있는 것이다. 이 랭킹 리스트의 등수는 보통 위에서부터 몇 번째 있는 점수인지로 결정한다. 하지만, 같은 점수가 있을 때는 그러한 점수의 등수 중에 가장 작은 등수가 된다. 예를 들어 랭킹 리스트가 100, 90, 90, 80일 때 각각의 등수는 1, 2, 2, 4등이 된다 랭킹..
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이 자연수로 주어진다. ..
