https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 처음에 보면 당황스러운 문제일 수 있다. 문제 경험이 많이 없다면 이거 어떤 아이를 어디로 옮기는지 브루트 포스로 풀어야 하는지 감조다 찬 올 수 있다. 하지만 문제를 조금씩 풀다보면 상당히 익숙한 느낌을 지울 수 없다. 분명 나는 이전에 비슷한 문제를 푼 적이 있단 말이다!! 그래서 움직이는 아이와 움직이지 않는 아이를 따로 표시해보니, 무슨 알고리즘을 써야하는지 감이 왔다. 바로 증가하는 수열의 최대..

https://www.acmicpc.net/problem/5073 5073번: 삼각형과 세 변 각 입력에 맞는 결과 (Equilateral, Isosceles, Scalene, Invalid) 를 출력하시오. www.acmicpc.net 가볍게 브론즈로 풀었다. 대신 문제를 어떻게 간결하게 논리적으로 깔끔하게 풀 수 있는가에 대해서는 충분히 고민해보면 좋은 문제이다. 그리고 입력되는 라인 수가 정해져 있지 않으므로 이에 대해서도 잘 정리해볼 수 있는 문제였다. 항상 string 파싱할 때 substr가 유용하므로 사용법을 익혀둘 필요가 있다. #include #include #include using namespace std; int a,b,c; vector parsed_nums(string str) {..

https://leetcode.com/problems/game-play-analysis-ii/ Game Play Analysis II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com player_id별로 최초 사용한 device_id를 출력한다. 대신 이번에는 GROUP BY를 사용하지 않고, player_id와 최소 event_date를 뽑아서 이와 매치되는 row를 출력해 player_id, device_id를 출력한다. 즉 앞서 풀었던 1단계를 활용하되,..

https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 엄청나게 실수한 부분을 못 찾아서 한참 헤맸다.. 여기서는 2차원으로 단순히 다이나믹 프로그래밍을 하면 안되고 방향에 따라 비용에 차이가 생기므로 배열에 따라 추가적으로 다이나믹 프로그래밍을 하기 위해 3차원 배열을 써야한다. → total_cost[r][c][dir] 그리고 난 훨씬 공식을 알아보기 쉽도록 바텀업 스타일로 다이나믹 프로그래밍을 만들었다. D..

이 문제를 다이나믹 프로그래밍을 활용해 조금 더 난이도 있게 풀려면 풀 수 있으나, 기본적으로 N, M이 작기 때문에 다이나믹프로그래밍을 활용해 효율을 추구하지 않아도 되는 문제이다. 그리고 자칫 다이나믹프로그래밍을 잘못 활용했다가 왕창 틀려버렸다..ㅠㅡㅜ 아래 코드를 기반으로 다이나믹 프로그래밍을 수행하면 출발점에 따라 제한되는 방향이 생겨서 최소 비용이 달라진다. 따라서 다이나믹 프로그래밍으로 기록하지 않고 바로바로 검색하는 방향으로 했다. 그리고 다이나믹 프로그래밍 시에 주의해야할 점은, 최소 비용의 중복 가능성이다. 만약 A라는 방향과 B라는 방향에서 오는 값이 같다면 이 두 방향중 무얼 선택하느냐에 따라 이후의 방향 전개에 영향을 미치기 때문에 두 방향 모두 탐색해보기 위해 DP를 바텀업으로 접..

https://www.acmicpc.net/problem/19941 19941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 전형적인 그리디 문제이다. 처음에 문제를 이해하지 않고 풀려고 한다면 사람에 대해 햄버거를 매칭하며 브루트 포스 식으로 최대 매칭 값을 구하려고 할 것이다. 하지만 조금만 더 고민해보면 만약 어떤 사람에 대해 K 범위 내의 매칭될 수 있는 햄버거가 여러 개라면 최대한 현재 진행 중인 방향의 역에 있고(예를 들어 오른쪽으로 사람을 매칭해나가면 최대한 왼쪽에 있는 햄버거를 매칭해주기)는 햄버거를 매..