인프런 커뮤니티 질문&답변

잉여인간님 좋은 질문 감사합니다!! 실전에서 빠르게 알고리즘을 선택하는 능력은 문제를 많이 풀면서 생기는 감각이지만, 강의 자료에서 강조하는 체계적인 접근법을 바탕으로 실전 팁을 드릴게요.

1. 입력값과 제약조건이 가장 강력한 힌트예요

"문제의 특성과 입력값, 출력값들을 보면서 힌트를 찾는" 게 핵심이에요. 제약조건을 보면 어떤 알고리즘을 써야 하는지 답이 나오는 경우들이 종종 있습니다

입력 크기가 N ≤ 100이면 O(N³)도 괜찮아요. 완전탐색이나 브루트포스로 접근해도 충분합니다. N ≤ 1,000이면 O(N²) 정도까지는 안전해요. 버블정렬이나 선택정렬처럼 이중 반복문을 쓸 수 있죠.

그런데 N ≤ 100,000이면 이야기가 달라져요. O(N log N) 이하로 풀어야 하니까 정렬이나 이분탐색을 떠올려야 해요. N ≤ 1,000,000이면 O(N) 또는 O(N log N)이 필수예요. 해시나 투 포인터 같은 선형 알고리즘을 생각해야 합니다

시간 제한도 중요한데, 보통 1초에 1억 번 연산 정도를 기준으로 생각하면 돼요. 이게 바로 강의에서 배운 시간복잡도를 실전에 적용하는 방법이에요.

2. 문제를 구조화하는 훈련이 정말 중요해요

4단계 접근법을 머릿속에서 빠르게 돌려보는 연습을 하는 걸 추천드립니다!

먼저 자료구조를 정해요. "이 데이터는 순서가 중요한가? 중복이 있나? 빠른 검색이 필요한가?" 이런 질문을 던지면서요. 순서가 중요하고 인덱스 접근이 필요하면 배열, 빠른 검색이 필요하면 해시, 최댓값/최솟값을 계속 뽑아야 하면 힙을 떠올리는 식입니다

그다음엔 패턴을 파악해요. 강의에서 말한 것처럼 "예시를 3개 정도 손으로 써보면서" 규칙성을 찾아보는 거예요. 이 과정이 정말 중요한데, 실전에서는 문제를 읽자마자 예제 입출력을 따라가면서 "아, 이런 식으로 변하는구나"를 캐치해야 해요.

3. 문제 유형별 시그널 포착하기

특정 단어나 문장이 나오면 거의 자동으로 알고리즘이 연결돼야 해요. "어떤 류의 조건들에는 어떤 식의 해결법이 쓰이더라"는 경험치입니다.

"최단 거리", "최소 비용"이라는 단어가 나오면 BFS나 DP를 떠올려야 해요. "모든 경우의 수"나 "가능한 모든 방법"이 나오면 완전탐색이나 DFS/백트래킹이죠. "연속된 부분"이나 "구간"이 나오면 투 포인터나 슬라이딩 윈도우를 생각해야 해요.

"정렬된 배열에서"라는 말이 나오면 거의 무조건 이분탐색이에요. "빈도수", "등장 횟수"가 나오면 해시를 먼저 고려하고요. "최적의 선택"이나 "탐욕적으로"라는 표현이 보이면 그리디 알고리즘을 떠올려야 합니다

4. 문제 분석의 실전 루틴

실전에서는 이렇게 접근해보세요. 문제를 읽으면서 동시에 이 사고 과정을 거치는 거예요.

먼저 1분 안에 입력 크기와 시간 제한을 확인하고 대략적인 시간복잡도 범위를 잡아요. 그다음 문제에서 요구하는 게 뭔지 한 문장으로 정리해요. "N개 원소 중 조건을 만족하는 최댓값 찾기" 이런 식으로요.

그리고 예제 입출력을 직접 따라가면서 패턴을 찾아보세요. 이때 강의에서 말한 것처럼 "잘 모르겠으면 예시를 3개 정도 손으로 써보면서" 하는 게 진짜 효과적이에요. 이 과정에서 "아, 이거 정렬하면 되겠네" 또는 "아, 이거 그래프 탐색이구나" 같은 깨달음이 와요.

마지막으로 비슷한 문제를 풀어본 적이 있는지 떠올려보세요. 강의 자료에서 강조했듯이 "절대적인 노출량"이 여기서 빛을 발하거든요. 같은 유형을 5-10문제 정도 풀어봤다면, 비슷한 냄새가 나는 순간 "어? 이거 저번에 풀었던 그 방식으로 하면 되겠네"가 바로 떠올라요.

제일 중요한 건 조급해하지 않는 거예요. 강의에서도 말했듯이 "최소 10-20분은 문제를 자세하게 이해하고" 접근해야 해요. 처음 5분은 문제 이해와 입력 분석에, 다음 5분은 접근 방법 고민에, 그다음에 구현을 시작하는 식으로요.

그리고 한 가지 접근이 막히면 다른 관점에서 봐요. "이걸 거꾸로 생각하면?" "예외 케이스부터 처리하면?" 이런 식으로 시각을 바꾸면 해결책이 보일 때가 많아요.

이렇게 고민하시는 거 보면 분명 좋은 결과 있으실 겁니다 같이 빠이팅해보시져!!

안녕하세요, 인프런 AI 인턴입니다. 잉여인간님.

코딩 테스트에서 어떤 알고리즘을 적용할지 빠르게 결정하는 것은 경험과 연습의 결과입니다. 하지만 몇 가지 팁이 도움이 될 수 있습니다:

1. 문제 유형 파악

• 키워드 탐색: 문제 설명에서 특정 알고리즘에 대한 힌트를 주는 키워드를 찾는 것이 중요합니다. 예를 들어, “최소 경로”가 언급된다면 다익스트라 알고리즘이 필요할 수 있습니다.
  

2. 문제 요구사항 분석

• 문제의 정확한 요구 파악: 주어진 입력과 원하는 출력을 명확히 이해하는 것이 중요합니다. 이는 어떤 자료 구조와 알고리즘이 필요한지를 결정할 수 있게 합니다.
  

3. 알고리즘 범주화

• 알고리즘과 자료 구조를 범주화: 문제를 다룰 수 있는 기본적인 알고리즘(정렬, 탐색, 그래프, 동적 프로그래밍 등)을 머릿속에 정리해 두십시오. 문제를 보면서 자동으로 관련 범주가 떠오르게 됩니다.
  

4. 단순한 문제부터 시작

• 간단한 것부터 해결: 문제를 가장 간단한 버전으로 상상해 보고, 이를 해결할 수 있는 방법을 찾으세요. 그런 다음 점차 복잡성을 늘려가며 해결책을 수정해 나갑니다.
  

5. 연습과 경험 축적

• 많이 풀어보기: 다양한 유형의 문제를 많이 접하며 경험을 쌓으면 패턴을 알아차리기 쉬워지고, 이는 빠른 결정에 큰 도움이 됩니다.
  

참고 링크

• 질문 제목: 코딩 테스트에서 알고리즘 선택 및 적용 방법
  

위의 기준들을 바탕으로 꾸준히 연습하시면, 더욱 원활하게 알고리즘을 선택하고 적용할 수 있을 것입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.