웰제오의 개발 블로그

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 접근 인터벌 스케줄링이 생각나는 문제이다. 각 숙제별로 마감기한이 존재하고, 해당 숙제를 했을 때 얻을 수 있는 컵라면의 수가 주어질 때, 얻을 수 있는 컵라면의 최댓값을 구하는 문제이다. 우선 데드라인의 오름차순으로 숙제들을 정렬하고, 동일한 데드라인에 대해서는 컵라면의 개수의 내림차순으로 정렬을 수행했다. 숙제 하나를 푸는데 단위시간 1이 소요되므로, 현재 날짜를 나타내는 변수를 1 부터 증가하면서, ..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 접근법 및 풀이 이제 입력크기를 통해 시간초과를 따지는 과정이 자연스럽게 이루어지는 것 같다 v 완전탐색은 당연히 시간초과가 날 것 이고, 최적화를 진행한다면 dp 인가 싶기도 했지만, 문제의 조건 때문에 모든 케이스에 대해서 상위 문제가 하위 문제를 포함하지 못하므로 dp 도 아니었다. 회의실을 고르는 작업이 시간순서에 따라 제약을 받으므로, 우선 정렬을 수행해야할 것 같은 느낌이 들었고, 이내 예전에 비슷한 문제를 학교수업 때 들은 기억이 났고, 정렬을 통한 그리디 문제였음이 떠올랐다 그리디 하게 회의실을 선..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 접근법 주어진 랜선들에 대해, 이 랜선들에서 동일한 L 이란 길이만큼의 랜선들을 잘라내어, 그 총 합이 N 을 만족하는지 확인하면 되는, 조건 자체는 간단한 문제이다 다만 랜선 최대의 길이가 2^31 - 1 점을 미루어 보아 브루트포스는 시간 초과가 난다 탐색 하는데 있어서 발생하는 시간을 줄이는건 이분탐색, 그 중에서도 대표적인 파라매틱 서치 문제의 유형이다 풀이 및..

https://www.acmicpc.net/problem/23560 23560번: 약 백준이는 $N$일 동안 약을 먹어야 한다. 약은 아침, 점심, 저녁에 한 번씩 먹어야 하고, 한 번 먹는 약은 약 봉투에 담겨있다. 약 봉투는 $3N$개가 일렬로 붙어 있고, {(아침 약), (점심 약), (저녁 약)} www.acmicpc.net 접근법 나는 아직 ps 내공이 부족해서 그런지 문제를 딱 보고 이런 유형이겠다 싶은게 떠오르지가 않는다 늘 그렇듯 브루트 포스, 완전탐색 수행 이후 해당 풀이에서 최적화를 진행하는 식으로 문제를 접근했다 배열 arr 를 자연수 1 ~ N 까지 오름차순으로 채운 뒤, 약을 구분하기 위해서 원소를 2로 나눈 나머지를 통해 아침, 점심, 저녁 약을 구분했다 완전 탐색을 수행할 경우..

25635번: 자유 이용권 (acmicpc.net) 25635번: 자유 이용권 자유 이용권은 놀이공원의 모든 놀이기구를 횟수의 제한 없이 마음껏 이용할 수 있는 이용권이다. 준원이는 ANA 놀이공원의 자유 이용권을 구매했고, 최대한 많이 놀이기구를 이용할 생각이다. www.acmicpc.net 풀이 이전에 포스팅 했던 INFP 두람 문제와 거의 똑같은 유형이다. 관련된 자세한 풀이는 해당 글을 참조하면 좋을 것 같다 INFP 두람 문제가 원순열이었다면, 이 문제는 원순열의 조건을 따지지 않아도 된다는것이 차이점 그리고 가능 여부가 아닌 최대값을 구하는 것 또한 차이점이다 주어진 입력값에 대해, 연속되는 날에 같은 이용권을 사용하지 않고 최대로 이용 가능한 날짜의 예시를 살펴보자 2 1 1 3// 순서대로..

요근래 다음달에 있을 삼성 SW 역량테스트 대비로 기출문제 몇개를 시간재고 푸는중이다 앞서 두어개 정도는 1시간 ~ 1시간 30분 정도 걸려서 풀리길래 할만하다고 생각했는데 세번째 문제로 끝판왕을 만났다 한 4시간정도 걸린 것 같다 😩 접을까 말까 고민하다가 결국에는 풀렸는데 그 과정에서 몇개 실수한 것 + 테크닉들을 정리해 다음에는 같은 실수를 반복하지 않으려고 한다 아래는 문제 링크이다 https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 지문이..

30분 이내에 풀지 못했지만, 문제를 다각도에서 접근하는 과정이 나중에 도움이 될 것 같아 글을 작성해본다 문제는 다음과 같다 https://www.acmicpc.net/problem/25186 25186번: INFP 두람 옷의 총개수는 C++의 32비트 int 자료형의 최댓값인 2,147,483,647을 초과할 수도 있다. www.acmicpc.net 풀이 과정 사람도 N명이고 옷의 가짓수도 N개면 원순열일 때 무조건 안겹칠텐데? 싶어서 초반에 조금 헤맸다 문제를 다시 읽어보니, 인원수는 N 명 == 옷의 가짓수 가 아니라 종류별로 한벌 이상 존재하는 전체 옷의 합이었다. 브루트 포스 ( 틀린 풀이 ) 처음에는 낭만이 가득한 브루트 포스로 문제를 접근해 보았다 배열을 오름차순으로 정렬 왼쪽부터 배열을 ..

활동중인 교내 ps 모임에서 괜찮은 문제를 하나 공유받았다 알고리즘 풀이글은 왠만하면 포스팅 안하려고 했는데, 생각할거리가 많아서 정리차 한번 적어본다 https://www.acmicpc.net/problem/20309 20309번: 트리플 소트 $N$은 $3, 4, 5$ 중 하나이다. www.acmicpc.net 문제 알고리즘 수업을 듣고 감명받은 윤이는 자신만의 정렬 알고리즘을 만들기로 했다. 윤이가 만든 정렬 알고리즘 "트리플 소트"는 다음과 같이 동작한다. 배열에서 연속한 위치에 있는 세 원소를 임의로 고른다. 세 원소의 순서를 뒤집는다. 예를 들어 세 원소가 순서대로 a,b,c이면 뒤집은 뒤에는 c,b,a가 된다. 배열이 오름차순으로 정렬될 때까지 위 과정을 반복한다. 하지만 윤이는 트리플 소트..