🏆 PS(Problem Solving)

1. 문제 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이과정 입력받는 1,000,000,000보다 작거나 같은 N을 문자열로 입력받고 string을 내림차순 정렬 하여 풀었다. 에 있는 quick sort 함수를 사용하였다. sort 함수의 3번째 인자에 비교 함수을 명시해 주는데 아무것도 명시하지 않으면 오름차순 정렬을 수행한다. sort함수로 string 타입의 문자열을 정렬할때는 시작과 끝을 나타내는 반복자(iterator)를 사용해야 합니다. 내림차순으로 비교하는 함수 : greater() 오름차순으로 비교하는..

1. 문제 https://www.acmicpc.net/problem/2563 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 2. 풀이 과정 처음에는 겹치는 부분을 제외하는 식으로 넓이를 구해야 하나 생각했는데 너무 복잡한 것 같았다. 좋은 로직을 고민을 해보다가 배열의 한칸을 넓이 1로 하는 사각형으로 생각하는 식으로 2차원 배열을 떠올렸다. 먼저 배경인 흰 도화지가 100x100이므로 도화지가 전부 채워진다면 색종이들의 넓이 합은 10000이 될 것이다. 100 x 100인 정사각형으로 구성되어 있는 도화지라고 생각..

1. 문제 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 2. 풀이 과정 핵심 로직 : 정렬, 중복제거, 이분탐색 위 로직들은 C++ 내장 라이브러리, 함수를 사용하면 좀 더 쉽게 표현 가능하지만 아직 수련중이라 직접 구현해보았다. 아이디어 1. 입력 받은 좌표를 long long int 크기의 배열1 에 저장해 놓는다. 2. 배열1과 같은 배열2를 만들고 정렬, 중복 제거 수행 3. 배열2..

1. 문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이과정 일반적인 정렬문제가 시간 제한과 메모리 제한을 고려해야하는 문제이다. 생각 1 10,000,000 크기의 배열을 선언하여 정렬 알고리즘을 수행한다면 10,000,000 x short 자료형(2byte) = 20,000,000 byte이다. 1 MB = 1024KB = 1024 x 1024 Byte (단위가 바뀔때 마다 2의 10제곱씩 커진다.) 따라서 20,000,000 byte = 19.0..

1. 문제 https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 2. 풀이 과정 1. 후위 표기식을 문자열로 받고, 알파벳에 치환되는 숫자를 인덱스를 [알바펫-65]로 하는 크기 26의 배열에 저장한다. 2. 문자열의 첫번째 문자부터 탐색을 한다. 해당 문자가 피연산자(A ~ Z)면 스택에 Push 해당 문자가 연산자(+, -, / , *)라면 스택에서 피연산자 2개 pop 시킨 후 연산 수행, 결괏값 스택에 Push 💡주의할 점! 스택에..