컴공에서 살아남기

가장 긴 증가하는 부분 수열 2 문제 수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 예제 입력 1 6 10 20 10 30 20 50 예제 출력 1 4 LIS (최장 증가 부분 수열) 유형에서 시간제한이 있는 문제를 새롭게 풀어보았다. ..

구간 합 구하기 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제한 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j ≤ N 예제 입력 1 5 3 5 4 3 2 1 1 3 2 4 5 5 예제 출력 1 12 9 1 누적합 문제를 처음 풀어봤다. 처음엔 단순 for문을 이용한 합계를 구해 시간초과가 발생했다. #include #incl..

프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중..

잃어버린 괄호 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫째 줄에 정답을 출력한다. 예제 입력 1 55-50+40 예제 출력 1 -35 예제 입력 2 10+20+30+40..

주유소 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다. 예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는..

균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때,..

[ 띄워쓰기를 포함하여 Enter 칠 때까지 문자열 입력받기 ] cin.getline(변수 주소, 최대 입력 가능 문자수, 종결 문자); ex) cin.getline(str, 100); getline(입력스트림 오브젝트, 문자열을 저장할 string객체, 종결 문자); ex) getline(cin, str); @ 주의사항: cin >> int형 변수; 을 사용하고 나서 바로 getline(cin, str); 을 사용하면 getline에서 문자열을 입력받지 않고 바로 다음 코드로 넘어간다. 이유: 버퍼에 정수 값을 입력한 뒤 누른 엔터('\n')가 그대로 남아있어 getline()에 들어가기 때문 따라서 cin.ignore() 함수를 사용하여 입력 버퍼의 모든 내용을 제거해줘야 getline 함수가 정상적..

[ vector 초기화 ] vector v(n); vector vv(n, vector(m)); [ vector의 멤버함수 ] vector v; - v.assign(5,2); 2의 값으로 5개의 원소 할당 - v.front(); 첫번째 원소를 참조 - v.back(); 마지막 원소를 참조 (++v.back() 하면 마지막 원소의 값을 1 올릴 수 있다) - v.clear(); 모든 원소를 제거, 원소만 제거하고 메모리는 남아있다. - v.pop_back(); 마지막 원소를 제거 - v.insert(2,3); 2번째 위치에 3의 값을 삽입 - v.insert(2,3,4); 2번째 위치에 3개의 4의 값을 삽입 (뒤에 원소가 있다면 뒤로 밀림) [ vector의 최대/최소 값 찾기 ] - int value =..

플로이드 문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거..

📖 플로이드 워셜 알고리즘 다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이다. 그러나, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에는 "플로이드 워셜 알고리즘"을 사용해야 한다. 📌 플로이드-워셜 알고리즘 vs 다익스트라 알고리즘의 차이점 1. 플로이드 워셜 알고리즘은 다익스트라에 비해 소스코드가 매우 짧아 구현이 쉽다. 2. 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야 하기 때문에 2차원 테이블에 최단 거리 정보를 저장한다. (다익스트라 알고리즘은 한 지점에서 다른 지점까지의 최단 거리만을 구하므로 1차원 리스트에 저장하였다) 3. 플로이드 워셜 알고리즘은 DP 알고리즘에 속한다. 만약 노드의 개수가..