코딩테스트/AL

2024.08.05 - [코딩테스트/AL] - [이것이 코딩테스트다] 그래프 탐색 알고리즘 : DFS & BFS [이것이 코딩테스트다] 그래프 탐색 알고리즘 : DFS & BFS대표적인 그래프 탐색 알고리즘에는 DFS와 BFS가 있습니다. 여기서 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말하며, DFS와 BFS는 코딩 테스트에서 매우 자주 등장하는 유yeonnys.tistory.com 저번 글에 이어 이번에는 DFS와 BFS 알고리즘을 활용한 예제 문제를 설명해보겠습니다! 문제) 음료수 얼려 먹기문제Q. N × M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로..

대표적인 그래프 탐색 알고리즘에는 DFS와 BFS가 있습니다. 여기서 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말하며, DFS와 BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 하는 부분입니다. 특히, 국내 대기업 공채에서는 DFS와 BFS를 적절히 활용해야 하는 문제를 많이 출제하고 있습니다.  DFS와 BFS를 보기에 앞서 반드시 알아야하는 자료구조에 대해 알아보겠습니다. 스택 자료구조먼저, 스택은 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 입니다. 즉, 입구와 출구가 동일한 형태로 가장 대표적인 예시로는 박스 쌓기 예시를 들 수 있죠. 여러 개의 박스를 쌓아야 할 때, 가장 아래부터 박스를 쌓아올립니다. 그 후, 박스를 제거할 때는 가..

이번에는 시뮬레이션과 완전 탐색에 중점을 둔 구현 문제에 대해 알아보겠습니다.  구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정  (사실상 모든 문제가 구현 문제라고 생각할 수 있습니다;^^)그러나 일반적으로 구현 유형의 문제는 문제에서 요구하는 내용이 구현에 초점이 맞춰있거나, 구현이 어려운 문제를 의미합니다. 즉, 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭합니다. 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제적절한 라이브러리를 찾아서 사용해야 하는 문제이러한 구현 문제의 경우, 다양한 라이브러리를 익히는 등 많은 연습이 필요한 문제입니다. 행렬은 파..

그리디 알고리즘이란? 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.  그리디 알고리즘은 한국어로 탐욕법이라고 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구하는데요, 그리디 알고리즘의 해법은 그 정당성 분석이 중요합니다. 즉, 단순히 가장 좋아 보이는 것을 반복적으로 선택하는 것만으로도 최적의 해를 구할 수 있는지를 검토하는 것이 필요합니다.   아래와 같은 예시 문제가 있습니다. 루트 노드(5)부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶을 때, 최적의 해는 무엇인가요? 직관적으로 확인할 수 있듯이, 5 -> 7 -> 9로 이동하면 노트..