구현(implementation)

구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

구현 유형의 문제: 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기는 어려운 문제

구현유형 예시

• 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제 (언어별로 다를 수 있음)
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 
• 문자열을 특정한 기준에 따라서 끊어 처리해야하는 문제 (문자열은 파이썬이 처리가 쉬운편)
• 적절한 라이브러리를 찾아서 사용해야 하는 문제 (ex 모든 순열, 모든 조합 찾기 등)

 

일반적으로 알고리즘 문제에서 2차원 공간은 행렬(Matrix)의 의미로 사용됨

시뮬레이션 및 완전 탐색 문제는 2차원 공간에서의 방향 벡터가 자주 활용된다.

 

시뮬레이션

BFS나 재귀와 같이 특정 자료구조 혹은 알고리즘에 종속되지 않고 주어진 문제 상황을 구현하는데 구현이 어려운 문제들을 시뮬레이션 유형의 문제라고 함.

 

완전탐색

가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다.

 

2가치 규칙이 적용되어야 한다.

1. 사용된 알고리즘이 적절한가? ( 문제를 해결할 수 있는가 )
2. 효율적으로 동작하는가? -> 시간 복잡도 고려

 

완전탐색 기법 활용법

① Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법
② 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
③ 재귀 호출
④ 비트마스크 - 2진수 표현 기법을 활용하는 방법
⑤ BFS, DFS를 활용하는 방법

 

 

 

 

출처

- 이코테 책 & 강의

- 완전탐색 https://hongjw1938.tistory.com/78

- 시뮬레이션 https://blog.encrypted.gg/948