[항해99 취업 리부트 코스 학습일지] 4주차 알고리즘 학습 Day 2

Q. 오늘 진행된 강의에서 학습한 내용은 무엇인가요?

백트래킹

백트래킹이란 무엇인가요?

백트래킹은 문제를 해결하기 위해 후보 해를 하나씩 만들어 나가다가, 해당 후보 해가 문제의 조건을 만족하지 않으면 즉시 포기하고 다음 후보 해를 시도하는 알고리즘입니다. 즉, 가능한 모든 해를 탐색하되 불필요한 탐색은 줄여서 효율적으로 문제를 해결하는 방법이에요.

백트래킹의 특징

• 재귀적 탐색: 백트래킹은 재귀적으로 모든 가능한 해를 탐색해요. 각 단계에서 후보 해를 확장하거나 포기하는 결정을 내려요.
• 가지치기: 가능성이 없는 경로를 빨리 포기(가지치기)하여 탐색 공간을 줄입니다. 이를 통해 시간 복잡도를 줄이고 효율성을 높여요.
• 상태 공간 트리: 해결 과정이 트리 형태로 표현되며, 트리의 각 노드는 해결의 각 단계를 나타냅니다. 각 단계에서 가능한 모든 선택지를 시도해 보고, 유망하지 않은 선택지는 가지치기를 통해 제거해요.

백트래킹을 활용할 수 있는 문제

• N-Queens 문제: 체스판 위에 N개의 퀸을 서로 공격할 수 없게 배치하는 문제.
• 미로 찾기: 미로의 시작점에서 끝점까지의 경로를 찾는 문제.
• 수도쿠: 주어진 퍼즐을 규칙에 맞게 채우는 문제.
• 조합 최적화 문제: 특정 조건을 만족하는 조합을 찾는 문제.

순열

순열이란 무엇인가요?

순열(permutation)은 서로 다른 n개의 원소 중에서 r개를 뽑아 순서를 고려하여 배열하는 경우의 수를 의미해요. 순서를 중요시하기 때문에 같은 원소라도 배열 순서가 다르면 다른 경우로 간주됩니다.

순열의 특징

• 순서 중요: 특정 원소의 배치를 다양하게 시도해 볼 때 유용합니다. 예를 들어, 암호 해독, 일정을 짜는 문제, 경로를 찾는 문제 등에서 사용돼요.
• 모든 가능한 순서를 고려: 모든 경우의 수를 고려하여 해를 찾습니다. 따라서 경우의 수가 매우 많을 수 있어요.

순열을 활용할 수 있는 문제

• 암호 해독: 가능한 모든 조합을 시도하여 암호를 해독하는 문제.
• 일정 짜기: 여러 작업을 특정 순서로 배치하는 문제.
• 여행 경로 찾기: 여러 도시를 방문하는 경로를 찾는 문제.

조합

조합이란 무엇인가요?

조합(combination)은 서로 다른 n개의 원소 중에서 r개를 뽑는 경우의 수를 의미해요. 이때 순서는 고려하지 않습니다. 예를 들어, 친구 3명 중에서 2명을 뽑아 팀을 만드는 경우, 누가 먼저 뽑혔는지는 중요하지 않고, 어떤 친구들이 팀에 포함되었는지만 중요해요.

조합의 특징

• 순서를 고려하지 않는 선택: 특정 원소들을 선택할 때, 그 순서는 상관없고 선택된 원소들의 조합만 중요해요.
• 경우의 수가 적음: 순서를 고려하지 않기 때문에 경우의 수가 순열보다 적습니다.

조합을 활용할 수 있는 문제

• 로또 번호 선택: 여러 숫자 중에서 특정 개수를 뽑는 문제.
• 팀 구성: 여러 사람 중에서 특정 인원을 선택하여 팀을 구성하는 문제.
• 부분 집합 구하기: 주어진 집합의 모든 부분 집합을 찾는 문제.

 

Q. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

백트래킹 문제인 백준 5568번이 가장 대표적인 문제로 이러한 문제를 하루에 1개씩 풀어보면서 감을 잡아야겠다.

 

 

 

 

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

https://hanghae99.spartacodingclub.kr/reboot

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지