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

1. 문제이해https://www.acmicpc.net/problem/2563 가로, 세로의 크기가 각각 100인 정사각형 모양의 도화지가 존재한다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 것이 목표이다.  2. 문제 풀이 실버 5의 단순 구현 문제이다. 문제를 처음 접근하면서, 단순히 색종이를 하나씩 붙인다는 생각으로 접근하면 매우 복잡한 문제가 되어버린다.하나씩 종이를 붙여가면서 겹치는 영역을 빼줄 생각을 하면 어렵다는 거다.몇개의 색종이를 붙일지도, 몇개의 색종이가 겹칠지도, 겹치는 영역이 몇개일지도 정해진 것이 ..

1. 문제이해 https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net 다음과 같은 피보나치 함수를 koong(n) (꿍 피보나치) 라고 할 때, 입력받은 n번째 꿍 피보나치를 출력하는 프로그램을 만드는 것이 목표이다. n 3 : koong(n − 1) + koong(n − 2) + koong(n − 3) + koong(n − 4) 2. 문제풀이 간단한 DP문제이다. 사실 친..

1. 문제이해 https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어지고, 그 다음 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소가 주어진다. 이때, 비밀번호를 찾으려는 사이트 주소의 비..

1. 문제이해 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있을 때, 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 것이 목표이다. 2. 문제풀이 주어진 수열에서 합이 M이 되는 연속되는 경우의 수를 구하는 문제이다. 연속된 수들의 합만 취급하기에 그..

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/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 다음과 같은 규칙을 따르되, N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 구현하는 것이 목표이다. 1. 2부터 N까지 모든 정수를 적는다. 2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. 3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. 2. 문제풀이 2부터 N까지의 자연수를 입력받고, K번째 지워지는 숫자를 찾는 문제..

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. 문제이해 1359번: 복권 (acmicpc.net) 1359번: 복권 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 다음과 같은 룰의 복권이 있을 때, 지민이가 복권에 당첨될 확률을 구하는 것이 목표이다. “1부터 N까지의 수 중에 서로 다른 M개의 수를 골라보세요. 저희도 1부터 N까지의 수 중에 서로 다른 M개의 수를 고를건데, 적어도 K개의 수가 같으면 당첨입니다!” 2. 문제풀이 지민이가 1부터 N까지의 수 중에 서로 다른 M개의 수를 골랐을 때, 복권과 적어도 K개의 수가 같으면 당첨이다. 조합, 확률 관련 문제로 고등학교 문제 푸는 것과 비슷한 느낌을 받았다.풀이 방법은 아래 그림과 같다. 문제의 예제 입력 4에 대한 풀이 예시이다.위 풀이방법을 일반화해보면 ..

1. 문제이해 https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 상근이는 길을 걷다가, 신기한 기계를 발견했다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었고, 버튼을 누르면, 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다. 버튼을 K번 눌렀을 때, 화면에 A와 B의 개수를 구하는 것이 목표이다. 2. 문제풀이 A와 B의 갯수를 찬찬히 살펴보면 바로 규칙을 찾을 수 있는 간단한 DP문제이다. 아래 표를 살펴보자. 버튼..