꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1449 쉬운 그리디(Greedy) 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 상태가 나쁜 파이프의 위치를 입력받고 오름차순 정렬을 합니다.2. 만약 i 번째 파이프가 상태가 나쁘다면 i부터 min(i 번째 파이프 위치 + 테이프의 길이 - 1, MAX)까지를 고쳤다고 표시를 합니다.->min을 쓴 이유는 범위 초과에 따른 런타임 에러 방지 위해->(i 번째 파이프 위치 + 테이프의 길이 -1)인 이유는 전후로 0.5 간격이 필요하기 때문에3. i 번째 파이프가 고쳐졌다고 표시되어있으면 다음 파이프로 넘어갑니다.4. 마지막 파이프까지 2번과 3번을 반복합니다. 그리디 알고리즘으로 분류된 이유는 오름차순으로 정렬된 파이..

문제 링크입니다: https://www.acmicpc.net/problem/1969 그리디(Greedy) 알고리즘으로 분류되어있지만 오히려 브루트 포스(Brute Force) 알고리즘에 가까운 문제였습니다. 처음에 문제에서 요구하는 바를 이해하지 못해서 어렵게 느껴졌는데 이해하고 나니까 엄청 쉬운 문제였습니다.결국 문제에서 요구하는 것은 각 인덱스에서 제일 많이 쓰인 알파벳을 구하고(사전순) 각각의 알파벳의 개수에 대해 Hamming Distance의 누적합을 구하는 것이였습니다. 알고리즘은 아래와 같습니다.1. Cache 배열에 각 인덱스당 A, C, G, T가 몇 개 사용되었는지 기록합니다.->A, C, G, T 순으로 저장하는 이유는 사전순에서 제일 빠른 단어를 출력하기 위해서입니다.2. 반복문을 ..

문제 링크입니다: https://www.acmicpc.net/problem/1543 진짜 간단한 문자열 탐색 문제였습니다.(솔직히 왜 그리디 알고리즘으로 분류되었는지는 모르겠습니다)하지만, string size()와 length()의 반환형이 unsigned int라는 점을 인지 못함과 동시에 문제에서 공백 또한 포함이라는 것을 읽지 못해 수도 없이 틀렸던 문제였습니다.간단히 설명하자면 아래와 같습니다.1. string size()와 length()의 반환형이 unsigned int이기 때문에 주어진 문자열의 크기보다 부분문자열의 크기가 클 경우 underflow가 발생하기 때문에 런타임 에러가 뜹니다.2. 문자열에 공백도 포함될 수 있기 때문에 cin이 아닌 getline을 통해 문자열을 입력받아야합니..

문제 링크입니다: https://www.acmicpc.net/problem/1202 그리디(Greedy) 알고리즘에 우선순위 큐(Priority Queue) 자료구조를 사용해야 했던 문제였습니다. 우선순위 큐 자료구조를 사용하는 부분은 종신1재정2시경3님(http://js1jj2sk3.tistory.com/14)의 코드를 참고했습니다. 알고리즘은 아래와 같습니다. 1. pair형 배열에 보석의 정보를 입력받고 int형 배열에 가방의 정보를 입력받습니다. 2. 보석은 무게를 기준으로 오름차순 정렬을 하고 가방은 최대 무게 허용량을 기준으로 오름차순 정렬을 합니다. 3. 핵심은 한 번 확인한 보석은 다시 확인하지 않는 것입니다. i) 가방의 개수만큼 반복문을 돌립니다. ii) 해당 가방이 허용할 수 있는 보..

문제 링크입니다: https://www.acmicpc.net/problem/1700 고려해야했던 것이 많았던 그리디(Greedy) 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 기기들의 사용 순서들을 입력 받습니다.2. K번 반복문을 돌리는데 이 때 고려해야할 것은 아래의 세 가지입니다.i) 해당 기기가 플러그에 꽂혀있는가ii) 플러그에 빈 곳이 있는가iii) 플러그에 빈 곳이 없는 경우3. 2번의 i) 와 ii) 같은 경우 콘센트를 뺄 필요가 없으므로 continue 해서 다음 기기를 확인합니다.4. 2번의 iii) 경우 콘센트를 빼야합니다.a) 콘센트를 빼야하는데 어떤 콘센트를 빼야하는지를 그리디하게 접근해야합니다.b) 그리디하게 접근하면 이후에 단 한번도 쓰지 않을 기기를 빼거나 제일 마지..

