문제 링크 www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 설명 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 요약을 하자면 저 한 문장으로 대체 가능합니다. 또한 성적이 일반 점수가 아니라 순위이기 때문에 낮을수록 좋습니다. 일반적으로 생각하는 이중 포문으로 푼다면 시간 초과가 뜨기 때문에 '그리디' 스럽게 풀어내야 합니다. 접근 방법 ..
알고리즘/ps
https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수 www.acmicpc.net 2 이상의 짝수는 2개의 소수를 더한 값과 같다는 내용입니다. 그렇다면 어떤 소수의 합으로 표현이 가능한가? 만약에 여러 경우가 존재한다면 그중에서 소수끼리의 차이가 가장 적은 것으로 출력하시오. 접근 단계 n까지의 소수를 구한다 가능한 소수 합의 조합을 구한다. 여러개라면 이 중에서 차이가 가장 적은 것을 출력한다. 시간 초과 난 소스 코드 1 2 3 4 5 6 7 8 9 1..
https://www.acmicpc.net/problem/10610 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶� www.acmicpc.net 문제 요약 입력받은 값으로 만들어낼 수 있는 수가 30의 배수라면 그중 가장 큰 값을, 배수가 아니라면 -1을 출력하라. 접근법 문제 분류를 보면 정수론이라고 되어있습니다. 위키 피디아에 따르면 '정수론(整數論, 영어: number theory) 또는 수론(數論)은 수학의 한 분야로, 각종 수의 성질을 대상으로 한다' 라는 군요. 30의 특성을 파악해봅시다. 30은 일단 뒤에 0이 없으면 안 되..
https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 www.acmicpc.net 문제 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의..
https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번� programmers.co.kr 문제 설명 n명의 학생이 있습니다. lost에는 체육복을 잃어버린 학생의 번호가 있고, reserve에는 여분의 체육복을 가져온 학생의 번호가 있습니다. 해당 번호는 체격 순으로 부여한 번호이므로 +1 혹은 -1 번호의 학생에게만 체육복을 빌려줄 수 있습니다. 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요. 유의..
https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수�� programmers.co.kr 문제 요약 마라톤 참가자 문자열 리스트 participarticipant 가 주어지고 완주한 선수 문자열 리스트인 completion이 주어집니다. 이 두 데이터를 이용해 완주하지 못한 선수를 return 하면 되는 문제입니다. 첫 번째 아이디어 문자열 리스트 중복 제거 이런 식으로 떠올렸습니다. 가장 먼저 떠올린 방법은 set을 이용한 ..
https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정� www.acmicpc.net 문제가 상당히 깁니다만 대부분 Hashing에 대한 개념을 짚고 있습니다. 요약 가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다. 이를 수식으로 표현하면 아래와 같다. 보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다. 우리가 직접 정하라고 하면 힘들 테니까 r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891(..
취직을 위한 코딩테스트를 준비하면서 기본 문제를 못 푸는 친구가 있어서 준비해봤습니다. 얼마나 효율적으로 푸느냐는 후에 생각해도 괜찮습니다. 일단은 풀어나 봅시다!!의 느낌으로 쉬운 문제부터 하나씩 포스팅하려고 합니다. https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 � www.acmicpc.net BOJ의 1152번에 대한 링크입니다. 문제 요약 문자열을 입력받고 총 몇 단어로 이루어져 있는가~ 를 출력하는 문제입니다. 접근법 제일 쉽게 떠올릴 수 있는 방법은 문자열..
그리디 알고리즘이란? 그리디 알고리즘은 해답에 포함될 원소들을 차례로 선택하는 과정을 거치게 되는데, 각 단계에서는 전체적인 상황을 종합적으로 판단하고, 고려하여 결정하는 것이아니라 현 시점의 정보를 바탕으로 가장 이익이 되는 원소들을 선택하는 방법이라고 할 수 있다. 복잡한 과정을 거치지 않고, 상황을 종합적으로 판단하는게 아니기 때문에 매우 빠른 알고리즘이라고 할 수 있다. 이러한 그리디 알고리즘은 최적화 문제를 해결하기 위한 방법이다. 2878번: 캔디캔디 문제 오늘 사탕 M개를 가득 담은 박스가 택배로 택희네 집에 도착했다. 택희는 이 사탕을 N명의 친구들에게 나누어 주려고 한다. 택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 받고 싶은 개수만큼 사탕을 받지 못한다면, 그 친구는..
