시간제한 메모리제한 알고리즘 분류 1 초 256 MB 구현, 문자열 문제 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. 출력 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다. 제한 0 ≤ S의 길이 ≤ 100 문제 해결 ..

시간제한 메모리제한 알고리즘 분류 2 초 512 MB 정렬, 값 / 좌표 압축 문제 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. 출력 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.첫째 줄에 S의 최솟값을 출력한다. 제한 1 ≤ N ≤ 1,000,000 -10^9 ≤ Xi ≤ 10^9 문제 해결 조건 ..

#include #include #include #include using namespace std; /* 문제 조건 1. 길이 다름: 시리얼번호가 짧은 것 2. 길이 같: 모든 자리수 합이 작은 것 (숫자) 3. 둘다 같: 사전순 . 숫자 = '0' && str[i]= '9' 일때, sum += str[i]-'0'; */ int sumOfSerial(const string& a) { int sum = 0; for (int i = 0; i = '0' && a[i] > n; vector v(n); f..

시간제한 메모리제한 알고리즘 분류 2 초 512 MB 그리디, 정렬, 스위핑 문제 “호 안에 수류탄!!” 대한건아 욱제는 수류탄 투척 훈련을 받고 있다. 욱제를 필두로, 훈련장에는 욱제를 포함한 N명의 전우들이 일렬(1열 횡대 ㅎ)로 서있다. 군대에 끌려온 사실에 심술이 난 욱제는 수류탄의 안전핀을 뽑아 전우에게 던졌다. 마찬가지로 심술이 난 전우들도 욱제가 던진 수류탄을 받아 전우들에게 던지기 시작했다. 이제 수류탄은 뜨거운 감자처럼 욱제와 전우들 사이를 옮겨 다닌다. 전우들은 팔 힘이 모두 다르기 때문에 수류탄을 던질 수 있는 사거리도 모두 다르다. 욱제와 전우들이 가지고 노는 훈련용 수류탄은 바닥에 떨어지기 전에는 절대 터지지 않는 특수한 수류탄이다. 욱제와 전우들은 특급 전사이기 때문에 사거리 내..

시간제한 메모리제한 알고리즘 분류 5 초 256 MB 정렬, 분할 정복 문제 인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많아 혼자 정렬을 하기에는 많은 시간이 걸려 C.T.P 회원들을 활용하기로 했다. 치킨집이 N개 있다고 가정을 하자. N개의 치킨의 수치를 무작위로 놓은 뒤 N/2명의 C.T.P 회원이 차례대로 2개의 치킨집을 선택해 정렬을 한다. 그 뒤 N/4명이 차례대로 바로 전 단계의 사람이 정렬한 두 개의 그룹을 차례대로 선택 하여 치킨집을 정렬을 한다. 계속해서 N/8명, N/16명이 정렬을 진행하다가 마지막 사람이 두 개의 ..

Merge Sort? : 주어진 문제를 반으로 분할하고 해결한 뒤 다시 병합하는 분할 정복 알고리즘 https://www.youtube.com/watch?v=ctkuGoJPmAE 나동빈님의 merge sort 튜토리얼을 보고 merge sort 배열의 구현에는 성공했다. 다음 단계로, 벡터 컨테이너 클래스로 merge sort를 구현하는 것을 시도했다. #include #include #include #include using namespace std; vectorsorted; //정렬된 데이터를 저장할 벡터 선언 /* i: 분할 후 왼쪽 리스트 j: 분할 후 오른쪽 리스트 k: 복사할 배열의 인덱스 */ void merge(vector& v, int start, int mid, int end) { in..