구현

leekoby·2023년 4월 5일

알고리즘

[자료구조/알고리즘] 이론

목록 보기

11/17

🔧변경내용🔨

제목 날짜 내용
발행일 23.04.05

제목	날짜	내용
발행일	23.04.05

📌들어가기에 앞서

해당 포스트는 알고리즘 구현을 학습한 것을 정리한 내용입니다.

🌈 Algorithm 구현의 기초

알고리즘 문제를 푼다는 것은, 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것과 같다.

각 유형은 원하는 의도가 분명하게 있고, 그것을 해결하는 것이 목표다.

데이터를 정렬할 수 있는가?
데이터를 효율적으로 탐색할 수 있는가?
데이터를 조합할 수 있는가? ...etc

이렇게 카테고리를 분류한다고 해도 내가 생각한 로직을 '코드로 구현'한다는 건 전부 공통적인 속성이다.

이러한 문제 해결을 코드로 풀어낼 때, 정확하고 빠를수록 구현 능력이 좋다고 말한다.

구현 능력이 좋은 개발자를 선발할 의도로 구현 능력을 직접 평가하기도 한다.

'정해진 시간 안에 빠르게 문제를 해결하는 능력'을 보기 위함이다.

머리로 이해하고 있어도 코드로 작성하지 않는다면(혹은 시간 부족으로 못 한다면) 정답이 될 수 없기 때문이다.

본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것을 구현 문제, 구현 유형이라고 통칭할 수 있다.

보통 이러한 문제들은 구현하는 것 자체를 굉장히 까다롭게 만든다.

지문을 매우 길게 작성하거나, 까다로운 조건이나 상황을 붙인다거나, 로직은 쉽지만 구현하려는 코드가 굉장히 길어지게 되는 문제들이 대다수다.

그렇기 때문에 깊은 집중력과 끈기가 필요하다.

구현 능력을 보는 대표적인 사례에는 완전 탐색(brute force)과 시뮬레이션(simulation)이 있다.

완전 탐색이란 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식이다.
시뮬레이션은 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션을 하는 것과 동일한 모습을 그리는 것이다.

💻 완전 탐색

모든 문제는 완전 탐색으로 풀 수는 있다.

이 방법은 굉장히 단순하고 무식하지만 "답이 무조건 있다"는 강력함이 있다.

예를 들어, 양의 정수 1부터 100까지의 임의의 요소가 오름차순으로 하나씩 담긴 배열 중, 원하는 값 N을 찾기 위해서는 배열의 첫 요소부터 마지막 요소까지 전부 확인한다면 최대 100번의 탐색 끝에 원하는 값을 찾을 수 있다.

그렇지만, 문제 해결할 땐 기본적으로 두 가지 규칙이 있다.

첫 번째, 문제를 해결할 수 있는가?
두 번째, 효율적으로 동작하는가?

완전 탐색은 첫 번째 규칙을 만족시킬 수 있는 강력한 무기이지만, 두 번째 규칙은 만족할 수 없는 경우가 있다.

양의 정수 1부터 100까지의 임의의 요소가 오름차순으로 하나씩 담긴 배열 중, 원하는 값 N을 찾으시오.
단, 시간 복잡도가 O(N)보다 낮아야 합니다.

이러한 문제가 나왔을 때, 최악의 경우 100번을 시도해야 하는 완전 탐색은 두 번째 규칙을 만족할 수 없다.

배열을 작은 수에서 큰 수, 혹은 그 반대로 정렬한 후 이분 탐색을 사용하는 방법 등 다른 알고리즘을 사용해야 한다.

그렇기 때문에, 완전 탐색은 문제를 풀 수 있는 가능한 모든 방법을 고려한 후 효율적으로 동작하는 알고리즘이 완전 탐색밖에 없다고 판단될 때 적용할 수 있다.

완전 탐색은 단순히 모든 경우의 수를 탐색하는 모든 경우를 통칭한다.

완전히 탐색하는 방법에는 Brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등 여러 가지가 있다.

그 중, Brute Force(무차별 대입)에 대해 예시를 들어보자.

Brute Force 예시

우리 집에는 세 명의 아이들이 있습니다.
아이들의 식성은 까다로워, 먹기 싫은 음식과 좋아하는 음식을 철저하게 구분합니다.
먹기 싫은 음식이 식탁에 올라왔을 땐 음식 냄새가 난다며 그 주변의 음식까지 전부 먹지 않고,
좋아하는 음식이 올라왔을 땐 해당 음식을 먹어야 합니다.

세 아이의 식성은 이렇습니다.

첫째: (싫어하는 음식 - 미역국, 카레) (좋아하는 음식 - 소고기, 된장국, 사과)

둘째: (싫어하는 음식 - 참치, 카레) (좋아하는 음식 - 미역국, 된장국, 바나나)

셋째: (싫어하는 음식 - 소고기) (좋아하는 음식 - 돼지고기, 된장국, 참치)

100개의 반찬이 일렬로 랜덤하게 담긴 상이 차려지고, 한 명씩 전부 먹을 수 있다고 할 때, 가장 많이 먹게 되는 아이와 가장 적게 먹게 되는 아이는 누구일까요? (단, 그 주변의 음식은 반찬의 앞, 뒤로 한정합니다.)

