amiro

amiro

I hope my writing will be helpful to someone.

처음의 제가 그러했듯이
제가 정리한 글들이
누군가에게 조금이나마
도움이 되기를 바라며

알고리즘 01 - 알고리즘 문제를 스스로 사고해서 풀기 위해서는 어떻게 해야될까?

3 분 소요

알고리즘 문제를 스스로 사고해서 푸는 방법

알고리즘 문제를 푸는 능력을 키우기 위해서는 많은 문제를 접하는 것도 좋을 것 같습니다. 그리고 새로운 문제를 접하여도 스스로 해결해 나가는 능력도 중요하다고 생각합니다. 저는 새로운 문제를 접하여도 문제를 이해하고, 적합한 해결 방법을 사고해낼 수 있도록 능력을 키우고 싶어서 어떻게 하면 좋은 방향일까 고민해보았습니다.

이 글에서는 알고리즘 문제를 스스로 사고하여 푸는 방법을 단계별로 정리하고, 이를 효과적으로 꾸준히 연습하기 위해 고찰해보았습니다.

1. 문제를 분석하는 사고의 시작

1.1 문제를 제대로 이해하기

  1. 문제 읽기
    • 주어진 문제를 읽고, 입력과 출력의 조건을 명확히 파악합니다.
    • 예제를 직접 손으로 계산하며 문제의 의도를 이해하는 것도 좋은 방법이 될 것 같습니다.
  2. 핵심 질문 던지기
    • “내가 무엇을 구하려고 하는가?”
    • “어떤 제약 조건이 있는가?”
    • “입력 데이터의 크기는 얼마나 되는가?”

예제 “1부터 n까지 숫자 중 k개의 조합을 구하세요.”

  • 구할 것: 조합
  • 제약 조건: k개의 숫자만 선택
  • 입력 크기: n의 값에 따라 시간 복잡도 고려 필요.

1.2 작은 입력으로 문제를 나눠보기

간단한 입력값으로 직접 손으로 풀어보며 문제의 패턴을 찾습니다. 이를 통해 문제를 해결하는 구조적 흐름을 떠올릴 수 있습니다.

예제

  • 입력: n = 4, k = 2
  • 직접 계산: [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]
  • 패턴 발견: 현재 숫자를 선택하고, 이후 숫자들로 조합 생성.

2. 해결 전략을 떠올리기

2.1 문제 유형 분석

알고리즘 문제는 자주 등장하는 패턴과 유형이 있습니다. 문제를 분석하며 적합한 해결 전략은 무엇이 있을까요?

주요 유형별 해결 전략

  1. 최적화 문제 동적 프로그래밍(DP)
    • “최소/최대 값을 구해야 할 때, 문제를 작은 단위로 나눠 해결.”
  2. 모든 경우 탐색 문제 백트래킹
    • “모든 가능한 선택을 탐색하며 조건에 맞지 않는 경로를 제거.”
  3. 탐색 문제 그래프 탐색 (BFS/DFS)
    • “그래프의 연결된 노드를 탐색하며 조건을 만족하는 노드를 찾음.”
  4. 데이터 정리 문제 정렬, 이분 탐색
    • “데이터를 정렬하거나, 중간값을 효율적으로 탐색.”

예제

  • 조합 생성 문제 → 백트래킹 사용.
  • 배열의 특정 합 문제 → 투 포인터 또는 백트래킹.

2.2 문제를 작은 단위로 쪼개기

큰 문제를 해결하려 하지 말고, 문제를 더 작은 단위로 나누어 하나씩 해결하는 방법이 있습니다. 아래와 같은 방법이 있겠죠.

  1. 현재 단계에서 할 수 있는 작업 찾기
    • “숫자를 선택할지 말지 결정한다.”
  2. 다음 단계로 문제를 넘기기
    • “숫자를 선택한 후, 남은 숫자들로 다시 재귀적으로 조합을 만든다.”

예제

문제: [1, 2, 3]에서 2개의 조합 구하기.

  1. 첫 번째 숫자 선택: [1] → 남은 숫자 [2, 3]으로 조합.
  2. 첫 번째 숫자 제외: 빈 경로 → 남은 숫자 [2, 3]으로 조합.

3. 코드로 구현하기

문제를 이해하고 해결 전략을 떠올렸다면, 이를 코드로 직접 구현해보는 것 입니다. 처음에는 의사 코드(pseudo-code)를 작성하면 좋습니다.

의사 코드 예제: 조합 생성

  1. 결과 리스트를 생성한다.
  2. 현재 숫자를 선택하거나 선택하지 않는 방식으로 탐색한다.
  3. 경로의 길이가 (k)에 도달하면 결과에 추가한다.

3.1 디버깅과 검증

  1. 작은 입력값 테스트
    • 간단한 입력값으로 코드가 예상대로 작동하는지 확인.
  2. 엣지 케이스 테스트
    • 예: 입력이 비어있거나, ( n < k )인 경우.

4. 스스로 사고를 훈련하는 방법

4.1 패턴 익히기

문제를 해결하면서 알고리즘의 주요 패턴을 익히는 것도 중요하다고 봅니다. 다음은 자주 쓰이는 패턴입니다.

  1. 동적 프로그래밍(DP)
    • 작은 문제를 해결해 큰 문제를 푸는 방식.
    • 예: 피보나치 수열, 배낭 문제.
  2. 백트래킹
    • 조건을 만족하는 모든 경로 탐색.
    • 예: N-Queens, 부분 집합 생성.
  3. 그래프 탐색
    • BFS: 최단 거리 탐색.
    • DFS: 모든 경로 탐색.

4.2 손으로 풀어보기

  • 문제를 보고 바로 코드를 작성하지 말고 간단한 입력값으로 직접 종이에 손으로 적어보는 것도 좋습니다.
  • 이 과정을 통해 규칙과 알고리즘을 떠올릴 수 있습니다.

4.3 복습과 피드백

  • 해결한 문제를 다시 풀어보며 다른 접근 방법을 시도하기
  • 실패한 문제는 풀이를 복습하고, 왜 실패했는지 분석하기

5. 쉽게 암기하는 팁

  1. 핵심 질문 기억하기
    • “문제를 작은 단위로 나눌 수 있는가?”
    • “현재 단계에서 선택할 수 있는 방법은 무엇인가?”
    • “조건을 만족하지 않으면 가지치기를 할 수 있는가?”
  2. 간단한 키워드로 암기하기
    • 동적 프로그래밍: “작게 쪼개고 저장하고 조합!”
    • 백트래킹: “탐색하고 잘못된 경로는 포기!”
    • 그래프 탐색: “넓게(BFS), 깊게(DFS) 탐색!”

6. 결론

알고리즘 문제를 스스로 사고해서 풀기 위해선 문제를 분석하고 해결 전략을 설계하는 훈련이 필요하다고 봅니다. 자주 등장하는 알고리즘 패턴을 익히고, 작은 문제부터 차근차근 해결하며 사고력을 확장해보세요. 마음 잡고 알고리즘 공부를 시도했지만, 꾸준히 하기 어려운 것 같습니다. 그럼에도 꾸준히 연습하다 보면 자연스럽게 더 어려운 문제도 해결할 수 있는 능력을 갖추게 될 수 있지 않을까요? 화이팅!

댓글남기기

참고