[99클럽 코테 스터디] 📝 Day17. 그리디 알고리즘

99클럽 코테 스터디 17일차 TIL + 그리디 알고리즘

📍 오늘의 학습 키워드

• 그리디 알고리즘
• 정렬 알고리즘
• 자료구조
• 탐욕적인 선택 속성과 최적 부분 구조
• 문제 해석 능력

📝 공부한 내용 본인의 언어로 정리하기

오늘은 그리디 알고리즘과 관련된 문제를 중심으로 공부했습니다. 그리디 알고리즘은 각 단계에서 최적의 선택을 하는 알고리즘으로, 지역적으로는 최적이지만 전체적으로는 최적해를 보장하지 않을 수 있습니다. 이를 이해하고 문제를 해결하기 위해서는 탐욕적인 선택 속성과 최적 부분 구조를 파악해야 합니다.

또한, 정렬 알고리즘과 자료구조 역시 그리디 알고리즘을 적용하는 데 중요한 역할을 합니다. 문제를 해결하기 위해서는 주어진 데이터를 적절하게 정렬하고, 필요한 정보를 효율적으로 관리할 수 있는 자료구조를 선택하고 활용해야 합니다.

마지막으로, 문제 해석 능력은 문제를 이해하고 적절한 해결 방법을 찾는 데 있어서 핵심적인 역할을 합니다. 문제의 요구사항을 정확하게 파악하고, 필요한 정보를 추출하는 능력이 중요합니다

📖 오늘의 회고

📚 어떤 문제가 있었고, 나는 어떤 시도를 했는지

오늘은 차량의 이동 경로 문제를 해결하면서 그리디 알고리즘의 중요성과 효율성을 다시 한 번 깨닫게 되었습니다. 처음에는 차량의 진입 지점과 진출 지점을 어떻게 다룰지 고민했지만, 진출 지점을 기준으로 정렬하는 것이 핵심임을 이해하고 문제를 해결할 수 있었습니다.

처음에는 모든 차량이 최소한 한 번 카메라를 만나는 최적의 위치를 찾는 것이 어려웠습니다. 다양한 접근법을 생각해 보았지만, 그리디 알고리즘을 사용해야 한다는 점을 깨닫기 전까지는 해결 방안을 찾는 데 어려움이 있었습니다.

그리디 알고리즘은 각 단계에서 최적의 선택을 하는 방식으로 문제를 해결하기 때문에, 탐욕적인 선택이 어떻게 전체적으로 최적해를 찾아가는지에 대해 이해하는 데 시간을 투자했습니다.

🤔 어떻게 해결했는지

🔖 참고링크 (단속카메라 게시글)

차량의 경로를 진출 지점 기준으로 정렬하고, 순차적으로 차량의 경로를 확인하면서 현재 설치된 카메라의 위치가 다음 차량의 진입 지점을 커버하지 못하면 새로운 카메라를 설치하는 방식으로 문제를 해결했습니다. 이를 통해 최소한의 카메라로 모든 차량을 커버할 수 있었습니다.

또한 문제를 해결하기 위해서는 주어진 조건을 파악하고, 그에 맞게 그리디한 방식으로 접근하는 것이 중요했습니다. 각 단계에서 최적의 선택을 하여 전체 해답을 찾아가는 과정을 반복하는 것이 핵심이었습니다. 문제를 해결하는 과정에서는 여러 예시를 통해 그리디 알고리즘이 어떻게 적용되는지를 이해하는 데 집중했습니다.

🤓 무엇을 새롭게 알았는지

오늘은 그리디 알고리즘을 적용하여 문제를 해결하는 방법에 대해 새롭게 이해할 수 있었습니다. 그리디 알고리즘은 각 단계에서의 최적 선택이 전체적으로 최적해를 보장하는 것이 아니기 때문에, 문제를 해결하는 과정에서 어떤 선택이 최적인지를 잘 따져봐야 한다는 것을 배웠습니다.

⏳ 내일 학습할 것은 무엇인지

내일은 동적 계획법(Dynamic Programming)에 대해 공부할 예정입니다. 동적 계획법은 최적 부분 구조를 가진 문제를 해결하는데 사용되는 중요한 알고리즘 중 하나이며, 효율적인 해결 방법을 제공합니다.

1. 다른 유형의 그리디 알고리즘 문제: 다양한 예제를 통해 그리디 알고리즘의 응용력을 키우기.
2. 동적 프로그래밍: 그리디 알고리즘과 비교하여 어떤 문제에 동적 프로그래밍이 적합한지 학습.
3. Java의 고급 자료구조: Java에서 제공하는 고급 자료구조를 학습하고, 이를 활용한 문제 해결 능력 기르기.

Java의 고급 자료구조

Java의 고급 자료구조에는 여러 가지가 있지만, 대표적으로는 다음과 같은 것들이 있습니다:

1. 트리(Tree): 이진 트리, 이진 검색 트리, AVL 트리, 레드-블랙 트리 등 다양한 형태의 트리 구조가 있습니다.
2. 그래프(Graph): 방향 그래프, 무방향 그래프, 가중 그래프 등 그래프 구조를 다루는 데 사용됩니다.
3. 해시맵(HashMap): 키-값 쌍을 저장하고 검색하는 데 사용되는 자료구조입니다.
4. 우선순위 큐(Priority Queue): 우선순위에 따라 요소를 처리하는 데 사용됩니다.
5. 세그먼트 트리(Segment Tree): 구간에 대한 쿼리를 빠르게 처리하는 데 사용됩니다.

동적 프로그래밍

동적 프로그래밍(Dynamic Programming)은 작은 부분 문제들의 해를 조합하여 전체 문제의 해를 구하는 알고리즘 설계 기법입니다. 주로 최적화 문제나 최장 경로, 최단 경로 등을 해결하는 데 사용됩니다. 주요 특징은 작은 부분 문제들이 중복되는 경우가 많고, 메모이제이션(Memoization) 또는 바텀업(bottom-up) 방식으로 구현됩니다.

스킬 향상을 위한 공부 방법

1. 실습과 문제 해결: 고급 자료구조나 동적 프로그래밍을 공부할 때는 실습과 문제 풀이가 중요합니다. 온라인 저지(Online Judge) 사이트에서 다양한 알고리즘 문제를 풀어보면서 실력을 키울 수 있습니다.
2. 프로젝트 참여: 실제 프로젝트에 참여하면서 고급 자료구조와 동적 프로그래밍을 적용해 볼 수 있습니다. 실무에서 발생하는 문제를 해결하면서 실력을 향상시킬 수 있습니다.
3. 책과 온라인 강의 학습: 고급 자료구조와 동적 프로그래밍에 대한 전문서적이나 온라인 강의를 통해 이론적인 부분을 학습할 수 있습니다. 이론을 잘 이해한 후 실습을 통해 응용력을 키울 수 있습니다.
4. 코드 리뷰와 피드백: 다른 개발자들의 코드를 분석하고 리뷰를 받아보면서 자신의 코드를 개선할 수 있는 방법을 배울 수 있습니다. 코드 리뷰는 실력 향상에 매우 효과적입니다.

정리하자면, 고급 자료구조와 동적 프로그래밍을 공부하는 가장 효과적인 방법은 실습과 문제 풀이, 프로젝트 참여, 책과 온라인 강의 학습, 그리고 코드 리뷰와 피드백을 통한 학습입니다. 이러한 방법을 조합하여 자신의 실력을 향상시킬 수 있습니다.