이 문제는 단순히 100개의 반찬을 첫째, 둘째, 셋째의 식성에 맞게 하나씩 대입하여 풀 수 있다.

for(let i = 0; i < 100; i++) {
  if(첫째 식성) {
    if(싫어하는 음식이 앞뒤로 있는가) {
      그냥 넘어가자;
    }
    좋아하는 음식 카운트;
  }
  if(둘째 식성) {
    if(싫어하는 음식이 앞뒤로 있는가) {
      그냥 넘어가자;
    }
    좋아하는 음식 카운트;
  }
  if(셋째 식성) {
    if(싫어하는 음식이 앞뒤로 있는가) {
      그냥 넘어가자;
    }
    좋아하는 음식 카운트;
  }
}

return 많이 먹은 아이;

각각 몇 가지 음식을 얼마나 먹을 수 있는지 각각 계산한 후, 제일 많이 먹는 아이와 제일 적게 먹는 아이를 파악할 수 있다.

문제를 풀 때, 반복문이 아닌 배열을 전부 순회하는 메서드를 사용한다거나 간결한 코드를 위한 문법을 사용한다고 하더라도 배열을 전부 탐색하여 세 명의 값을 도출한다는 것엔 변함이 없다.

💻 시뮬레이션

시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형이다.

보통 문제에서 설명해 준 로직 그대로 코드로 작성하면 되어서 문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있다.

시뮬레이션 예시

시뮬레이션에 관련된 예시를 하나 살펴보자.

무엇을 위한 조직인지는 모르겠지만, 비밀스러운 비밀 조직 '시크릿 에이전시'는 소통의 흔적을 남기지 않기 위해 3일에 한 번씩 사라지는 메신저 앱을 사용했습니다. 그러나 내부 스파이의 대화 유출로 인해 대화할 때 조건을 여러 개 붙이기로 했습니다. 해당 조건은 이렇습니다.

캐릭터는 아이디, 닉네임, 소속이 영문으로 담긴 배열로 구분합니다.

소속은 'true', 'false', 'null' 중 하나입니다.

소속이 셋 중 하나가 아니라면 아이디, 닉네임, 소속, 대화 내용의 문자열을 전부 X로 바꿉니다.

아이디와 닉네임은, 길이를 2진수로 바꾼 뒤, 바뀐 숫자를 더합니다.

캐릭터와 대화 내용을 구분할 땐 공백:공백으로 구분합니다: ['Blue', 'Green', 'null'] : hello.

띄어쓰기 포함, 대화 내용이 10글자가 넘을 때, 내용에 .,-+ 이 있다면 삭제합니다.

띄어쓰기 포함, 대화 내용이 10글자가 넘지 않을 때, 내용에 .,-+@#$%^&*?! 이 있다면 삭제합니다.

띄어쓰기를 기준으로 문자열을 반전합니다: 'abc' -> 'cba'

띄어쓰기를 기준으로 소문자와 대문자를 반전합니다: 'Abc' -> 'aBC'

시크릿 에이전시의 바뀌기 전 대화를 받아, 해당 조건들을 전부 수렴하여 수정한 대화를 객체에 키와 값으로 담아 반환하세요. 같은 캐릭터가 두 번 말했다면, 공백을 한 칸 둔 채로 대화 내용에 추가되어야 합니다. 대화는 문자열로 제공되며, 하이픈- 으로 구분됩니다.

문자열은 전부 싱글 쿼터로 제공되며, 전체를 감싸는 문자열은 더블 쿼터로 제공됩니다.

예: "['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'"

문제는 대화 내용이 담긴 문자열을 입력받아, 문자열을 파싱하여 재구성하려고 한다.

예시를 이용하여 순차적으로 작성해 보자.

1. "['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'"
입력값으로 받은 문자열을 각 캐릭터와 대화에 맞게 문자열로 파싱하고, 파싱한 문자열을 상대로 캐릭터와 대화를 구분한다.

첫 번째 파싱은 - 을 기준으로 ['Blue', 'Green', 'null'] : 'hello. im G.', ['Black', 'red', 'true']: '? what? who are you?' 두 부분으로 나눈다.
두 번째 파싱은 : 을 기준으로 \['Blue', 'Green', 'null'\] 배열과 'hello. im G.' 문자열로 나눈다.

배열과 문자열을 사용해, 조건에 맞게 변형한다.
- 소속이 셋 중 하나인지 판별합니다.
- ['Blue', 'Green', 'null'] 아이디와 닉네임의 길이를 2진수로 바꾼 뒤, 숫자를 더한다:
  - [1, 2, 'null']
- 'hello. im G.' 10 글자가 넘기 때문에, .,-+@#$%^&* 를 삭제한다:
  - 'hello im G'
- 'hello im G' 띄어쓰기를 기준으로 문자열을 반전한다:
  - 'olleh mi G'
- 'olleh mi G' 소문자와 대문자를 반전한다:
  - 'OLLEH MI g'
변형한 배열과 문자열을 키와 값으로 받아 객체에 넣는다.
- { "[1, 2, 'null']": 'OLLEH MI g' }