문제 링크입니다: https://www.acmicpc.net/problem/2529 순열을 이용하는 그리디(greedy) 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 그리디하게 접근했을 때 최대 숫자는 9 ~ (9 - K)의 숫자들로 이루어질 것이고 최소 숫자는 0 ~ K까지의 숫자들로 이루어질 것입니다.2. 초기에는 최대 숫자를 내림차순으로 벡터에 저장하고 최소 숫자를 오름차순으로 벡터에 저장한다.3. 2 번에서 구한 벡터들에 대해 반복문을 돌리는데 저장된 숫자들의 위치와 부등호 간에 모순이 없을 때까지 반복한다.i) 최대 숫자에 대해 모순이 발생하면 prev_permutation 함수를 이용하여 해당 숫자보다 작으면서 최대인 숫자로 바꿔준다.ii) 최소 숫자에 대해 모순이 발생하면 next..

문제 링크입니다: https://www.acmicpc.net/problem/1138 간단한 그리디(greedy) 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. 인덱스 번호대로 키가 부여되므로 이미 정렬되어 있는 상태입니다.2. 왼쪽에 자신보다 키 큰 사람의 수를 입력받습니다.3. 자기보다 키 큰 사람이 있는 경우 빈 자리를 지나칩니다.4. 빈 자리이고 2번에서 입력받은 수만큼 키 큰 사람을 지나쳤다면 자신의 자리입니다. #include using namespace std; const int MAX = 10; int N;int line[MAX]; int main(void){ cin >> N; //키 순서 for (int i = 0; i > left;..

문제 링크입니다: https://www.acmicpc.net/problem/2437 문제를 잘 못 읽어서 두번 틀린 쉬운 그리디(greedy) 알고리즘 문제였습니다.문제에서는 한 쪽에만 추를 올릴 수 있다고 했지만 저는 반대쪽에도 올릴 수 있다고 임의로 판단하였기 때문에 틀렸습니다. 알고리즘은 아래와 같습니다.1. 주어진 숫자들을 배열에 넣고 오름차순 정렬을 합니다.2. 다음에 등장하는 숫자가 (누적합 + 1) 이하라면 누적합 + 1까지의 숫자들은 기존의 숫자들의 조합으로 모두 표현 가능합니다. ->초기에 1을 더했으므로 누적합 + 13. 하지만, 다음에 등장하는 숫자가 (누적합 + 2) 이상이라면 기존의 숫자들의 조합으로 (누적합 + 1) 표현이 불가능하므로 (누적합 + 1)을 출력해줍니다. #incl..

문제 링크입니다: https://www.acmicpc.net/problem/1049 그리디(Greedy)하게 접근해서 제일 싼 브랜드 제품을 구매해야한다는 것은 누구나 알 수 있었던 문제였습니다.하지만 패키지와 단품을 동시에 구매하는 경우 꼭 동일 브랜드에서 구매하지 않아도 되는 것이 핵심이였습니다. 알고리즘은 아래와 같습니다.1. 패키지와 단품 가격 각각의 최소 가격을 구합니다.2. 6개 이하인 경우 패키지 혹은 단품만 사기 때문에 패키지 vs (단품 * N)만 비교해주면 됩니다.3. 7개 이상부터는 패키지와 단품을 섞어 사는 경우가 발생할 수 있습니다.i) 패키지를 0부터 (N/6) + 1까지 반복문을 돌리는데 이 때 (N/6) + 1까지 반복문을 돌리는 이유는 실이 9개 필요한데 패키지 2개를 사는..

문제 링크입니다: https://www.acmicpc.net/problem/9012 알고리즘 분류는 스택으로 분류되어있지만 단순 문자열을 이용하여 푼 문제였습니다. 알고리즘은 아래와 같습니다.1. '(' 괄호가 오면 cnt를 1 증가시키고 ')' 괄호가 오면 cnt를 1 감소시킵니다.2. cnt가 0보다 작아지면 정상적인 괄호 문자열이 아니기 때문에 false를 반환합니다. ex) ())(3. 문자열을 다 순회하면 cnt가 0인 경우와 아닌 경우를 살펴봐야합니다.i) cnt가 0이라면 정상적인 괄호 문자열이였기 때문에 true를 반환합니다.ii) cnt가 0이 아니라면 정상적인 괄호 문자열이 아니였기 때문에 false를 반환합니다. #include #include using namespace std; b..