웰제오의 개발 블로그

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// 순서대로..

Geeks for Geeks 해외 코딩 관련 플랫폼이 있다 페이스북에서 해외 코딩 인터뷰 관련 그룹 몇개를 팔로우 하고 있는데, 그곳에는 문제와 함께 본인의 풀이를 유튜브에 올려, 문제와 풀이 영상 링크를 함께 포스팅 하는 사람들이 있다 오늘도 문제 하나가 포스팅 되었는데 제목이 무려... Find the size of Largest Subset with positive Bitwise AND 엄청난 길이의 제목에 압도당해 홀린듯이 문제를 확인했고, 푸는데 꽤 애를 먹었던 문제고 내용도 괜찮아서 정리할겸 올려본다 아래는 문제의 링크이다 Find the size of Largest Subset with positive Bitwise AND - GeeksforGeeks Find the size of Large..

2차원 grid 가 주어지는 여러 알고리즘 문제 거의 대부분은 grid 순회 및 탐색이 문제의 해결과정에 포함되어 있고, 이 과정은 dfs, bfs 로 이루어진다. dfs, bfs 에서 중요한건 중복방문을 제거하기 위한 방문처리인데 쉽고 간단한 방법은 동일한 사이즈의 2차원 grid 를 할당받아 해당 자료구조에 방문여부를 표시한다. 이후에 좌표값의 유효여부를 포함해 해당 좌표로의 탐색이 가능한지 판별한다 public static boolean isPosValid(int[][] grid, boolean[][] isVisited, int row, int col) { int rowSize = grid.length; int colSize = grid[0].length; return row >= 0 && col ..

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