프로그램에선 정수 뿐 아니라 소수점이 존재하는 실수를 다뤄야 할 때가 많다. 이러한 실수를 저장하는 변수로 부동 소수점(floating point) 변수를 사용하게 된다. 32bits로 실수를 표현한다고 해보자. 고정 소수점의 경우 MSB를 부호 비트, 15bits와 16bits를 각각 정수부/소수부 표기에 사용한다. 부동 소수점의 경우 MSB를 부호 비트, 8bits를 지수부, 23bits를 가수부 표기에 사용한다. 지수와 가수는 다음을 따른다 = (가수)*(2^(지수)) 이러한 표현의 방법 때문에 부동 소수점은 더 넓은 범위의 실수를 표현할 수 있게 된다. 4bytes(32bits)로 표현하는 방법을 single precision, 단정밀도(1: 부호, 8: 지수, 23: 가수) 8bytes(64bi..

ASCII American Standard Code for Information Interchange 1byte 공간 중 7bit를 사용하여 128개의 문자를 표현할 수 있다. 나머지 1bit는 오류 검산을 위한 패리티 비트로 사용하거나 확장 아스키를 표현하는데에 사용된다. 간단하고 메모리 공간을 효율적으로 사용하지만 지원하는 문자가 한정적이다. Unicode 전 세계의 모든 문자를 표현하기 위한 국제 표준 문자 규격. 각 문자에 고유한 코드 값을 할당하여 문자를 유일하게 식별할 수 있도록 함. 4바이트(32비트) 테이블을 사용하여 약 42억개의 문자를 다룰 수 있다. 유니코드를 그대로 사용할 경우 사용 비중이 높은 로마자(ASCII) 입장에서는 4배 가량의 비효율성이 발생. 이러한 유니코드의 문제를 보..

In-Place 방법을 사용하여 추가 메모리를 사용하지 않는다. pivot은 배열의 가장 끝 원소로 설정한다. 배열의 시작 인덱스는 front, 끝 인덱스는 end라고 한다 front cursor는 front부터 end-1까지 탐색하여서 pivot보다 큰 수를 탐색한다 back cursor는 end - 1부터 front까지 탐색하여서 pivot보다 작은 수를 탐색한다. → ← pivot 3 10 10 1 4 9 2 7 7 front와 back이 교차되지 않았다면 front의 원소와 back의 원소를 바꿔준다. front와 back이 교차되었다면 front의 원소와 pivot의 원소를 바꿔준다. front의 값을 정렬 후 pivot의 위치라는 점을 활용하여 재귀적으로 함수를 호출해준다. #include #..

1. 시퀀스 컨테이너 가장 일반적인 형태의 컨테이너. 특별한 제약, 규칙 없이 데이터를 선형으로 저장함. 입력한 순서대로 저장하기 때문에 데이터의 검색에는 불리함 vector, deque, list, forward_list 2. 연관 컨테이너 일정한 규칙에 따라 자료를 조직화하여 저장, 관리하는 컨테이너. 자료를 정렬하여 저장하기 때문에 데이터의 검색에 유리함. 많은 양의 자료나 검색 속도가 중요한 경우에 사용. set, map, unordered_set, unordered_map 3. 컨테이너 어댑터 간결함과 명료성을 위해 시퀀스나 연관 컨테이너에서 인터페이스를 제한하여 변형시킨것. 반복자를 지원하지 않는다. stack, queue, priority_queue 구분 Container 시간복잡도 특징 R..

https://www.acmicpc.net/problem/1508 1508번: 레이스 첫째 줄에 N, M, K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, M은 K보다 작거나 같다. 또, K는 2보다 크거나 같고, 50보다 작거나 같다. 둘째 줄에 심판이 있을 수 있는 K개의 위치가 주어 www.acmicpc.net https://djgameprogramming.tistory.com/117 공유기 설치(이분 탐색, 그리디) https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 도대체 어느 부분에서 이분 탐색을 해야하는건가 했는데 '간격'의 탐색에서 이분 탐색을 활용하여 점점 좁혀나가는 문제였다. 공유기를 설치할때 앞에서부터 탐색하여 목표하는 간격값을 넘어가면 바로 공유기를 설치한다 → 그리디 설치한 공유기 갯수와 목표 공유기 갯수를 비교하여 이분탐색으로 목표 간격값을 최대한 늘려나간다 → 이분 탐색 1. 중간 간격값을..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 쉬운 계단 수 문제를 먼저 보자. 길이가 N인 계단 수에서 맨 끝에 숫자를 추가하면 길이가 N+1인 계단 수가 된다. 이때 더할 수 있는 숫자는 기존의 계단 수의 가장 끝의 숫자로 판단한다. 0, 9일때는 각각 1과 8이고 1~8의 숫자는 각각 2가지의 숫자가 될 것이다. DP[i][j] i = 계단 수의 길이 j = 가장 끝의 숫자 저장하는 값 = i길이의 수열에서 끝의 숫자가 j일때 해당 수열로 특정 길이의 계단 수를 만들 수 있는 갯수 이런 방법을 재귀함수와 메모이제이션으로 구현하고 길이가 충족할때 1을 ..

https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 엣지들의 합이 최대가 되는 경로탐색 문제에서 M번이라는 횟수 제한이 추가되었다. M번의 탐색이라는 제한이 걸려있으므로 이러한 정보를 저장하여야 한다. 그러므로 i번째 순서에 j라는 버텍스로 갔을때 엣지합의 최대값을 저장하여 DP를 활용한다. DP[i][j] = i번째에 j에 도달했을때 엣지들의 최대 합 그래프를 1번부터 탐색하여 DP를..

https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 기본적으론 완전 탐색을 기반으로 두고 이미 탐색했던 상황에 대해선 저장된 값을 사용하는 DP 기법을 활용하는 문제다. 처음엔 특정 문을 열때 각각 왼쪽, 오른쪽에 있는 벽장으로부터 열 수 있다는 점에서 착안하여 DP[21][2]의 이중 어레이를 사용하려고 했다. 하지만 특정 벽장을 열때마다, 즉 단계마다 열려있는 벽장의 정보를 저장할 수가 없었다. 해당 문제에서 중요한 점은 각 상황에 따라 열..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제 이름 그대로 Longest Common Substring의 길이를 찾는 문제 LCS에 대하여 정리해놓은 글이 있다 https://djgameprogramming.tistory.com/110 Longest Common Subsequence/Substring(LCS) DP를 활용하는 알고리즘 중 하나. Longest Common Subsequence는 최장 공통 부분 수열 Longes..

DP를 활용하는 알고리즘 중 하나. Longest Common Subsequence는 최장 공통 부분 수열 Longest Common Substring는 최장 공통 부분 문자열 문자열은 연속되는 순서를 의미하고 수열은 연속되지 않는 순서도 모두 포함한 의미이다. ABRAC라는 문자열이 존재할때 이 문자열의 부분 수열은 0(공집합), A, AB, ABR, AR, ABRAC... 등등 여러개가 존재한다. 여기서 AR이라는 부분 수열은 Substring에는 포함되지 않지만 Subsequence에는 포함된다. 1. Longest Common Subsequence 먼저 연속되지 않은 최장 공통 부분 수열의 길이를 탐색하는 방법을 살펴보자. 두 문자열 ABCBD, CABCD를 비교할때 단순하게 문자열의 맨 앞에서부..

https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net Top-Down 방식의 다이나믹 프로그래밍 기법을 사용한다. DP[N번째 숫자][M개의 구간]으로 정의한다. DP에 저장되는 값은 N번째 숫자까지 M개의 구간을 만들때 가능한 숫자의 최대합. M개의 구간을 만들어야 하는 상황에서 N번째 숫자에 도달했다면 가능한 경우의 수는 다음과 같다. 1. N번째 숫자를 M번째 구간에 포함시키지 않는다. -> DP[N][M] = DP[N..