📗 CS

문제 수열 A가 주어졌을 때 가장 긴 증가하는 부분수열의 길이와 부분수열을 출력하는 문제. 증가 수열의 길이는 DP를 이용하여 쉽게 구할 수 있습니다. 우선 증가수열의 길이부터 구해봅시다. 1. dp 배열 값을 모두 1로 초기화 합니다. : v 배열에서 모든 인덱스의 배열값은 증가 수열의 시작이 될 수 있기 때문에 1로 초기화 해줍니다. 2. 0번째부터 n-1번째 까지 이중 포문으로 현재 인덱스 위치의 값보다 다음 인덱스 위치(j번째)의 값이 더 크다면 dp 배열의 j번째 값과, i번째 값 + 1중 큰 값을 dp배열의 j번째 값에 삽입합니다. 3. 가장 긴 증가하는 부분 수열을 출력 dp 배열을 이용하여 역추적하여 증가하는 부분수열을 쉽게 구할 수 있습니다. 역추적하지 않고 dp값이 1인 배열부터 순서대..

https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 오큰수를 풀었다면 매우 쉽게 접근할 수 있는 문제입니다. 매커니즘은 동일한데, 오큰수와 달리 어떤 값을 비교하고 어떤 값을 정답 배열에 저장해야하는지만 잘 파악하면 쉽게 풀 수 있습니다. 우선 세팅을 하기 위해 배열을 입력받고 map을 이용해 카운팅하여 c 배열에 해당 숫자가 나온 횟수를 넣어줍니다. 오큰수에서는 배열 값을 스택에 넣고 스택의 탑값과 비교했다면, 오등큰수 배열을 만드는 과정에서는 비교 과정에서..

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 요약 1. 크기가 N인 배열에서 2. i번째 인덱스의 배열의 값에서 오른쪽에 있는 수 중 가장 큰 수를 출력 3. 만약 오른쪽에 있는 수가 현재 인덱스의 배열의 값보다 작다면 -1 출력 이중 포문으로 해결은 가능하지만 최악의 경우에 1,000,000 * 1,000,000 = 1,000,000,000,000 (1조) 즉, 1조 / 1억(1s) = 10,000s가 걸리게 되어 시간초과가 발생합니다. 문제는 배열의 i번째 값에서 오른쪽에 있는 수 중 가장 큰 수를 어떻게 빠르게 ..

C++에서 스트링을 입력받을 때 std::cin을 이용해 입력받곤 합니다. 이 때 입력받는 스트링에 공백을 포함하고 싶을 때, 예를 들면 "hello world" 라는 스트링을 하나의 변수에 저장하기 위해서는 getline()을 통해 입력을 받아야 합니다. 하지만 이 때 getline을 호출하기 전 받는 입력이 있다면, 버퍼에 개행문자(\n)가 남아있기 때문에 '\n'이 getline에 바로 입력되어 버리게 됩니다. cin은 '\n'을 처리하지 않고 입력버퍼에 남겨둠 ➡️ getline()은 입력버퍼에 남아있는 '\n'을 가져와서 처리 ➡️ 입력받아 저장된 스트링 변수의 앞부분에 '\n'이 함께 저장됨. int n; string s; cin >> n; getline(cin, s); // n을 입력 이후 ..

프로세스란? 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램을 말합니다. 디스크로부터 메모리에 적재되어 CPU로부터 하나의 프로세스를 할당을 받을 수 있습니다. 운영체제로부터 주소 공간, 파일, 메모리 등을 할당받는데 이를 총칭하여 프로세스라고 합니다. 프로세스는 프로그램과 뭐가 다른가? "프로그램"은 보조기억장치(SSD, 하드디스크)에 존재하며 실행되기를 기다리는 명령어와 정적인 데이터의 묶음입니다. 즉 프로그램은 단순히 명령어와 데이터의 묶음일 뿐, 생명을 가지고 있지않습니다. 이 프로그램의 명령어와 정적 데이터가 "메모리에 적재"되는 순간 생명이 있는 프로세스가 된다고 보시면 됩니다. 프로그램의 명령어와 정적 데이터 --- (메모리에 적재) ---> 프로세스 프로세스의 구성 : 프로세스에 대한 ..