알고리즘, 코딩테스트/알고리즘 문제풀이
-
[백준 BOJ/C++] 4803 트리알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 10. 10. 00:54
4803번: 트리 기본적인 사이클 탐지 알고리즘 문제다. 그래프(Graph) 내에서 사이클(Cycle) 이 존재하는지를 찾는 문제는 흔한 그래프 탐색 문제 유형 중 하나다. 이 문제에서는 트리(Tree) 의 정의를 이용해서 주어진 그래프 내에서 사이클이 존재하는지 확인하고 사이클을 이루는 노드들에 연결되지 않은 트리의 수를 찾아야 한다. 트리는 그래프의 한 종류로 그래프가 트리가 되기 위해서는 몇가지 조건이 있지만 이 문제에서는 사이클만 신경써주면 된다. 문제에서 입력 자체가 두 노드 사이에 간선은 하나만 주어지고 간선에 가중치가 있는것도 아니기 때문에 사이클의 존재 여부로만 트리인지 아닌지 판단할 수 있다. 단, 주의해야하는 점은 예제로 주어진 입력과 같이 주어지는 간선정보에 포함되지 않은, 다른 노드..
-
[백준 BOJ/C++] 2668 숫자 고르기알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 10. 3. 00:55
2668번: 숫자 고르기 문제를 처음 접하면 아이디어가 잘 떠오르지 않는 어려운 문제이기도 하지만 막상 제대로 파악하고 나면 의외로 간단히 풀 수 있는 문제다. 그래프(Graph)와 관련된 문제이고 사이클(Cycle)을 찾는 문제임을 발견하기만 한다면 그 이후부터는 크게 까다로울 것은 없다. 문제는 정체를 알 수 없는 표가 주어지고 여기에서 집합을 찾는다는 표현으로 접근 방법을 어렵게하고 있다. 이 문제의 핵심은 바로 이 표가 그래프로 나타내어질 수 있음을 발견하는 것 그리고 찾고자 하는 집합의 조건이 그래프에서 사이클을 형성하는 노드들임을 발견하는 것이다. 대놓고 그래프 문제임을 보여주거나 연결과 탐색, 경로와 같이 큰 고민 없이 그래프로 연상할 수 있는 키워드를 사용하는 문제들도 많지만 이렇게 특이한..
-
[백준 BOJ/C++] 1240 노드사이의 거리알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 30. 02:07
1240번: 노드사이의 거리 간선정보를 입력받아 그래프의 최단거리를 구하는 문제다. 아주 기본에 가까운 문제라 최단거리 알고리즘의 기본기를 연습하기 좋은 문제라고 할 수 있다. 시작점과 끝점 여러개를 입력받아 거리를 구해야한다는 점과 문제 설명이 자세하지 않다는 점 정도가 고민해봐야할 부분이다. 문제 설명이 아주 간단한데 말 그대로 주어진 그래프에서 특정 두 노드의 거리를 구해주면 된다. 두 노드 사이의 간선에 방향성이 있는지, 여러개의 간선이 같은 두 노드 사이에 존재할 수 있는지 등 일반적인 그래프 탐색 문제에서 주어지는 설명은 한마디로 압축하고있다. 트리는 두 노드 사이에 간선이 하나만 존재하며 간선에 방향이 존재하지 않는다. 또한 트리는 사이클이 없는 그래프일 뿐이므로 BFS나 DFS와 같은 그래..
-
[백준 BOJ/C++] 10026 적록색약알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 25. 00:39
10026번: 적록색약 BFS, DFS 등을 이용해 2차원 맵을 탐색하는 그래프 탐색 문제다. 기본적이고 전형적인 유형에 아주 약간의 아이디어로 살짝 난이도를 올려놓아서 아주 까다롭지 않게 그래프 탐색 기본기를 익히기 좋은 문제라고 할 수 있다. RGB로 표현한 2차원 맵을 탐색하는 문제다. 보통 주어진 2차원 맵을 탐색하는 문제에서 요구하는 목표는 길을 찾거나 맵 상 구분되는 영역의 크기를 구하거나 영역의 수를 세는 형태로 자주 등장한다. 여기에 추가적으로는 맵을 변화시키는 등의 요소를 더하는 것이 대부분이다. 이 문제도 색상 지도와 적록색약을 가져와 결국 맵에 변화 요소를 주고 변화 전, 후의 영역의 수를 구하도록 하는 문제다. R과, G, B를 모두 구분하도록 그래프를 탐색시켜 적록색약이 아닌 사람..
-
[백준 BOJ/C++] 11497 통나무 건너뛰기알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 17. 23:16
11497번: 통나무 건너뛰기 정렬을 이용해서 그리디(Greedy)한 방법으로 풀 수 있는 전형적인 유형의 문제다. 그리디 알고리즘을 이용해야하는 문제들이 아이디어를 떠올리기만 하면 풀이가 간단해지는데 이 문제 역시 마찬가지다. 하지만 실버1 난이도의 문제인 만큼 핵심 아이디어를 찾기 까다롭지는 않은 편이다. 그림과 같이 통나무들을 원형으로 배치해 하나씩 건너 뛸 수 있게 한다는 컨셉이다. 문제에서 요구하는 것은 통나무들의 순서를 조정해서 바로 인접한 통나무의 높이 차이가 최소가 되어 뛰어다니기 쉽게 만드는 것이다. 각 통나무들의 높이가 주어졌을 때 인접한 통나무들의 높이차이 중 가장 큰 차이를 최소로 만들어 그 값을 출력하면 된다. 단 통나무들은 일직선으로 펼쳐진 것이 아니라 원형으로 양 끝이 연결된 ..
-
[백준 BOJ/C++] 3273 두 수의 합알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 10. 00:50
3273번: 두 수의 합 기본 개념이나 알고리즘을 연습하기 좋은 실버난이도의 문제다. 투 포인터 (Two Pointer) 알고리즘을 이용하면 간단히 풀 수 있다. 서로 다른 양의 정수들로 이루어진 배열에서 두 수를 골라 더해서 특정 값을 만들 수 있는 숫자 쌍을 찾는 문제다. 특별히 꼬아놓거나 이해가 어렵게 설명한 문제는 아니라서 비슷한 유형의 문제를 접해봤었다면 접근이 어렵지 않다. 크게 두가지 과정을 거치면 되는데 바로 정렬과 투 포인터 알고리즘 (Two Pointer Algorithm)이다. 문제의 포인트 Two Pointer Algorithm 투 포인터 알고리즘을 모르고 있더라도 문제를 보면 아이디어를 찾기 어려운 편은 아니다. 먼저 배열의 탐색을 쉽게 할 수 있도록 정렬이 필요함을 생각해 볼 수..
-
[백준 BOJ/C++] 2170 선긋기알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 6. 00:46
2170번: 선긋기 문제도 상당히 단순하고 쉬워보이지만 의외로 골드등급의 문제고 정답비율도 30% 대로 높지 않은편이다. 구현양도 얼마 안되지만 이러한 스타일의 문제를 많이 접해보지 않았다면 아이디어를 찾는데 어려움을 겪을 수도 있는 문제다. 문제는 정말 심플하다. 여러 선의 시작점과 끝점을 받아서 선들의 전체 길이를 구하면 된다. 하지만 이 선들은 일직선 상에 겹칠 수 있게 그려지며 따라서 겹쳐진 구간과 선이 그어지지 않은 구간을 제외한 실제전체 길이를 구해야 한다. 주어지는 값들의 범위도 꽤 크다. 점의 위치는 -1,000,000,000 ~ 1,000,000,000 사이이며 선의 수는 최대 1,000,000 으로 효율적으로 해결할 방법을 찾아야 한다. 문제의 포인트 아이디어 찾기 문제가 단순한 만큼 ..
-
[백준 BOJ/C++] 5214 환승알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 2. 02:00
5214번: 환승 단순한 최단거리 탐색 문제로 보이지만 의외로 정답비율이 낮은편이고 헷갈릴 수 있는 부분이 있는 문제다. 하이퍼튜브라는 컨셉을 문제에서 의도한대로 머릿속에 그리는데 어려움이 있었다. 문제 설명은 아주 짧고 간단하다. K개의 역이 주어지고 이 중 1번역에서 N번역까지 도달하는 최단경로를 찾아주면 된다. 간선에는 가중치도 없기 때문에 그냥 보기에는 상당히 간단해 보였다. 하지만 금방 하이퍼튜브라는 컨셉을 정확히 이해하지 못했음을 깨달았다. 주어지는 경로상 존재하는 역들을 모두 각각 연결하고 하이퍼튜브로 연결된 경로에 대한 비용은 1로 계산 하는 형태로 이해하고 풀었었는데 메모리 제한에 걸리는 상황이 발생했다. 문제의 설명도 너무 짧아 더욱 이해하기 어려웠다. 문제의 포인트 하이퍼튜브 컨셉 이..