휘발 방지용

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net stl vector에 대해서 더 공부할 수 있던 문제였다. 처음엔 vector v로 선언해서 {X, 순서}를 저장하려고 했는데, 풀다보니까 순서를 굳이 저장할 필요가 없어져서 vector v로 바꾸어 풀었다. 참고로 pair로 선언된 vector를 sort함수로 정렬할때 compare함수를 따로 작성안하면 first 값을 기준으로 정렬 된다고함!!..

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여, 필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다. 바킹독의 실전 알고리즘 0x08강 링크 강의내용 복습 수식의 괄호 쌍 괄호의 종류 : () {} ... 올바른 수식인지 스택을 이용해 판단하는 법(FILO) 문자열을 순서대로 읽어들이면서, 여는 괄호가 나오면 스택에 push한다. 닫는 괄호가 나오면 스택에 가장 최근에 들어온 여는 괄호와 짝을 이룰경우, 여는 괄호를 스택에서 pop 하면 된다. 스택이 비어있을 경우나 짝이 맞지 않는 경우는 올바르지 않은 수식이다. 문자열을 다 읽었을때 스택이 비어있다면 올바른 수식 !! 괄호가 남아있다면 올바르지 않은 수식이다. 올바르지 않은 괄호쌍 예시 짝이 안맞음 ..

https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 유클리드 호제법 최대공약수를 구한 방법 두 자연수 A, B의 최대공약수를 구할 땐, 유클리드 호제법을 사용한다. A > B 일때, A를 B로 나눈 나머지를 R이라 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. B > R 이고, A를 R로 나눈 나머지를 R2라 하면, B와 R의 최대공약수는 R과 R2의 최대공약수와 같음을 반복적용한다. 이 과정을 반복하다가, 두 수(C, D(C>D)라 하자)를 나눈 나머지가 0이 되었을 때, 나누는 수 D가 A와 B의..

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여, 필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다. 바킹독의 실전 알고리즘 0x07강 링크 강의내용 복습 덱의 정의와 성질 덱 : 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조 *자료구조에서 덱은 deque(Double End Queue)를 의미 덱의 성질 1. 원소의 추가가 O(1) 2. 원소의 제거가 O(1) 3. 제일 앞/뒤의 원소 확인이 O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능 *STL deque에서는 인덱스로 원소에 접근 가능 덱의 기능과 구현 배열과 연결리스트 두개 모두 구현 가능하나, 배열을 이용하는게 구현하기 쉽다. const int MX = 100..

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여, 필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다. 바킹독의 실전 알고리즘 0x06강 링크 강의내용 복습 큐의 정의와 성질 큐 : 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조(FIFO, First In First Out) 큐의 성질 1. 원소의 추가가 O(1) 2. 원소의 제거가 O(1) 3. 제알 앞/뒤의 원소 확인이 O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 rear : 큐에서 원소가 추가되는 곳(뒤쪽) front : 큐에서 원소가 제거되는 곳(앞쪽) 큐의 기능과 구현 배열과 연결리스트 어떤것으로도 구현은 가능하나, 배열이 구현하기 더 쉽다..

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여, 필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다. (이것은 다 ~ 개강 전까지 그동안 굳어있던 머리를 활성화 시키기 위한 발악인 것입니다...) 바킹독의 실전 알고리즘 0x05강 링크 강의내용 복습 스택의 정의와 성질 스택 : 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조, LIFO(Last In First Out) *Restricted Structure : 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있음(스택, 큐, 덱) 스택의 성질 1. 원소의 추가가 O(1) 2. 원소의 제거가 O(1) 3. 제일 상단의 원소 확인이 O(1) 4. 제일 상단이 아닌 나머지 원소들의 확인/변경은 원칙적..

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여, 필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다. (이것은 다 ~ 개강 전까지 그동안 굳어있던 머리를 활성화 시키기 위한 발악인 것입니다...) 바킹독의 실전 알고리즘 0x04강 링크 강의내용 복습 연결리스트의 정의와 성질 연결리스트 : 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조 연결리스트의 성질 1. k번째 원소를 확인/변경하기 위해 O(k)가 필요함 배열과 달리 공간에 원소들이 연속해서 위치하고 있지 않기 때문 2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) 연결리스트의 굉장히 큰 장점! 3. 원소들이 메모리 상에 연속해있지 않아 Cach..

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여, 필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다. (이것은 다 ~ 개강 전까지 그동안 굳어있던 머리를 활성화 시키기 위한 발악인 것입니다...) 바킹독의 실전 알고리즘 0x03강 링크 강의내용 복습 배열의 정의와 성질 *프로그래밍 언어의 관점에서의 배열과 달리, 바킹독님 강의의 자료구조로써의 배열에서는 길이를 마음대로 늘리거나 줄일 수 있다고 생각한다. 배열 : 메모리 상에 원소를 연속하게 배치한 자료구조 배열의 성질 1. O(1)에 k번째 원소를 확인/변경 가능 메모리 상에 원소를 연속하게 배치한 자료구조이기 때문에 시작주소에서 k칸 만큼 오른쪽으로 갈 수 있다. 2. 추가적으로 소모되는 메모리의 양..

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여, 필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다. (이것은 다 ~ 개강 전까지 그동안 굳어있던 머리를 활성화 시키기 위한 발악인 것입니다...) 바킹독의 실전 알고리즘 0x01강 링크 바킹독의 실전 알고리즘 0x02강 링크 강의내용 복습 시간복잡도와 공간복잡도 시간 제한과 메모리 제한에 대한 내용. 컴퓨터는 1초에 대략 3-5억 개 정도의 연산을 처리할 수 있다. 즉, 문제에서 시간제한이 1초라고 한다면, "당신의 프로그램은 3-5억 번의 연산 안에 답을 내고 종료되어야 한다"는 의미! 시간복잡도 입력의 크기와 문제를 해결하는 데 걸리는 시간의 상관관계 연산의 수행 횟수는 입력된 개수(n)에 의해 결정..