본문 바로가기

분류 전체보기311

[백준] 1715번 문제풀이 문제 : www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 알고리즘 : 1. 입력을 받은 뒤 priority heap(우선순위 힙) 에 push함. 2. pop을 하면 최솟값이 나옴. pop을 2번 하고, 이걸 더한걸 Sum에 더함. 3. pop 2번한걸 push함. 4. 이 과정을 반복함 (n-1번) #define _CRT_SECURE_NO_WARNINGS #include #define MAX_SIZE 100001 int heap[MAX_SIZ.. 2021. 4. 9.
[알고리즘] Counting Sort 구현 Counting Sort는 O(n)의 시간을 가지고 있다. 매우 빠른 시간복잡도임을 알 수 있다. 대신 한정된 입력에서 나온다는 보장이 있어야 한다. 5, 2, 1, 3, 4, 2, 1, 3, 2, 4, 5, 1, 2, 4, 5 이 배열을 Sorting 하면 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5 이렇게 된다. 그럼 구현은 굉장히 단순하게 할 수 있다. 그냥 1,2,3,4,5 각각의 개수를 세서 배열에 저장한 후 출력하면 된다. 근데 만약 1, 100 같은 경우에는 어떻게 될까? 1을 출력한 뒤, 100을 출력하려면 2~99까지의 의미없는 반복을 진행하여야 한다. 이런 문제점을 없앤게 바로 아래의 코드이다. 각각의 좌표를 지정한 후에, 좌표에 숫자를 꽂아넣는 방식이.. 2021. 4. 8.
[알고리즘] 삽입정렬(Insertion Sort) 알고리즘 보호되어 있는 글 입니다. 2021. 4. 8.
포브스 선정 가장 이상한 자세로 자는 강아지 1위 이빵돌 2021. 4. 8.
[백준] 10162번 문제풀이 문제 : www.acmicpc.net/problem/10162 알고리즘 : 1. T의 1의자리가 0이 아니라면, -1을 출력함. 2. T/300이 1보다 크면, T = T - ((T/300) * 300) 을 하고, 5분 Count를 T/300개 더함. 3. T/60이 1보다 크면, T = T - ((T/60) * 60) 을 하고, 1분 Count를 T/60개 더함. 4. T/10이 1보다 크면, T = T - ((T/10) * 10) 을 하고, 10초 Count를 T/10개 더함. 소스코드 : #define _CRT_SECURE_NO_WARNINGS #include int main(void) { int T; scanf("%d", &T); int five = 0; int one = 0; int ten = .. 2021. 4. 7.
[백준] 1946번 문제풀이 문제 : www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 알고리즘 : 1. 왼쪽 기준으로 구조체를 Sorting. 2. 오른쪽에서 1이 나올 때 까지, 왼쪽[0]의 오른쪽 보다 작으면 count++ 3. count 출력 이렇게 하면 실패한다. 그 이유는 2번에서 왼쪽[0]의 오른쪽이 고정된게 아니고, 왼쪽[0]의 오른쪽보다 더 작은게 나오면 갱신을 시켜줘야한다. 그래야 문제에서 요구하는 조건에 맞을 수 있다. 소스코드1(틀린거) : #d.. 2021. 4. 7.

티스토리툴바