컴굥일지

문제 https://www.acmicpc.net/problem/15904 문제 내용 문자열을 입력받아 임의의 문자를 적절히 제거하여 UCPC를 만들 수 있는지 없는지를 판단하는 문제이다. 가능하다면 I love UCPC를, 불가능하다면 I hate UCPC를 출력하면 된다. 문제 풀이 공백이 포함된 문자열을 입력받기 위해 getline() 함수를 사용한다. 이후 find() 함수를 사용하여 U C P C의 위치를 받는다. 참고로 find() 함수는 대상문자열.find(찾는 대상, 시작 위치)의 방식으로도 쓸 수 있다. (찾는 대상이 존재하지 않으면 -1을 반환한다.) 앞의 문자의 위치를 뒤의 문자의 시작 위치로 주면, find() 함수가 반환하는 위치가 U

문제 https://www.acmicpc.net/problem/4583 문제 내용 입력받은 문자열이 거울상 문자열인지 확인하고, 맞으면 거울에 비춰지기 전 모습을, 그렇지 않으면 INVALID를 출력하는 문제이다. 문제 풀이 일단 거울상 문자에 해당하는 'b', 'd', 'p', 'q', 'i', 'o', 'v', 'w', 'x'를 미리 배열로 만들어둔다. #이 입력될 때까지 문자열을 계속 입력받기 때문에, while 반복문 안에서 문자열을 입력받고 #인지 아닌지 확인하는 과정이 필요하다. 위 과정이 끝나면, 문자열의 각각의 문자에 대해서 거울상 문자인지 아닌지를 판단하는 과정을 거치면 된다. find()를 통해 문자가 reflect 배열 안에 존재하지 않으면 결과는 INVALID가 된다. 문자가 거울상..

문제 https://www.acmicpc.net/problem/9009 문제 내용 하나의 양의 정수를 최소한의 피보나치 수들의 합으로 나타내면 된다. 문제 풀이 일단 먼저 피보나치 배열을 만들어두었다. 입력이 1,000,000,000 이하의 수로 들어오기 때문에, 피보나치 수를 45 정도까지 구해두면 문제를 푸는데 문제가 없었다. 숫자를 입력받고 나서는, 반복문을 통해 문제를 해결해 나갔다. 하나의 테스트 데이터에 대해, 역순으로 피보나치 수와 비교하며 진행했다. (코드를 보면 이해가 갈 것이다.) 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0..

문제 https://www.acmicpc.net/problem/1026 문제 내용 정수 배열 A와 B의 원소의 곱이 최소가 되도록 하는 함수 S를 만드는 문제이다. 문제 풀이 문제에는 배열 B를 재배열하지 말라고 되어있다. 하지만 굳이 문제를 그렇게 풀 필요는 없어 보인다. (B를 기준으로 A를 맞추는 건 너무 일이 많아 보인다....) 배열 A와 B 모두 정렬하여, A는 앞에서부터, B는 뒤에서부터 곱하여 더한다면 S의 값이 최소가 된다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 int n,tmp; cin >> n; vect..

문제 https://www.acmicpc.net/problem/1448 문제 내용 입력받은 빨대들 중에서 3개를 뽑아 삼각형을 만드는 문제이다. 삼각형으로 만들 수 없다면 -1 출력하고, 만들 수 있다면 세 변의 길이의 합의 최댓값을 출력한다. 문제 풀이 삼각형을 이루기 위해서는 (가장 긴 변의 길이) >..

문제 https://www.acmicpc.net/problem/11582 문제 내용 하나의 배열을 정렬하는데, 이때 중간단계를 출력하는 문제이다. 참고로 여기서 쓰인 정렬의 방식은 합병 정렬이다. (합병 정렬에 대한 설명은 더보기에 있다.) 더보기 더보기 합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 방식이다. 합병 정렬은 분할 정복이라는 기법에 바탕을 두고 있다. 분할 정복 기법은 문제를 작은 2개의 문제로 분할하고, 각각을 해결한 뒤에, 결과를 모아서 원래의 문제를 해결하는 방식이다. 문제 풀이 문제에서 설명한 방식대로 정렬을 진행한다. (sort 함수 이용) 이때, k명이 정렬을 하..

문제 https://www.acmicpc.net/problem/11656 문제 내용 문자열을 입력받아, 접미사를 사전 순으로 정렬하여 출력하면 된다. 문제 풀이 이 문제에서 그나마 가장 까다로운 부분은 접미사를 만들어내는 부분이다. string 클래스의 substr(시작 지점, 문자 개수) 함수를 사용하면 쉽게 해결할 수 있다. 이 문제에서는 반복문을 n부터 시작해서 1씩 감소시켰다. 이는 첫번째 인자를 n-i로 하여 0부터 n-1까지 증가하도록 했으며, 두 번째 인자는 i로 하여 n부터 1까지 감소하도록 했다. ex) [school] => school, chool, hool, ool, ol, l 순으로 저장된다. 코드 #include #include #include #include using names..

문제 https://www.acmicpc.net/problem/20044 문제 내용 학생들의 코딩 역량을 입력받아 두명씩 팀을 짠다. 이때, 팀의 코딩 역량의 차이가 최소화 되어야 한다. 문제 풀이 학생들의 코딩 역량을 입력받아 값을 정렬한다. 그리고 배열의 양쪽 끝에서부터 팀을 만들어가면 된다. (가장 작은 값과 가장 큰 값을 이어주는 것) 코드 #include #include #include using namespace std; int n, a, num, mmin; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //입력 cin >> n; //팀의 개수 vectorv; for (int i = 0; i < 2*n; i++) { /..

문제 https://www.acmicpc.net/problem/16206 문제 내용 롤케이크를 잘라서 길이가 10인 롤케이크를 최대한 많이 만드는 문제이다. 문제 풀이 Q) 롤케이크의 길이가 [10,34,20,14,20]이고, 자를 수 있는 횟수가 2번이라면 어떻게 해야 할까? 1) 그냥 정렬한 뒤에 순서대로 자른다. - 먼저 정렬하면 [10,14,20,20,34]가 된다. 여기서 10은 칼질하지 않아도 되고, 14는 한번, 20도 한 번의 칼질이 필요하므로 10 / 14(10,4) / 20(10,10)으로 총 4개의 길이가 10인 롤케이크가 나온다. 2) 정렬을 하긴 하되, 10 단위의 롤케이크 부터 먼저 처리하는 경우 - 10단위의 길이가 먼저 오도록 정렬을 하면 [10,20,20,14,34]가 된다..

문제 https://www.acmicpc.net/problem/14659 문제 내용 아래와 같이 봉우리들에 활잡이들이 한 명씩 있다. 모든 활잡이는 자신의 오른쪽으로 활을 쏠 수 있으며, 자신보다 낮은 위치의 적만 잡을 수 있다. 최고의 활잡이가 처치할 수 있는 적의 최대 숫자를 출력하면 된다. 문제 풀이 반복문과 조건문을 통해 봉우리의 높이를 비교해야 한다. 위의 사진을 보면, 봉우리가 0번부터 시작한다고 했을 때, 2번과 3번 봉우리를 비교하면 2번이 더 높다. 그렇기 때문에 3번은 자신보다 낮은 봉우리의 개수가 몇 개인지를 구할 필요가 없다. 즉, 자신보다 낮은 봉우리의 개수를 카운트 하다가 자신보다 높은 봉우리를 만나면 지금까지 지나온 낮은 봉우리 개수와, 이전에 카운트했던 개수를 비교하여 max..