초보 개발자의 이야기, 릿허브

1. 문제이해 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하는 것이 목표이다. 2. 문제풀이 듣도 못한 N명의 명단과 보도 못한 M명의 명단이 주어질 때, 듣도 보도 못한 사람들의 명단을 구하는 프로그램이다. 이해하기 쉽게 말하자면, 두 집합의 교집합을 구하는 문제이다. N명의 사람들의 명단을 입력받은 후, M명의 사람들을..

1. 문제이해 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 1. 국어 점수가 감소하는 순서로 2. 국어 점수가 같으면 영어 점수가 증가하는 순서로 3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 다음과 같은 순서로 학생의 이름을 출력하는 프로그램을 작성하는 것이 목표이다. 2. 문제풀이 어렵지 않은 단순 정렬문제이다. C++에 내장된 sort..

1. 문제이해 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 1. 산술평균 : N개의 수들의 합을 N으로 나눈 값 2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값 4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 위와 같은 네 가지 기본 통계값을 구하는 것이 목표이다. 단, 산술평균은 소수점 이하 첫째 자리에서 반올림한 값을 출력하며, ..

1. 문제이해 https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 하루동안 팔린 책의 개수(N)과 팔린 책들의 이름이 주어진다. 이때, 가장 많이 팔린 책의 이름을 출력하는 것이 목표이다. (단, 가장 많이 팔린 책이 여러 개일 경우, 사전 순으로 가장 앞서는 제목을 출력한다.) 2. 문제풀이 팔린 책의 개수(N)와 책의 이름들이 주어질 때, 가장 많이 팔린 책의 이름을 구하는 것이 목표이다. 책의 이름과 해당 책의 판매량을 모두 저장해야하..

1. 문제이해 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 상근이가 가지고 있는 숫자 카드의 개수(N)와 각 숫자카드에 적힌 숫자를 입력받는다. 이어서 정수 M과 M개의 숫자들을 입력받는다. M개의 수들에 대해 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1, 아니면 0을 출력한다. 2. 문제풀이 N과 M의 범위는 무난하지만, 입력받는 숫자의 범위가 꽤나 크다. (-10,000,000 N; for (int..

1. 문제이해 https://www.acmicpc.net/problem/11931 11931번: 수 정렬하기 4 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net N개의 정수가 주어질 때, 이를 내림차순으로 정렬하여 출력하는 것이 목표이다. 2. 문제풀이 앞서 풀이한 수 정렬하기 1, 2와 거의 동일한 문제이다. (수 정렬하기 3의 경우에는 앞선 풀이방법대로 하면 시간초과가 발생했다.) 앞선 문제들과 다른 점이라면 입력받은 숫자들을 내림차순으로 정렬해야 한다는 점이다. C++에서 지원하는 sort 함수의 기본형은 다음과 같다...

1. 문제이해 https://www.acmicpc.net/problem/10867 10867번: 중복 빼고 정렬하기 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. www.acmicpc.net N개의 정수를 입력받아, 중복을 제거해 오름차순으로 정렬하는 것이 목표이다. 2. 문제풀이 N개의 정수를 입력받고, 중복을 제거한 후 정렬하기만 하면 되는 간단한 문제이다. 중복을 제거한다는 점에만 주의해주면 되는데, 필자는 set container를 이용해 풀이했다. set은 key 라 불리는 원소의 집합으로, 중복을 자동으로 제거하고, 삽입이 되면 자동으로 정렬된다. (사실상 set을 쓰면 너무나도 간단한 문..

1. 문제이해 https://www.acmicpc.net/problem/2548 2548번: 대표 자연수 첫째 줄에는 자연수의 개수 N이 입력된다. N은 1 이상 20,000 이하이다. 둘째 줄에는 N개의 자연수가 빈칸을 사이에 두고 입력되며, 이 수들은 모두 1 이상 10,000 이하이다. www.acmicpc.net 모든 자연수들에 대해 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수를 대표 자연수라고 한다. N개의 자연수가 주어질 때, 그 중 대표 자연수를 출력하는 것이 목표이다. (단, 대표 자연수가 2개 이상일 경우, 가장 작은 숫자를 대표 자연수로 출력한다.) 2. 문제풀이 문제의 의도만 잘 파악하면 어렵지 않은 문제이다. N개의 자연수 중 전체 차이의 합을 최소로 하는 값을 찾는 ..

1. 문제이해 https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 2차원 평면위의 좌표들을 y좌표가 증가하는 순으로, y좌표가 같다면 x좌표가 증가하는 순으로 정렬하는 프로그램을 구현하는 것이 목표이다. 2. 문제풀이 2차원 평면 좌표를 y좌표 순으로 정렬하되, y좌표가 같다면 x좌표 순으로 정렬하는 것이 목표이다. 이전에 풀이한 11650번 좌표 정렬하기와 흡사한 문제이다. 해당 문제에서는..

1. 문제이해 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 수직선 위에 N개의 좌표를 압축하려고 할 때, Xi를 좌표 압축한 결괏값이 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. N개의 좌표를 입력받고, 해당 좌표들을 압축한 결과를 출력하는 것이 목표이다. 2. 문제풀이 N개의 좌표들을 입력받아 해당 좌표들을 압축한 결과를 출력하는 것이 목표이다. 압축 방식은 자신보다 작..