cococo-coding

문제 분석 a+b+c+....z = s가 되는 자연수 n의 개수를 구한다. 이때 a,b,c 들은 서로 다른 자연수들이고, 이 자연수들의 개수는 1부터 하나씩 더해주어야 최대가 된다. 1+2+3=6 의 예시를 이용해서 반복문으로 i의 값을 1씩 늘려가면서 6(자연수의합)과 같아지는 경우 나오도록 설정했다. 알고리즘 설계 우선 s의 최댓값이 위의 그림에 나와있듯이 매우 크므로, long long 자료형으로 설정한다. sum도 마찬가지로! 이후에 while문으로 1부터 계속해서 더한 값이 sum보다 클 때까지 반복한다. 이때 i는 1로 초기값을 설정하고 i++해준다. 만약 sum > s 라면 i값을 하나 빼주고 break문으로 반복문을 탈출해서 i값을 출력한다. 시간 복잡도 sum을 구할 때까지 while문을..

문제 분석 원본 알파벳과 입력받은 알파벳을 비교하는 문자열 문제이다. 원본 알파벳이 순서대로 다 있다면 true를, 아니라면 false를 출력한다. 알고리즘 설계 이중포문을 이용해 구현했다. 원본을 a , 비교할 알파벳을 b로 설정하고 while문으로 b를 입력받는다. a는 for(int i=0; i> n >> m; //2 string a, b; cin >> a; while(m--) { int cnt = 0; cin >> b; int start = 0; //j값 시작 조절하기 for (int i = 0; i < n; i++) { for (int j = start; j < b.size(); j++) { if (a[i] == b[j]) { cnt++; //cout

문제 분석 캥거루의 위치 a,b,c를 입력받고 양 끝의 캥거루만을 움직이면서 사이를 좁혀나가는 문제이다. 이때 a와 b사이의 위치, b와 c사이의 위치를 비교하여 더 긴 쪽으로 캥거루를 옮겨야 움직이는 횟수를 최대로 늘릴 수 있다. 알고리즘 설계 움직이는 횟수를 구하는 것이 목표이므로 a와 b, b와 c사이의 더 긴 거리를 구하면 끝이다. 그 거리내에서만 캥거루들을 움직일 수 있기 때문에 -1을 해준 값을 출력한다. ex) a:3 b:5 c:9 a나 c캥거루가 캥거루 사이 좌표로 움직여야하므로, a가 b와 c사이로 뛰어간다. 이때 최대횟수로 만들어야하므로 a는 8로 움직인다. 이후로는 c가 다시 7로 움직이고, 다시 a가 6으로 움직이고 ... 이런 식으로 반복이 되므로 결국은 처음에 주어진 좌표에서 긴..

문제 분석 봉우리 겸 활잡이 수를 입력받는다. 각 봉우리 높이는 모두 다르고, 오른쪽으로만 이동하는 상황에서 가장 많은 적을 처치할 수 있는 숫자를 구한다. (문제가 이해가 잘 안 갔는데 '힌트'를 보니 금방 이해가 되었다.) 알고리즘 설계 이중포문을 이용한다. 만약 4개의 봉우리를 입력받고, 각 봉우리가 1번, 2번, 3번, 4번이라고 한다면 i - j 1번 - 2,3,4번 2번 - 3,4번 3번 - 4번 이렇게 비교하도록 한다. 시간 복잡도 봉우리 높이 입력받기 - n 이중 포문 - (n-1)*{(n-1)+(n-2)+(n-3)....} -> 대략 O(n2) 코드 #include #include #include using namespace std; /* 1. 봉우리 겸 활잡이 수를 입력받는다. 2. 봉..

문제 분석 좌석배치에 따라 컵홀더 개수가 달라지며, 컵홀더를 사용할 수 있는 사람 수를 구하는 문제이다. S는 일반 좌석, L은 커플석이며 L은 항상 쌍으로 두 좌석이 붙어있다. 양 끝좌석에는 컵홀더가 무조건 존재한다. 이러한 특징에 따라 코드를 구성했다. 알고리즘 설계 우선 string형으로 좌석을 입력받았다. 그리고 for문으로 좌석중에 'S'가 있다면 일반좌석 수(cnts)를 카운팅, 아니라면 커플석이므로 커플석 수(cntl)를 카운팅했다. 이때 커플석은 무조건 두 좌석이 붙어있으므로, 커플석좌석을 다 구한 뒤에는 2로 나누어줘야 한다. 컵홀더의 총 개수를 구해보자. 우선 일반좌석 수+커플석좌석 수를 더한 총 좌석수에서 1을 빼준 개수에 좌석 양쪽 끝에 무조건 2개를 더해주면 구할 수 있다. int..

문제 분석 두 정수 a,b를 받아서 5와 6 숫자들을 변경하여 두 수의 최댓값을 구하는 문제이다. 모든 수가 6일때의 합이 최댓값이 되고, 모든 수가 5일때의 합이 최솟값이 된다. 알고리즘 설계 a와 b를 string으로 받는다. 5와 6을 치환해야하는 부분이 있기 때문! 만약 각 인자의 '5'가 있으면 '6'으로 치환해서 max값을 구해준다. 이때 stoi함수로 a와b를 각각 int형으로 변경해준뒤에 max를 구해준다. min도 동일하게 구해준다. stoi함수는 괄호안에 바꿀 string을 넣어줘야한다. int max = stoi(a) + stoi(b); 코드 #include #include using namespace std; /* 1. 정수 a,b를 받는다. 2. 정수 중 5와 6을 찾는다. 3. ..

문제 분석 우선 그리디 알고리즘의 문제이다. 문제를 보면 '버튼 A,B,C를 누른 횟수의 합은 항상 최소가 되어야 한다. ~ 10번은 최소 횟수가 아니기 때문에 답이 될 수 없다'라는 문구를 보면 그리디임을 알 수 있다. 그리고 맞춰야 할 조건들이 몇 개 있다. 1. T초를 맞추지 못하면 음수-1을 출력한다. 2. 버튼 조작 횟수를 출력할 때 해당 버튼을 누르지 않는 경우는 0을 출력한다. 이 부분만 주의하면 무난하게 풀 수 있는 문제였다. 알고리즘 설계 우선은 요리시간을 초단위로 변환해서 (300초, 60초, 10초) 벡터로 만들어준다. 그리고 버튼클릭횟수도 총합이 아니라 각 버튼별 횟수로 출력해야하므로 벡터(나 배열)로 만들어준다. 기본적으로 벡터의 개수만 넣어서 만들어주면 자동으로 0으로 초기화된다..

그리디 알고리즘의 첫 문제를 풀어봤다. 문제 분석 그리디 알고리즘의 문제이다. 타로가 지불한 돈을 입력받아 1000엔에서 뺀 값(change)을 잔돈으로 치환하는 문제이다. 문제를 보면 '언제나 거스름돈 개수가 가장 적게 잔돈을 준다'라는 구문이 있다. 보통 그리디 알고리즘은 '가장 적게'나 '가장 많게' 이런 식으로 많이 나온다고 하던데 문제를 잘 살펴보면 쉽게 찾을 수 있다. 알고리즘 설계 잔돈(500, 100, 50, 10, 5, 1)들을 배열이나 벡터에 담아서 쭈루룩 훑는 방식이 편하다. 큰 순으로 담아야 잔돈 개수가 적어지므로, 500부터 벡터에 담았다. change를 잔돈으로 나눈 몫-> 동전 개수 change를 잔돈으로 나눈 나머지-> 새로운 change 이 구문을 반복한다. 아래는 예제를 ..