정렬6 [Programmers] 귤 고르기 https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 각각 크기 별로 귤을 분류하여 저장할 배열을 만들어, 같은 크기의 귤마다 몇 개씩 있는지를 파악한 다음 배열을 내림차순으로 정렬하면 탐욕 알고리즘에 기반하여 문제를 쉽게 해결할 수 있다. 구현 std::unordered_map 클래스를 활용하면 귤을 크기 별로 몇 개씩 있는지 쉽게 파악할 수 있다. 이때 std::sort() 메서드를 사용해 정렬하기 위해서는 std::uno.. 2023. 12. 6. [Programmers] 튜플 https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 중복되는 원소가 없는 튜플에 대한 집합 표현만 주어지므로, 집합 내에서 중복하여 많이 등장하는 숫자일수록 튜플의 앞에 위치하는 원소임에 착안하여 문제를 해결하고자 하였다. 구현 이를 구현하기 위해, 원소 별로 집합 내에서의 등장 횟수를 카운트할 때 std::unordered_map 클래스를 활용한 다음, pair 형식의 원소들을 std::vector 클래스로 옮겨 등장 횟수에.. 2023. 9. 25. [Baekjoon] 20920번: 영단어 암기는 괴로워 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 문제 해결 과정 착안 문자열을 키로 가지며, 등장하는 빈도 수를 값으로 저장하여 문제를 해결하고자 std::map과 같은 컨테이너를 활용하고자 하였다. 이때 키의 자료형이 문자열 형이므로 해시 테이블(hash table)을 사용하는 것이 일반적으로 속도 측면에서 유리하기 때문에 std::unordered_map 클래스를 사용해 데.. 2023. 7. 9. [Baekjoon] 2108번: 통계학 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 해결 과정 착안 숫자가 입력된 빈도를 나타내기 위한 보조 배열을 선언하여 사용하며, 입력받는 수를 배열에 저장한 다음, 오름차순으로 정렬하여 문제를 해결하고자 하였다. 구현 아래와 같이 입력받는 $n$개의 수를 저장한 다음 오름차순으로 정렬하면 간단하게 문제 해결이 가능하다. 산술평균: 입력받을 때마다 합을 계산하여 마지막에 $n$으로 나누어 계산(-0 처리에 주의). 중앙값: 정렬된 배열의 중간 인덱스 .. 2023. 7. 8. [Baekjoon] 1931번: 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 해결 과정 착안 문제를 처음 접하고 어떻게 해결할 지 막연해서 꽤 오래 고민을 했다. 최대한 많은 회의에 대해 회의실을 배정하려면 어떻게 해야할지 열심히 생각해보다가, 아래와 같은 조건들이 문제 해결의 핵심이라고 생각을 했다. 처음 생각한 조건 회의 시간이 짧은 회의들을 가능한 한 많이 배정한다. 회의실이 비는 시간을 최소로 한다(단, 회의실 배정 가능한 시간에 대해 별도의 제약이 없음에 유의) 위의 조건을 만족하면서 회의를 순차적으로 배정하다보면 결과적으로 최대한 많은 회의에 대해 회의실을 배정할 수 있을.. 2023. 6. 21. [순서론(Order theory)] Strict Weak Ordering의 개념 포스트를 읽으실 때 참고하실 점프로그래밍에 대한 깊은 이해를 쌓고자, 개인적으로 필요한 수학적 지식들을 간략하게만 기록하기 위한 포스팅입니다. 단순한 수준의 프로그래밍을 하기 위해서는 필요하지 않은 내용이 다수 포함될 수 있습니다.만약 포스팅에 잘못된 내용이 있다면 댓글이나 이메일을 통해 알려주시면 수정하겠습니다. 감사합니다. Strict weak ordering집합 $S$에 대하여 다음의 4 가지 조건을 만족하는 동차 관계(homogeneous relation) $strict weak ordering이라고 한다. 비반사성(irreflexibility): 집합 $S$에 속하는 모든 원소에 대해 $a 추이성(transitivity): 집합 $S$에 속하는 원소 $x, y, z$에 대해, $x 비대칭성(a.. 2023. 5. 30. 이전 1 다음
