본인이 PS를 하면서 자주 사용하는 STL들을 정리하겠습니다. 1. vector동적배열이다. 임의의 위치에 있는 원소 접근과, 뒤에서 원소를 추가하는 연산은 O(1)(분할상환분석)을 보장한다. 2. stack스택 자료구조이다. 3. queue큐 자료구조이다. 4. deque동적배열이다. 임의의 위치에 있는 원소 접근과, 앞과 뒤에서 원소를 추가하는 연산은 O(1)을 보장한다. 5. set균형잡힌 이진트리이다. 원소 삽입과 삭제, 탐색 등의 연산은 O(logn)을 보장한다. 6. pair2개의 데이터를 저장할 수 있는 변수이다. 비교 연산시 1순위 first 2순위 second로 판별한다. 7. map딕셔너리 자료구조이다. 원소 삽입과 삭제, 탐색 등의 연산은 O(logn)을 보장한다. 8. algorit..
** 본문은 C에 대한 기본적인 이해가 있음을 가정하고 작성하였습니다. 기본적으로 a+b연산을 하는 코드는 다음과 같다. 헤더파일은 C의 헤더파일을 모두 사용할 수 있고 거기에 추가적으로 stl 컨테이너들도 사용할 수 있다.using namespace std; 문장은 c++에서 사용되는 문법으로 이름공간중 std라는 이름공간을 그냥 사용하겠다는 뜻이다.이 문장이 없다면 std 이름공간에 포함된 cin이나 cout함수는 std::cin과 std::cout 등과 같은 방법으로 사용해야 한다.이러한 타이핑의 귀찮음을 없애기 위해 위 문장을 헤더파일 밑에 선언한다. 헤더파일은 cin, cout 등 c++에서의 기본 입출력 함수및 기타 등등을 포함하는 기본적인 헤더파일이다.cin은 입력 함수이다. 별도의 입력타입..
** 평소 생각하던 문제 해결 전략들을 적어나갈 생각이다. 1. x좌표와 y좌표를 분리해서 생각하기x좌표만 있다고 생각하고 문제를 더 쉽게 풀어보고 이후에 y좌표를 추가하면 어떻게 풀 수 있는지 생각하는 접근 방법이다. 2. 순서를 강제하기주어진 문제가 임의의 순서를 추가 하였을 때 더 쉽게 접근할 수는 없는지 생각해보는 접근이다.보통 dp문제에서 많이 사용하는 접근 방법이다. 3. 주어진 문제를 반으로 나누기주어진 문제를 반으로 나누었을 때 왼쪽 범위에서 시작하고 오른쪽 범위에서 끝나는 답을 비교적 구하기 쉬운지 \(O(n)\)판단하여 분할정복으로 푸는 접근 방법이다. 4. 뒤에서부터 생각하기보통 앞에서 부터 결정하면 결정하기 난해한 문제들은 뒤에서부터 결정하였을 때 쉽게 풀리는 경우도 있다. 5. 일..
PS에서 사용하는 복잡도는 시간복잡도와 공간복잡도가 있다. 시간복잡도는 프로그램 수행시간을 분석하는 것이고 반복문에 크게 영향을 받는다.빅오 표기법에서 입력의 크기가 n일 때 주어진 프로그램의 수행시간이 \(5n^4-7n^3+n^2+4\) 의 식을 가진다면.최고차항의 계수와 그보다 낮은 차수의 항을 제외시켜 \(O(n^4)\)와 같이 표기한다.주어진 입력의 크기가 n이라고 하였을 때 아래와 같은 코드들은 각각의 시간 복잡도를 가진다. 주어진 순서대로 위가 가장 빠르다.PS에서 보통 1억을 1초로 잡고 계산한다.예를 들어 n이 1000이라면 6번 이하로는 가능한 알고리즘이다. 공간복잡도는 프로그램의 메모리 사용량을 분석하는 것이다.간단하게 사용한 배열의 크기 * (해당 자료형의 크기) 로 계산한다. 보통 ..
그릇 모으기 문제 n개의 그릇 더미가 있다 각 그릇 더미는 최대 h개의 그릇이 쌓여있고 항상 큰 그릇 위에 작은 그릇을 놓을 때 주어진 연산들을 사용하여 한 개의 그릇 더미로 만드는 최소 연산 횟수를 구하는 문제이다. 문제 풀이 문제를 좀 더 단순화하여 약한 조건으로 생각해보자.0번 그릇 더미를 새로 만들고 여기에 우리가 최후의 더미를 만든다는 조건과,모든 그릇의 크기는 각각 다르다는 조건을 추가해보면 우리는 주어진 접시들을 소팅한 후 가장 큰 접시부터 0번 그릇 더미위에 올리면 된다.따라서 현재 크기의 접시를 0번 그릇 더미 위에 올리는데 드는 연산 횟수는 다음과 같다.먼저 현재 크기의 접시를 해당 그릇 더미 맨 아래 (그보다 큰 접시는 이미 0번 그릇 더미로 옮겨 졌기 때문에) 에서 분리하기 위해서는..
삼성 소프트웨어 역량테스트 대비 문제 추천 14499 주사위 굴리기12100 2048(Easy)13460 째로탈출 213458 시험 감독10875 뱀2468 안전 영역1938 통나무 옮기기1600 말이 되고픈 원숭이2931 가스관1937 욕심쟁이 판다2638 치즈9376 탈옥5427 불3055 탈출1726 로봇2169 로봇 조종하기1194 달이 차오른다, 가자.2156 포도주 시식11727 2xn 타일링 211055 가장 큰 증가 부분 수열11066 파일 합치기2602 돌다리 건너기1022 소용돌이 예쁘게 출력하기3020 개똥벌레1939 중량제한3079 입국심사
주사위 굴리기 문제 지도 위에서 주어진 명령에 따라 주사위를 굴린다. 각 명령에 대해서 주사위 맨 윗면의 값을 출력하는 문제이다. 문제 풀이 시뮬레이션 문제이다. 명령이 K번 존재하므로 \(O(K)\)로 해결가능하다. 주어진 그림과 같이 항상 맨 윗면이 1 바닥과 닿아 있는 면을 6으로 생각하고 구현해보자. 오른쪽으로 구르는 경우를 예시로 들면 1. 먼저 구를수 있는지 판단(다음 좌표가 지도 내부인지) 2. 다음 주사위 상태에서 2번과 5번 면은 변하지 않는다. 오른쪽이므로, 현재 1번 면이 다음 3번 면으로 현재 4번 면이 다음 1번 면으로 현재 6번 면이 다음 4번 면으로 현재 3번 면이 다음 6번 면으로 바뀌게 된다. 3. 다음 상태공간을 만들었다면 6번 면과 지도 값을 비교하여 문제에 주어진 조건..