패스트캠퍼스 챌린지 37일차

[강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다.

 

3월 1일 오늘의 강의

 

오늘 강의를 끝으로 유형별 문제풀이까지 강의를 끝마쳤다! 실전 코딩 테스트 문제 풀이와 기술 면접 가이드만 남았는데 이것도 한달정도면 끝마칠 것 같다. 강의가 끝나도 코딩테스트는 계속 준비할 예정이다.

 

알고리즘을 공부할 때마다 느끼는 것은 반복의 중요성이다. 코딩 테스트를 통해 알고리즘을 어떻게 효과적으로 사용할 것인지 고민할 수 있어 알고리즘을 공부한다면 코딩 테스트를 통해 계속해서 접목시켜보는 것을 추천한다.

 

백준 9663번 문제 : N - Queen

 

 

문제 해석

1. N-Queen 문제는 대표적인 백 트래킹 문제이다.

2. N X N 크기의 체스 보드 위에 퀸이 서로를 공격할 수 없게 배치한다.

3. DFS를 이용해서 백 트래킹 알고리즘을 구현하여 문제를 풀이한다.

 

 

 

복기

1. row 리스트를 생성해준 뒤, 각 열(인덱스)에 값을 입력해주어 check 함수를 통해 참일 경우 다음 행으로, 거짓일 경우 재귀 함수 종료를 통해 반복해주었다.

2. 백트래킹 문제에서는 계속해서 조건을 만족시켜야하기 때문에 해당 조건을 구현해서 참, 거짓을 판단하는 것이 중요하다.

3. 간단하게 재귀 함수를 구현한 문제이다.

 

백준 1987번 문제 : 알파벳

 

 

문제 해석

1. 말은 상, 하, 좌, 우 네 방향으로 이동할 수 있다.

2. 지나온 알파벳과는 다른 알파벳으로만 이동해야한다.

2. 백트래킹을 이용하여 모든 경우의 수를 고려한다. 이때 시간 제한이 2초이기 때문에 BFS 방식으로 접근한다.

 

DFS(좌), BFS(우)

 

복기

1. DFS는 시간초과가 발생했지만 BFS에서는 문제를 풀이할 수 있었다. 재귀 함수를 호출하는 과정에서도 시간 복잡도에 영향을 끼치지만 효율적으로 코드를 작성하면 시간 내에 풀이할 수 있을 것이다.

2. BFS는 set 자료형을 통해 중복 처리를 해주었다. 그리고 각 단계별로 현재의 좌표에 대한 경로값까지 지정해주었고 경로값을 최댓값과 비교하여 갱신해주므로써 문제에서 요구하는 답을 출력할 수 있었다.

 

 

https://bit.ly/37BpXiC

 

 

패스트캠퍼스 [직장인 실무교육]

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.