전체 글
-
[백준 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로 계산 하는 형태로 이해하고 풀었었는데 메모리 제한에 걸리는 상황이 발생했다. 문제의 설명도 너무 짧아 더욱 이해하기 어려웠다. 문제의 포인트 하이퍼튜브 컨셉 이..
-
[백준 BOJ/C++] 1707 이분 그래프알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 28. 01:04
1707번: 이분 그래프 이분 그래프 (Bipartite Graph) 의 개념을 알고있거나 문제에서 빠르게 이해했다면 그리 어렵지 않은 탐색 문제다. 하지만 문제의 설명이 짧고 친절하지도 않은 편이라 혼란스러울 수 있는 부분들이 있었다. 노골적으로 그래프 문제임을 보여주고있지만 자세한 설명이나 예시 없이 이분 그래프인지 아닌지를 판별하도록 하고있다. 이분 그래프라는 개념을 어느정도 알고 있었다면 그나마 접근이 용이하겠지만 그렇지 않은 경우 예시도 없는 한줄 설명 만으로 빠르고 정확히 이해하기에는 쉽지 않은 편이었다. 문제 자체에서 여러번 탐색이 필요하다거나 특정 알고리즘을 사용한다거나 구현 양이 많아지는 문제는 아니지만 생소할 수 있는 문제라 한번쯤 풀어보면 좋을 문제다. 문제의 포인트 이분 그래프의 개..
-
[백준 BOJ/C++] 9466 텀 프로젝트알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 23. 23:20
9466번: 텀 프로젝트 그래프에서 사이클을 찾고 사이클을 이루지 않는 노드들의 갯수를 세는 문제다. 제한시간에 걸리지 않기 위해서는 탐색했던 노드를 다시 방문하지 않도록 해야 한다. 학생들이 노드로 주어지며 다른 학생을 지목하는 간선을 통해서 그래프(Graph)가 만들어진다. 그래프에서 사이클(Cycle) 은 특정 노드에서 탐색해가다가 다시 해당 노드로 돌아오게되는 형태의 연결을 말한다. 팀은 자기 자신을 지목한 학생이나 사이클을 이루는 학생들로 만들어지며 팀을 이루지 못한 학생들의 수를 카운트 하면 된다. 문제는 간단해 보이지만 일반적인 그래프 탐색 알고리즘 보다 고민하고 체크해야할 것이 추가되어 난이도가 꽤 있는 편이다. 중복을 피하기 위해 방문했던 노드를 체크해야 하는데 추가적으로 싸이클에 포함되..
-
[백준 BOJ/C++] 1431 시리얼 번호알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 21. 22:51
1431번: 시리얼 번호 문자열 내에서 각 문자의 정렬이 아니라 문자열들을 정렬하는 문제다. 별도의 정렬 기준이 주어지기 때문에 문자열들 간의 비교와 정렬을 연습하기 좋은 문제다. 일반적인 정수나 문자들 사이에서의 정렬 문제는 간단하지만 문자열들의 순서를 바꾸는 문제는 직접 경험하지 않은 상태로 만나게 된다면 헷갈릴 수 있는 부분이 있어 풀어보는 것이 좋다. 사용하는 언어의 문자열 혹은 정렬 알고리즘 라이브러리에 어느정도 익숙해야 문자열 기준의 정렬을 어렵지 않게 할 수 있다. 사용 언어에 따라 난이도 차이가 발생할 수 있으며 특히 C언어를 사용한다면 문자열 포인터와 관련해서 신경써야할 부분이 꽤 있으므로 차라리 vector를 제공하는 C++을 이용해서 쉽게 접근하는 것이 이득일 수 있다. 문제의 포인트..
-
[백준 BOJ/C++] 18870 좌표 압축알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 19. 22:14
18870번: 좌표 압축 정렬을 통해 풀어내는 문제고 실버 II 난이도라서 쉽게 생각했지만 의외로 까다로운 문제다. 조건이 타이트하진 않지만 문제 설명이 자세하지 않고 생각을 좀 해야 풀이 방법에 다가갈 수 있다. 특히 사용하는 언어에 따라 난이도 차이가 심해질 수 있는 문제다. 우선 문제 설명이 짧은 편이라 단번에 파악하기 어려울 수 있는데 간단히 표현해 입력 받은 각 좌표들 보다 작은 좌표의 갯수를 출력하면 된다. 여기에서 한가지 조건을 추가해 압축이라는 형태를 만들었는데 바로 중복된 좌표는 1개로 간주해야 한다는 것이다. 이정도만 파악하면 문제가 간단해 보이지만 의외로 풀어가다보면 고민해야 하는 지점이 몇가지 있었다. 다른 언어에서는 훨씬 간단할 수 있지만 적어도 C나 C++에서는 쉽게 풀어내기에 ..
-
[백준 BOJ/C++] 1759 암호 만들기알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 18. 00:52
1759번: 암호 만들기 아주 어렵지 않고 재밌게 풀 수 있는 순열/조합 문제다. Input으로 주어지는 알파벳 소문자를 중복 없이 조합하되 간단한 룰을 만족하는 조합을 찾아내면 된다. 1. 알파벳 사전 순서로 정렬 2. 1개 이상의 모음(a, e, i, o, u)과 2개 이상의 자음을 포함 위 규칙을 만족하면서 각 요소의 중복이 없는 조합을 만들어 모두 출력해야 한다. 이런 순열, 조합의 문제는 DFS로 구현하거나 간단히 각 언어마다 제공되는 API가 있다면 이를 이용해 어렵지 않게 풀어낼 수 있다. 문제의 포인트 순열 혹은 조합 구하기 순서가 의미를 가지고 중복을 허용하지 않는다는 점에서 순열이라고 할 수 있겠지만 사실 순서는 정해져 있는 것이기 때문에 일반적인 순열 문제와 같이 접근하지는 않았다. ..