코후닝

알고리즘 분류: 구현 문제 링크: https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net 【 풀이 】 점수의 개수(n), 태수의 새로운 점수(score), 랭킹 범위(r) 선언 랭크를 저장할 변수(rank_count) 선언 랭킹 리스트 입력 받기 랭킹을 순회한다. -> 기존 점수보다 새로운 점수가 작으면 rank_count +1 점수가 같으면 rank_count 유지 배열 범위에서 벗어나는 점수이면 rank_count = ..

알고리즘 분류: 구현, 그리디 알고리즘 문제 링크: https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 【 풀이 】 입력받을 보드판과 최종 결괏값을 선언한다(string). '.' 이 나올 때까지 순회한다. 한 글자씩 검사해, 글자가 'X'이면 카운트를 센다. '.' 이 나왔을 때 카운트가 홀수이면 반복문을 빠져나와 -1 을 출력한다. '.' 이 나왔을 때 카운트가 짝수이면 결괏값에 '.' 추가 카운트가 2가 되면 결과값에 "BB" 추가 카운트가 4가 되면 결과값에 "AAAA" 추가 최종 결과 출력 【 코드 】 #include #include usin..

알고리즘 분류: 구현, 문자열 문제 링크: https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 【 풀이 】 각 문자들이 끊기지 않으면서 연속해서 나타나는 경우의 단어의 개수를 세는 문제이다. 우선 각 문자의 등장 여부를 나타내는 알파벳 배열을 선언. 테스트 케이스 내에서 문자열을 입력받은 뒤 문자열의 각 글자를 검사. 이미 글자가 한번 나왔고, 연속되지 않는다면 break. 여기에 해당하지 않는다면, 글자에 해당하는..

알고리즘 분류: 자료구조, 우선순위 큐 문제 링크: https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 【 풀이 】 C++ STL의 priority_queue(우선순위 큐)를 이용하면 쉽게 해결할 수 있다. 우선순위 큐는 큐의 한 종류로, 우선순위에 따라 정렬된 큐이다. 특정 원소가 삽입(push)되면 주어진 우선순위에 따라 큐가 정렬되고, 삭제(pop)은 정렬된 큐의 맨 앞에서 이루어진다. 특정 원소를 삽입해서 생기는 정렬 과..

알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 【 풀이 】 피보나치 함수의 호출 횟수를 출력하는 문제이다. 문제의 코드에 호출될 때마다 횟수를 더해주는 코드를 작성해서 그 횟수를 출력하면 당연히 시간 복잡도에 걸려 시간 초과가 발생하게 된다. 하지만 그 횟수 출력으로 우리가 따로 횟수를 확인해 규칙을 찾고 점화식을 도출해 동적계획법으로 해결하면 된다. 규칙을 찾아본 결과 n[0] = 1 n[1]..

알고리즘 분류: 수학, 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 【 풀이 】 수학적 사고와 동적계획법을 이용하여 해결하는 문제이다. 문제에서 원하는 건 피보나치 수를 저장하는 배열 F가 주어졌을 때, F[n]에 해당하는 피보나치 수를 구하는 데 필요한 코드1에 해당하는 한 줄, 코드2에 해당하는 한 줄이 각각 몇번 실행되는지를 구하는 것이다. 직접 해보면 알 수 있지만, 결국 코드1은 n이 ..