Diiiiiikey

Blog

Algorithm 구현의 기초

문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현

프로그래밍 언어의 문법을 정확히 알고, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것이 목표

구현 능력을 보는 대표적인 사례

  • 완전 탐색(brute force) - 가능한 모든 경우의 수를 전부 확인
  • 시뮬레이션(simulation) - 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션을 하는 것과 동일한 모습

완전 탐색

단순하고 무식하지만 답이 무조건 있다는 강력함

하지만 문제 해결에는 기본적으로 문제 해결 가능해야 하고, 효율적이여야 함

문제 해결에는 강력

단, 시간 복잡도가 O(N)보다 낮아야 함 - 이라는 문구가 붙으면 완전 탐색으로는 안됨. 따라서 완전 탐색 밖에 없다고 판단될 때 적용

  • Brute Force(조건/반복을 사용하여 해결)
  • 재귀
  • 순열
  • DFS/BFS
  • etc..

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.'"

가

{ "[1, 2, 'null']": 'OLLEH MI g' }

로

댓글남기기

참고