코딩테스트
-
[백준 BOJ/C++] 1987 알파벳알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 16. 01:33
1987번: 알파벳 백트랙킹, DFS를 연습하기 적당한 문제다. 요구사항이 복잡하거나 구현량이 많지 않고 중복된 알파벳을 피해서 가장 멀리 갈 수 있는 경로를 찾아야 한다. 알파벳으로 채워진 맵에서 같은 알파벳을 중복하지 않게 방문하여 갈 수 있는 최대 거리를 구하는 문제다. 시작점은 항상 (0, 0) 이며 상하좌우 한 칸 씩 탐색해 나가면 된다. 몇 몇 실수하기 쉬운 부분이 있는지 정답 비율이 낮은 편이지만 복잡한 문제는 아니라서 백트랙킹, DFS 문제와 관련해 기본기를 쌓기 좋은 문제다. 문제의 포인트 백트랙킹 알고리즘 알파벳의 중복 피하기 백트랙킹 알고리즘 일반적으로 맵 형태의 입력이 주어지고 이동시켜가는 문제는 BFS든 DFS든 탐색 알고리즘을 이용해야하는 경우가 많다. 최단 경로를 찾아야 하는 ..
-
[백준 BOJ/C++] 9663 N-Queen알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 16. 00:06
9663번: N-Queen 알고리즘 공부나 코딩 테스트를 준비하는 사람들이라면 꼭 한번 풀어봐야한다고 할 수 있을만큼 백트래킹을 대표하는 유명 문제다. 컴퓨터가 등장하기 훨씬 전부터 존재했던 문제로 8*8 크기의 체스판에 8개의 퀸을 배치하는 8-Queen 문제에서 시작되었다. Chess에서 Queen은 N * N 크기의 체스판에 정확히 N개까지 서로의 이동 경로를 피해서 배치할 수 있다. 이동 방법도 복잡하지 않아서 프로그램으로 단순화해서 풀이하기도 쉬운 편이다. N의 갯수가 15 미만인 것에서 흰트를 얻는다면 모든 경우의 수를 직접 따져봐야함을 알 수 있다. 하지만 이 문제를 처음 접하면 백트랙킹이나 브루트 포스에 대해 알고있더라도 막상 Queen을 놓는 상황과 앞서 놓은 Queen과의 위치 확인을 ..
-
[백준 BOJ/C++] 1781 컵라면알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 23:56
1781번: 컵라면 주어진 문제 리스트에서 각 시간당 가장 많은 보상을 얻을 수 있도록 최선의 선택을 해야하는 문제다. 문제 설명이 자세하진 않은 편이라 완전히 이해는데 시간이 좀 걸렸다. 풀고 나면 간단하고 구현도 쉽지만 그리디 문제 답게 접근하는 방법이나 아이디어를 떠올리기가 만만치는 않은 문제다. 한 시간에 한 문제씩 풀 수 있는데 각 문제에는 데드라인이 있어서 해당 시간 내에 풀어야 한다. 즉 반드시 그 시간에 푸는 것이 아니라 데드라인 시간 이전 어느 시간이든 풀 수 있다. 또한 데드라인은 얼마든지 중복될 수 있어서 매 시간마다 어떤 문제를 선택하는지에 따라 총 보상 수가 달라진다. 마치 각 조합을 모두 탐색해 최적해를 찾는 문제처럼 보이기도 하지만 문제의 수 N이 200,000으로 커서 모든 ..
-
[백준 BOJ/C++] 1461 도서관알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 23:28
1461번: 도서관 전형적인 그리디 알고리즘 문제이며 단순하다면 단순한 편이지만 처음 접했을 때 문제를 정확히 이해하지 못했었다. 쉬운 편의 문제라고 할 수 있겠지만 문제 설명이 자세하고 친절하지는 않은 편이라 헤맬 수 있는 문제다. 1차원 수평선 위 0에서 시작해 음수와 양수 구간을 효율적으로 이동시키도록 하는 문제다. 한번에 옮길 수 있는 책 수의 제한이 있어서 다시 시작점인 0으로 돌아오는 것을 고려해야 하는데 마지막에는 돌아오지 않아도 된다. 최소 몇 회 만에 옮길 수 있는지 찾아야 한다. 문제의 포인트 한번에 이동시킬 수 있는 책의 수 돌아오는 구간과 마지막 구간 선택 음수 구간과 양수 구간의 표현 한번에 이동시킬 수 있는 책의 수 수평선에서 좌,우로의 이동을 이용하는 문제이므로 우선 그림과 같..
-
[백준 BOJ/C++] 1092 배알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 23:03
1092번: 배 전형적인 그리디 알고리즘 문제이지만 시간 초과 가능성을 고려해야 한다. 특별한 복잡한 스킬이 필요하진 않지만 그리드 적인 접근 방식을 연습하기 좋은 문제다. N대의 크레인에 M개의 박스를 최소 횟수로 옮기는 문제다. 각 크레인에는 무게 제한이 있어서 제한 내의 무게를 가진 박스만 옮길 수 있다. 크레인에 박스를 효율적으로 배분해서 최소 몇 회 만에 옮길 수 있는지 찾아야 한다. 문제의 포인트 그리디 알고리즘 시간초과를 피하는 방법 그리디 알고리즘 Greedy Algorithm은 사실 특별한 기술이나 전형적인 틀이 있는 유형은 아니다. 어찌보면 그만큼 발견이나 아이디어가 중요다고 할 수 있다. 그래도 그리드 알고리즘 문제를 여럿 풀다보면 어느정도 접근 방법에 대한 감을 기를 수 있다. 숫자..
-
[백준 BOJ/C++] 1774 우주신과의 교감알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 22:48
1774번: 우주신과의 교감 크루스칼 알고리즘을 연습해보기 좋은 문제다. 특별히 복잡하게 꼬아놓은 부분은 없는데 사전에 일부 간선만 주어지고 나머지 가능한 모든 간선을 추가하는 과정만 추가되었다. 입력으로 주어지는 모든 노드들 사이에 가능한 모든 간선들을 list up 하고 각 간선의 길이를 계산해두고 이를 토대로 크루스칼 알고리즘을 이용해 최소 신장 트리를 찾아주면 된다. 단, 입력으로 주어지는 이미 연결된 통로는 최소 신장 트리에 반드시 포함되어야 하며 새로 추가한 간선들의 길이의 합을 출력해야 한다. 문제의 포인트 최소 신장 트리를 구할 수 있는가? 간선의 길이는 주어지지 않는다. 최소 신장 트리 사이클 없이 모든 노드를 연결하는 최소 신장 트리 (MST, Minimum Spanning Tree)만..
-
[백준 BOJ/C++] 5719 거의 최단 경로알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 22:37
5719번: 거의 최단 경로 다익스트라 알고리즘을 통해 최단 경로를 찾아내는 전형적인 문제에서 살짝 꼬아서 난이도를 높인 문제다. 문제 이름에서 유추할 수 있듯 최단 경로를 제외한 그 다음 최단 경로를 찾아 그 길이를 출력해야 한다. 예를 들어 아래 그림과 같은 입력이 주어졌을 때 굵은 화살표로 표시된 최단 경로가 아니라 점선으로 표시된 그 다음 최단 경로를 찾아야 한다. 주어진 예제와 같이 최단 경로는 여러개일 수 있으며 이 경우 모든 최단 경로가 제외되어야 한다. 문제의 포인트 주어진 입력을 어떻게 그래프로 표현할 것인가? 최단 경로를 어떻게 찾고 어떻게 제외시킬 것인가? 그래프의 표현 입력은 다른 일반적인 그래프 문제와 같이 간선의 정보로 주어진다. 각 간선은 단방향이고 길이라는 가중치를 가지고 있..