정렬
-
[백준 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++] 1431 시리얼 번호알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 21. 22:51
1431번: 시리얼 번호 문자열 내에서 각 문자의 정렬이 아니라 문자열들을 정렬하는 문제다. 별도의 정렬 기준이 주어지기 때문에 문자열들 간의 비교와 정렬을 연습하기 좋은 문제다. 일반적인 정수나 문자들 사이에서의 정렬 문제는 간단하지만 문자열들의 순서를 바꾸는 문제는 직접 경험하지 않은 상태로 만나게 된다면 헷갈릴 수 있는 부분이 있어 풀어보는 것이 좋다. 사용하는 언어의 문자열 혹은 정렬 알고리즘 라이브러리에 어느정도 익숙해야 문자열 기준의 정렬을 어렵지 않게 할 수 있다. 사용 언어에 따라 난이도 차이가 발생할 수 있으며 특히 C언어를 사용한다면 문자열 포인터와 관련해서 신경써야할 부분이 꽤 있으므로 차라리 vector를 제공하는 C++을 이용해서 쉽게 접근하는 것이 이득일 수 있다. 문제의 포인트..
-
[백준 BOJ/C++] 18870 좌표 압축알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 19. 22:14
18870번: 좌표 압축 정렬을 통해 풀어내는 문제고 실버 II 난이도라서 쉽게 생각했지만 의외로 까다로운 문제다. 조건이 타이트하진 않지만 문제 설명이 자세하지 않고 생각을 좀 해야 풀이 방법에 다가갈 수 있다. 특히 사용하는 언어에 따라 난이도 차이가 심해질 수 있는 문제다. 우선 문제 설명이 짧은 편이라 단번에 파악하기 어려울 수 있는데 간단히 표현해 입력 받은 각 좌표들 보다 작은 좌표의 갯수를 출력하면 된다. 여기에서 한가지 조건을 추가해 압축이라는 형태를 만들었는데 바로 중복된 좌표는 1개로 간주해야 한다는 것이다. 이정도만 파악하면 문제가 간단해 보이지만 의외로 풀어가다보면 고민해야 하는 지점이 몇가지 있었다. 다른 언어에서는 훨씬 간단할 수 있지만 적어도 C나 C++에서는 쉽게 풀어내기에 ..