[S4]Chapter11. [자료구조/알고리즘] 코딩 테스트 준비

박현석·2022년 12월 17일
1

코드스테이츠

목록 보기
39/40
post-thumbnail

Algorithm

  • 문제를 해결하는 최선의 선택이다.
  • 어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제의 풀이 방법, 해(解)를 의미한다.
  • 알고리즘은 프로그래밍에서는 input 값을 통해 output 값을 얻기 위한 계산 과정을 의미한다.
    주어진 문제를 해결할 때, 정확하고 효율적으로 결과 값을 얻는 것이 필요하고 그때 바로 이 알고리즘이 사용된다.

일상생활 알고리즘 예시

문제

횡단보도 옆에 신호등이 있습니다. 현재는 빨간불이지만 5분 뒤에는 초록불로 바뀔 것입니다.
5분이 지나고, 초록불로 바뀐 신호등은 10초 뒤 ‘30’이라는 숫자와 함께 1초에 한 번씩 점등하기 시작합니다.
총 30번을 점등한 신호등은 이어 빨간불로 바뀝니다.

입력(Input)

  • 알고리즘은 출력에 필요한 자료를 입력받을 수 있어야한다.
    이 상황에서는 제일 먼저 빨간불인 신호등이 초록불이 되려면 5분이라는 시간을 입력 받아야한다.
    하나 더 알아야 할 것은 신호등은 항상 시간을 입력받아야 알고리즘이 동작하지만 꼭 입력을 받지 않아도 되는 알고리즘도 있다.(예를 들어 원주율(pi)의 1조 번째 자리 수를 구하려는 경우 입력은 없지만 출력은 있다.)

출력(Output)

  • 알고리즘은 실행이 되면 적어도 한 가지 이상의 결과를 반드시 출력해야한다.
    만약 알고리즘에 출력이 없다면 이 알고리즘은 끝이 났는지, 끝이 나지 않았는지 확인할 길이 없기 때문이다.
    출력은 알고리즘에서 “끝이 났다" 라는 표현이므로 반드시 존재해야 하며, 이는 유한성과도 연관이 있다.
    이 상황에서 출력은 “초록불로 바뀐다" 이다.

유한성(Finiteness)

  • 알고리즘은 유한한 명령어를 수행한 후, 유한한 시간 내에 종료해야한다.
    이는 알고리즘은 실행된 후에는 반드시 종료되어야 한다는 말과도 같다.
    알고리즘이 무한히 실행이 된다면 무한히 기다려야 할 것이며, 그것은 출력의 기약이 없는 알고리즘일 것이다.
    신호등이 빨간불인 상태에서 초록불로 변하는 과정에 대한 기약이 없다면 그 신호등은 제대로 된 알고리즘으로 동작하는 것이 아닐 것이다.

명확성(Definiteness)

  • 알고리즘의 각 단계는 단순하고 명확해야 하며, 모호해서는 안된다.
    예를 들어 "신호등이 몇 분 뒤에 켜집니다" 와 같이 표현한다면, 명확성이 떨어질 뿐더러 모호한 표현이라고 볼 수 있다. "신호등이 5분 뒤에 켜집니다" 와 같이 명확하게 표현을 해야만 한다.

효율성(Efficiency)

  • 알고리즘은 가능한 한 효율적이어야 한다. 모든 과정은 명백하게 실행 가능해야 하며, 실행 가능성이 떨어지는 알고리즘은 효율적이지 못한 알고리즘이라 볼수 있다.
    알고리즘은 시간 복잡도와 공간 복잡도를 통해 결정이 되므로, 시간 복잡도와 공간 복잡도가 낮을수록 효율적인 알고리즘이라고 볼 수 있다.

알고리즘의 중요성

  • 좋은 알고리즘은 절차가 명확하게 표현되어 있고, 효율적이므로 다양한 문제 해결 과정에서 나타나는 불필요한 작업들을 줄여줄 수 있다.
    그렇지만 알고리즘의 순서가 달라지면 결과 또한 다르게 나타날 수 있다는 것은 주의해야할 점.

알고리즘은 어떻게 해야 잘 풀 수 있을까요?

문제를 이해한다.

  • 대부분의 코딩 테스트에서는 문제의 설명과 입출력예시, 제한사항, 그리고 주의사항 등으로 문제상황을 제시한다. 주어진 조건을 토대로 문제가 무엇인지를 이해하는 것부터 시작해야한다.

문제를 어떻게 해결할 수 있을지, 전략을 세워야 한다.

  • 연습장에 전체적인 그림을 그려가면서 페어와 나눠본다. 전체적인 흐름을 공유할 수 있다.
  • 수도코드를 작성하기 전, 인간의 사고로 문제를 해결할 수 있어야 한다. 연습장이나 온라인 화이트보드를 사용하여 문제에 대해 논의하고, 해결한다.
  • 코드를 작성하기 전에 페어와 수도코드를 먼저 작성해준다. 알고리즘 전략은 잘 짜여진 수도코드에서부터 시작한다.
  • 막혔던 생각이 페어에게 설명을 하면서 해결되는 경우도 있다.

문제를 코드로 옮겨 본다.

  • 페와 논의한 저략을 코드로 옮겨 본다.
  • 구현한 코드를 페어와 논의해 보고, 구현한 코드의 최적화를 시도해 본다.

시간 복잡도와 공간 복잡도

시간 복잡도

Big-O 표기법

  • 시간 복잡도를 표기하는 방법은 세가지가 있다.
    Big-O(빅-오), Big-Ω(빅-오메가), Big-θ(빅-세타)
  • 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다.
    이 중에서 Big-O 표기법이 가장 자주 사용된다.
    빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.

O(1)

  • Big-O 표기법은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기하는 방법이다.
    O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.
    다시 말해 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.

예시

function O_1_algorithm(arr, index) {
	return arr[index];
}
let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

O(n)

  • 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

예시

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}
function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

O(log n)

  • Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가졌다.
    BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)

O(n2)

  • 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

예시

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		// do something for 1 second
		}
	}
}
function another_O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			for (let k = 0; k < n; k++) {
			// do something for 1 second
			}
		}
	}
}

O(2n)

  • Big-O 표기법 중 가장 느린 시간 복잡도를 가졌다.

예시

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

데이터 크기에 따른 시간 복잡도

데이터 크기 제한예상되는시간 복잡도
n ≤ 1,000,000O(n) or O (logn)
n ≤ 10,000O(n2)
n ≤ 500O(n3)
### 공간 복잡도 - 알고리즘이 수행되는 데에 필요한 메모리의 총량을 의미한다. 즉 프로그램이 필요로 하는 메모리 공간을 산출하는 것을 의미 #### 공간 복잡도 예시 ```javascript function factorial(n) { if(n === 1) { return n; } return n*factorial(n-1); } ``` - 함수 factorial은 재귀함수로 구현되었습니다. 변수 n에 따라 변수 n이 n개가 만들어지게 되며, factorial 함수를 재귀함수로 1까지 호출할 경우 n부터 1까지 스택에 쌓이게 된다. 따라서 해당 함수의 공간 복잡도는 O(n)이라 볼 수 있다. #### 공간 복잡도는 얼마나 중요한가요? - 보통 때의 공간 복잡도는 시간 복잡도보다 중요성이 떨어진다. 시간 복잡도에 맞다면 공간 복잡도도 얼추 통과하기 때문이다. 공간 복잡도를 중요하게 보는 경우는 동적 계획법과 같은 알고리즘이나 하드웨어 환경이 매우 한정되어 있는 경우이다.

Algorithm의 유형

Greedy Algorithm

  • 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

Greedy Algorithm 문제 해결 단계

  1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다.
  2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.
  3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.

Greedy Algorithm 적용 예시

김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다.
  1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택합니다.
  2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사합니다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택합니다.
  3. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사합니다. 액수가 부족하면 1번 과정부터 다시 반복합니다.
  • 가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 줍니다.

탐욕 알고리즘의 특징

  • 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
  • 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.

Algorithm 구현

  • 가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것과 같고, 각 유형은 원하는 의도가 분명하게 있고, 그것을 해결하는 것이 목표이다.
  • 본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것을 구현 문제, 구현 유형이라고 통칭할 수 있다.

완전 탐색

  • 이 방법은 굉장히 단순하고 무식하지만 "답이 무조건 있다"는 강력함이 있다.
  • 완전 탐색은 단순히 모든 경우의 수를 탐색하는 모든 경우를 통칭한다.
    완전히 탐색하는 방법에는 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.' 문자열로 나눕니다.
  2. 배열과 문자열을 사용해, 조건에 맞게 변형합니다.
    • 소속이 셋 중 하나인지 판별합니다.
    • ['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'
  3. 변형한 배열과 문자열을 키와 값으로 받아 객체에 넣습니다.
    • { "[1, 2, 'null']": 'OLLEH MI g' }

Dynamic Programming

  • 탐욕 알고리즘과 같이 작은 문제에서 출발한다는 점은 같다.
    그러나, 탐욕 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, DP는 모든 경우의 수를 조합해 최적의 해법을 찾는다.
  • 주어진 문제를 여러 개의 (작은) 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결한다.
    하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다.
    다시 말해, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍이다.

두 가지 가정이 만족하는 조건에서 사용할 수 있다.

  1. Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
  2. Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

Overlapping Sub-problems

  • 큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다.

예시

unction fib(n) {
	if(n <= 2) {
		return 1;
	};
	return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...

fib(7) = fib(6) + fib(5)
fib(7) = (fib(5) + fib(4)) + fib(5) // fib(6) = fib(5) + fib(4)
fib(7) = ((fib(4) + fib(3)) + fib(4)) + (fib(4) + fib(3)) // fib(5) = fib(4) + fib(3)
...
  • 작은 문제의 결과를 큰 문제를 해결하기 위해 여러 번 반복하여 사용할 수 있을 때, 부분 문제의 반복(Overlapping Sub-problems)이라는 조건을 만족한다.

주의점

  • 주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라, 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 한다.

Optimal Substructure

  • 정답은 최적의 해결 방법(Optimal solution)을 의미한다.
    주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아야한다.
    그리고 작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있다.

예시

최단 경로를 찾는 문제
  1. A → D로 가는 최단 경로 : A → B → C → D
  2. A → C로 가는 최단 경로 : A → B → C (A → B → E → C 가 아닙니다.)
  3. A → B로 가는 최단 경로 : A → B

Algorithm의 유형 예제

Greedy Algorithm - 거스름돈

문제

타로는 자주 JOI 잡화접에서 물건을 산다. JOI 잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI 잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한 장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
JOI 잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다고 되어 있습니다. 즉 언제나 거스름돈을 적게 주는 알고리즘을 짜야만 합니다.

예제 1
입력 : 380 / 출력 : 4
예제 2
입력 : 1 / 출력 : 15

380엔을 타로가 지불을 해야 한다면 타로가 받아야 할 거스름돈은 620엔입니다. 그렇다면 500엔 1개, 100엔 1개, 10엔 2개로 총 4개의 동전을 거슬러 받는 것이 가장 적게 잔돈을 거슬러 받는 방법일 것입니다. 가장 적게 거슬러 받기 위한 로직을 작성해보도록 하겠습니다.
function keepTheChange(input) {
	//1000엔짜리 지폐를 냈다는 가정이 있고, 입력 값으로는 지불해야 할 금액이 들어옵니다.
	let change = Number(1000 - input);
	//카운트하기 위해 변수 count에 0을 할당합니다. 
	let count = 0;
	//입력 값에 배열이 들어오지 않으므로 직접 배열을 만들어줍니다.
	const joiCoins = [500, 100, 50, 10, 5, 1];
	//만든 배열의 개수만큼만 돌려줘야 합니다.
	for(let i = 0; i < joiCoins.length; i++){
		//거스름돈이 0원이 되면 for문을 멈춥니다.
		if(change === 0) break;
		//거스름돈과 잔돈을 나눈 몫을 카운팅합니다.(쓰인 잔돈의 개수 카운팅)
		count += Math.floor(Number(change/joiCoins[i]));
		//거스름돈을 잔돈으로 나눈 나머지를 재할당합니다.
		change %= joiCoins[i];
	}
	//count를 리턴합니다.
	return count;
}
함수 keepTheChange는 항상 1000엔짜리 지폐를 냈다는 가정이 있고, 입력 값으로는 지불해야 할 금액이 들어오기 때문에 변수 change에 1000 - input을 하여 잔돈을 먼저 계산을 해줍니다.
JOI 잡화점은 항상 잔돈이 충분히 있고 거스름돈 개수가 가장 적게 잔돈을 주어야만 하기 때문에, 가장 금액이 큰 잔돈부터 계산을 시작합니다. 그러기 위해서는 가장 금액이 큰 잔돈 순서대로 배열을 만들어 줄 필요성이 있으므로, joiCoins라는 배열을 만들어 큰 잔돈 순서대로 요소를 채워줍니다.
for문에서는 만든 배열의 요소 개수만큼만 반복문을 돌릴 것이고, if문에서는 잔돈이 0원이 되면 for문을 멈추도록 조건을 짠 뒤, 거스름돈이 큰 순서대로 나눠서 몫을 구하는 방식을 취합니다.
count 변수에는 change와 joiCoins[i]를 나눈 몫을 카운트하여 넣어주고, change에는 거스름돈으로 나누어 나온 나머지를 재할당 해줍니다.

Brute-Force Algorithm

  • 무차별 대입 방법을 나타내는 알고리즘이다.
  • 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도하여 문제를 해결하는 방법이다.
  • 공간복잡도와 시간복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법을 의미한다.
Brute Force Algorithm은 크게 두 가지 경우에 사용
  1. 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때
  2. 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

Brute Force Algorithm의 한계

  • 문제가 복잡해질수록 기하급수적으로 많은 자원을 필요로 하는 비효율적인 알고리즘이 될 수 있다.

Brute Force Algorithm을 어디서 사용하고 있을까?

  • 배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색한다.
function SequentialSearch2(arr, k) {
	// 검색 키 K를 사용하여 순차 검색을 구현
	// 입력: n개의 요소를 갖는 배열 A와 검색 키 K
  // 출력: K값과 같은 요소 인덱스 또는 요소가 없을 때 -1
	let n = arr.length;    // 현재의 배열 개수를 n에 할당합니다.
  arr[n] = k;            // 검색 키를 arr n인덱스에 할당합니다.
	let i = 0;             // while 반복문의 초기 값을 지정하고
	while (arr[i] !== k) { // 배열의 값이 k와 같지 않을 때까지 반복합니다.
		i = i + 1;           // k와 같지않을 때 i를 +1 합니다.
	}
	if (i < n) {     // i가 k를 할당하기전의 배열개수보다 적다면(배열안에 k값이 있다면)
		return i;      // i를 반환합니다.
	} else {
		return -1;     // -1을 반환합니다.
	}
}
문자열 매칭 알고리즘 (Brute-Force String Matching)

  • 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색한다.
function BruteForceStringMatch(arr, patternArr) {
  // Brute Force 문자열 매칭을 구현합니다.
  // 입력: n개의 문자 텍스트를 나타내는 배열 T, m개의 문자 패턴을 나타내는 배열P
  // 출력: 일치하는 문자열이 있으면 첫번째 인덱스를 반환합니다. 검색에 실패한 경우 -1을 반환합니다.
  let n = arr.length;
  let m = patternArr.length;
  for (let i = 0; i <= n - m; i++) {
  // 전체 요소개수에서 패턴개수를 뺀 만큼만 반복합니다. 그 수가 마지막 비교요소이기 때문입니다.
  // i 반복문은 패턴과 비교의 위치를 잡는 반복문입니다.
    let j = 0;
    // j는 전체와 패턴의 요소 하나하나를 비교하는 반복문입니다.
    while (j < m && patternArr[j] === arr[i + j]) {
      // j가 패턴의 개수보다 커지면 안되기때문에 개수만큼만 반복합니다.
      // 패턴에서는 j인덱스와 전체에서는 i + j 인덱스의 값이 같은지 판단합니다.
      // 같을때 j에 +1 합니다.
      j = j + 1;
    }
    if (j === m) {
			// j와 패턴 수가 같다는 것은 패턴의 문자열과 완전히 같은 부분이 존재한다는 의미입니다.
      // 이 때의 비교했던 위치를 반환합니다.
      return i;
    }
  }
  return -1;
}
선택 정렬 알고리즘 (Selection Sort)

  • 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환하는 정렬 알고리즘
function SelectionSort(arr) {
  // 주어진 배열을 Selection Sort로 오름차순 정렬합니다.
  // 입력: 정렬 가능한 요소의 배열 A
  // 출력: 오름차순으로 정렬된 배열
  for (let i = 0; i < arr.length - 1; i++) {
  // 배열의 0번째 인덱스부터 마지막인덱스까지 반복합니다.
  // 현재 값 위치에 가장 작은 값을 넣을 것입니다.
    let min = i;
    // 현재 인덱스를 최소값의 인덱스를 나타내는 변수에 할당합니다.
    for (let j = i + 1; j < arr.length; j++) {
    // 현재 i에 +1을 j로 반복문을 초기화하고 i 이후의 배열요소과 비교하는 반복문을 구성합니다.
      if (arr[j] < arr[min]) {
      // j인덱스의 배열 값이 현재 인덱스의 배열 값보다 작다면
        min = j;
        // j 인덱스를 최소를 나타내는 인덱스로 할당합니다.
      }
    }
    // 반복문이 끝났을 때(모든 비교가 끝났을때)
    // min에는 최소값의 인덱스가 들어있습니다.
    // i값과 최소값을 바꿔서 할당합니다.
    let temp = arr[i];
    arr[i] = arr[min];
    arr[min] = temp;
  }
	// 모든 반복문이 끝나면 정렬된 배열을 반환합니다.
  return arr;
}

그 밖의 Brute Force 활용 알고리즘

  • 버블 정렬 알고리즘 - Bubble Sort
  • Tree 자료 구조의 완전탐색 알고리즘 - Exhausive Search (BFS, DFS)
  • 동적 프로그래밍 - DP(Dynamic Programing)

Dynamic Programming - 피보나치 수열과 타일링

Recursion + Memoization

  • 다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해놓은 해결책을 이용한다.
    이때 결과를 저장하는 방법을 Memoization 이라고 한다.
다이내믹 프로그래밍을 적용한 피보나치 수열
function fibMemo(n, memo = []) {
		// 이미 해결한 하위 문제인지 찾아본다
    if(memo[n] !== undefined) {
			return memo[n];
		}
    if(n <= 2) {
			return 1;
		}
		// 없다면 재귀로 결괏값을 도출하여 res 에 할당
    let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
		// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
    memo[n] = res;
    return res;
}
  1. fibMemo 함수의 파라미터로 n 과 빈 배열memo 를 전달합니다.
    a. 이 빈 배열은 하위 문제의 결괏값을 저장하는 데에 사용합니다.
  2. memo 의 n번째 인덱스가 undefined 이 아니라면 : 다시 말해 n 번째 인덱스에 해당하는 피보나치 값이 저장되어 있다면, 저장되어 있는 값을 그대로 사용합니다.
  3. undefined라면 : 즉, 처음 계산하는 수라면 fibMemo(n-1, memo) + fibMemo(n-2, memo)를 이용하여 값을 계산하고, 그 결괏값을 res 라는 변수에 할당합니다.
  4. 마지막으로 res 를 리턴하기 전에 memo 의 n 번째 인덱스에 res 값을 저장합니다.
    a. 이렇게 하면 (n+1)번째의 값을 구하고 싶을 때, n번째 값을 memo 에서 확인해 사용할 수 있습니다.

Iteration + Tabulation

  • 반복문을 이용한 방법은, 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법입니다. 따라서 이 방식을 Bottom-up 방식이라 부르기도한다.
반복문과 다이내믹 프로그래밍으로 구현한 피보나치 수열
function fibTab(n) {
    if(n <= 2) {
			return 1;
		}
		// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
    let fibNum = [0, 1, 1];
    for(let i = 3; i <= n; i++) {
        fibNum[i] = fibNum[i-1] + fibNum[i-2];
		// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
		// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다
    }
    return fibNum[n];
}
  1. fibTab 함수의 파라미터는 n 하나뿐입니다. 만약, n 이 2와 같거나, 그 이하라면 1을 반환합니다.
    a. 피보나치 수열의 첫 번째와 두 번째는 1, 1이라는 것을 기억해야 합니다.
  2. fibNum이라는 변수에 n 이 1 & 2일 때의 값을 배열을 사용해 저장해 놓습니다.
    a. 피보나치 수열은 1부터 시작하지만 인덱스는 0부터 시작하기 때문에 0 번째 인덱스를 채워 줄 dummy data로 0을 삽입합니다.
  3. 2의 다음인 3부터 n까지 피보나치 수를 구하고, fibNum배열에 저장합니다.
  4. fibNum의 n 번째 인덱스 값 을 반환합니다.

2x1 타일링

문제
  • 2xn 크기의 타일이 주어진다면, 2x1과 1x2 크기의 타일로 채울 수 있는 경우의 수를 모두 구해야 합니다.
    a. n = 1일 땐 경우의 수는 1 : 세로 타일 1개
    b. n = 2일 땐 경우의 수는 2 : 세로 타일 2개 or 가로 타일 2개
    c. n = 3일 땐 경우의 수는 3 : 세로 타일 3개 or 왼쪽 세로 타일 1개 + 가로 타일 2개 or 가로 타일 2개 + 오른쪽 세로 타일 1개
  • 2개의 타일로 빈 공간을 어떻게 채우든 상관없이, 맨 마지막 타일은 세로 타일 1개이거나 가로 타일 2개인, 2 가지 경우밖에 없습니다. 맨 마지막 타일의 경우의 수를 제외했을 때 남는 공간의 마지막 타일도 세로 타일 1개, 혹은 가로 타일 2개인 2가지 경우밖에 없습니다. 이렇게, DP 문제는 문제 속의 규칙성을 찾는 것이 키 포인트입니다.
  • n = 4일 땐 경우의 수는 5 : 세로 타일 1개를 뺀 n = 3과, 가로 타일 2개를 뺀 n = 2일 때의 경우의 수를 더했습니다.
function tiling2x1(n) {
  let memo = [0, 1, 2];
  for (let i = 3; i <= n; i++) {
    memo[i] = memo[i - 1] + memo[i - 2];
  }
  return memo[n];
};

Algorithm with Math

순열과 조합

순열

  • 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것이며, 이는 조합과 마찬가지로 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다.
  • 여기 사과와 오렌지, 레몬 총 3개의 원소로 이루어진 집합이 있습니다. 만약에 이 3가지의 과일 중 2가지의 과일을 중복 없이, 이번에는 순서에 상관있게 부분집합을 만든다면 총 몇 개의 부분집합이 나올 수 있을까요?
  • 총 6개의 부분집합이 나올 수 있을 것입니다. 왜냐하면 순열은 조합과 달리 순서도 따져서 부분집합을 만들기 때문이다.
    즉 사과가 뒤로 가는 경우와 사과가 앞으로 가는 경우를 다르게 보고 각기 하나의 경우의 수로 치는 것.
순열의 식

  • 순열은 일반화 과정을 거쳐, Permutation의 약자 P로 표현합니다. 여기서도 n은 원소의 총 개수를 의미하고, r은 그중 뽑는 개수를 의미
  • 순열 또한 중복을 허용하지 않기 때문에 반드시 R <= N을 만족해야 한다는 것

조합

  • 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관없게 r개의 원소를 선택하는 것이며, 이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다.
  • 여기 또 다시 사과와 오렌지, 레몬 총 3개의 원소로 이루어진 집합이 있습니다. 만약에 이 3가지의 과일 중 2가지의 과일을 중복 없이, 순서에 상관없는 부분집합을 만든다면 총 몇 개의 부분집합이 나올 수 있을까요?
  • 총 3개의 부분집합이 나올 수 있을 것입니다. 왜냐하면 조합은 순서에 상관없이 원소를 선택해 부분집합을 만드는 것이기 때문이다.
    즉 사과가 뒤로 가든, 앞으로 가든 상관 없이 그저 사과 1개와 오렌지 1개가 있으면 하나의 경우의 수로 치는 것.
조합의 식

  • 조합은 일반화 과정을 거쳐, Combination의 약자 C로 표현합니다. 여기서 n은 원소의 총 개수를 의미하고, r은 그중 뽑는 개수를 의미
  • 조합은 중복을 허용하지 않기 때문에 반드시 R ≤ N을 만족해야 한다는 것

GCD와 LCM

GCD(최대공약수)

공약수(Common Divisor)

  • 공약수는 두 수 이상의 여러 수 중 공통된 약수를 의미
  • 6의 약수는 1, 2, 3, 6이고 9의 약수는 1, 3, 9
  • 공통된 약수는 1, 3으로 공약수라고 표현하고, 최대공약수는 3임을 알 수 있다.

LCM(최소공배수)

공배수(Common Multiple)

  • 공배수는 두 수 이상의 여러 수 중 공통된 배수를 의미
  • 12 와 18 의 최소 공배수는 36임을 알 수 있다.

GCD와 LCM을 구하는 방식

가장 작은 수들의 곱으로 나타내며 구하는 법

  • 12와 18을 가장 작은 수의 곱으로 나타냈을때 여기서 겹치는 부분인 2와 3을 곱한 수인 6이 최대공약수이고, 6을 중심으로 2와 3을 곱해 나오는 수인 36이 최소공배수가 된다.
유클리드 호제법
  • 유클리드 호제법은 최대공약수와 관련이 깊은 공식
  • 2개의 자연수 a와 b가 있을 때, a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 이론
    이러한 성질에 따라 b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나누는 과정을 반복해, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수임을 알 수 있게된다.
  • 2개의 자연수 a와 b가 있다. 단 a가 b보다 커야 한다는 조건(절대적 조건)이 있다.
    왜냐하면 나누었을 때 음수가 나오면 안 되기 때문.
  • q는 몫(Quotient)을 의미하고, r은 나머지(Rest)를 의미한다고 생각하면 된다.
  • 다시 b를 r로 나눕니다. 그러면 다시 몫인 q와 나머지인 r’가 나올 것이고, r을 다시 r’와 나누게 되면 언젠가 몫인 q와 나머지인 r이 0이 되는 상황이 도출이 된다.
  • 이 때 나누는 수인 r’가 바로 최대공약수라는 의미
![](https://user-images.githubusercontent.com/58800295/183022847-8cbb03ab-a9e0-4877-8c6c-c663d8275a92.png0

멱집합

  • 집합 {1, 2, 3}의 모든 부분집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 으로 나열할 수 있고, 이 부분집합의 총 개수는 8개이고, 이 모든 부분집합을 통틀어 멱집합이라고 한다.
  • 이렇게 어떤 집합이 있을 때, 이 집합의 모든 부분집합을 멱집합 이라고 한다.

  1. Step A: 1을 제외한 {2, 3}의 부분집합을 나열합니다.
    • Step B: 2를 제외한 {3}의 부분집합을 나열합니다.
      - Step C: 3을 제외한 {}의 부분집합을 나열합니다. → {}
      - Step C: {}의 모든 부분집합에 {3}을 추가한 집합들을 나열합니다. → {3}
    • Step B: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열합니다.
      - Step C: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열하려면, {}의 모든 부분집합에 {2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {2, 3}을 추가한 집합들을 나열합니다. → {2}, {2, 3}
  2. Step A: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열합니다.
    • Step B: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열하려면, {3}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {3}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열합니다.
      - Step C: {3}의 모든 부분집합에 {1}을 추가한 집합을 나열하려면, {}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {1, 3}을 추가한 집합들을 나열합니다. → {1}, {1, 3}
      - Step C: {3}의 모든 부분집합에 {1, 2}를 추가한 집합을 나열하려면, {}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {1, 2, 3}을 추가한 집합들을 나열합니다. → {1, 2}, {1, 2, 3}

  • 멱집합 문제는 트리 문제는 아니고, 그림은 이해를 돕기 위해 사용.

Algorithm with Math 예제

순열과 조합 - 순열과 조합을 이용한 문제들

문제: 카드 뽑기
[A, B, C, D, E]로 이뤄진 5장의 카드가 있습니다. 이 5장의 카드 중 3장을 선택하여 나열하려고 합니다. 이때, 다음의 조건을 각각 만족하는 경우를 찾아야 합니다.
  1. 순서를 생각하며 3장을 선택합니다.
  2. 순서를 생각하지 않고 3장을 선택합니다.

case 1. 순서를 생각하며 3장을 선택할 때의 모든 경우의 수


  • 모든 카드를 1장씩 나열하면서, 나열된 카드가 3장에 도달하면 카드의 나열을 중지합니다.
  • 해당 조건을 만족하려면, 다음과 같은 방법으로 경우의 수를 구합니다.
    1. 첫번째 나열하는 카드를 선택하는 방법에는 다섯 가지가 있습니다.
    2. 첫번째 카드를 나열하고 난 다음, 두번째 카드를 선택하는 방법에는 네 가지가 있습니다.
    3. 두번째 카드를 나열하고 난 다음, 세번째 카드를 선택하는 방법에는 세 가지가 있습니다.
  • 따라서 5 X 4 X 3 = 60 가지의 방법이 있습니다.
  • 이렇게 n 개 중에서 일부만을 선택하여 나열하는 것을 순열이라고 합니다. 순열은 순서를 지키며 나열해야 합니다.
  • 예를 들어 카드를 3장 뽑을 때, [A, B, D]와 [A, D, B] 두 경우 모두 A, B, 그리고 D라는 같은 카드를 3장 선택했지만, 나열하는 순서가 다르므로 서로 다른 경우로 파악해야 합니다.
    - 5장에서 3장을 선택하는 모든 순열의 수 = 5P3 = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60
    - 일반식 : nPr = n! / (n - r)!
    - 5! = 5 X (5 - 1) X (5 - 2) X (5 - 3) X (5 - 4) = 5 X 4 X 3 X 2 X 1 = 120
  • 그렇다면, 순열의 모든 경우의 수를 나열하고 싶다면 어떻게 해야 할까요?
    예) [A, B, C], [A, B, D], [A, B, E], [A, C, B] ... 등
// 반복문 코드
function permutationLoop() {
	// 순열 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
	// 문제 안에 포함되어 있을 경우 이런 식으로 직접 적어서 사용합니다.
  let lookup = ['A', 'B', 'C', 'D', 'E'];
  let result = [];
  for (let i = 0; i < lookup.length; i++) {
    for (let j = 0; j < lookup.length; j++) {
      for (let k = 0; k < lookup.length; k++) {
        if(i === j || j === k || k === i) continue;
        result.push([lookup[i], lookup[j], lookup[k]])
      }
    }
  }
  return result;
}
permutationLoop();
  • result 배열 안에 순열의 경우의 수를 삽입한 뒤, 반환하는 함수입니다.
반복문의 개수 === 요소를 뽑는 개수
  • 5개의 요소 중 3개를 뽑는 조건 : 하나의 반복문당 5 개의 요소(lookup.length)를 순회하고, 반복문을 3번 중첩하여 3개의 요소를 뽑습니다. 조금 더 풀어서 쓰자면 이러한 식이 됩니다:
// 반복문 1개당 1개의 요소를 뽑습니다.
  for (let i = 0; i < lookup.length; i++) {
		let pick1 = lookup[i];
    for (let j = 0; j < lookup.length; j++) {
			let pick2 = lookup[j];
      for (let k = 0; k < lookup.length; k++) {
				let pick3 = lookup[k];
				if(i === j || j === k || k === i) continue;
        result.push([pick1, pick2, pick3])
      }
    }
  }
중복된 요소는 제거
  • 같은 인덱스를 선택하는 것은, 중복된 요소를 선택한다는 것과 같습니다. 하지만 순열은 중복된 요소를 허용하지 않기 때문에, result에 넣기 전에, 동일한 인덱스인지 검사하고, 동일하다면 삽입하지 않고 다음으로 넘어갑니다.
  • AAA부터 EEE까지 전부 만드는 코드이지만, 마지막에 중복 요소를 제거함으로써 순열이 완성됩니다.
결과
/* 
[
  [ 'A', 'B', 'C' ], [ 'A', 'B', 'D' ], [ 'A', 'B', 'E' ],
  [ 'A', 'C', 'B' ], [ 'A', 'C', 'D' ], [ 'A', 'C', 'E' ],
  [ 'A', 'D', 'B' ], [ 'A', 'D', 'C' ], [ 'A', 'D', 'E' ],
  [ 'A', 'E', 'B' ], [ 'A', 'E', 'C' ], [ 'A', 'E', 'D' ],
  [ 'B', 'A', 'C' ], [ 'B', 'A', 'D' ], [ 'B', 'A', 'E' ],
  [ 'B', 'C', 'A' ], [ 'B', 'C', 'D' ], [ 'B', 'C', 'E' ],
  [ 'B', 'D', 'A' ], [ 'B', 'D', 'C' ], [ 'B', 'D', 'E' ],
  [ 'B', 'E', 'A' ], [ 'B', 'E', 'C' ], [ 'B', 'E', 'D' ],
  [ 'C', 'A', 'B' ], [ 'C', 'A', 'D' ], [ 'C', 'A', 'E' ],
  [ 'C', 'B', 'A' ], [ 'C', 'B', 'D' ], [ 'C', 'B', 'E' ],
  [ 'C', 'D', 'A' ], [ 'C', 'D', 'B' ], [ 'C', 'D', 'E' ],
  [ 'C', 'E', 'A' ], [ 'C', 'E', 'B' ], [ 'C', 'E', 'D' ],
  [ 'D', 'A', 'B' ], [ 'D', 'A', 'C' ], [ 'D', 'A', 'E' ],
  [ 'D', 'B', 'A' ], [ 'D', 'B', 'C' ], [ 'D', 'B', 'E' ],
  [ 'D', 'C', 'A' ], [ 'D', 'C', 'B' ], [ 'D', 'C', 'E' ],
  [ 'D', 'E', 'A' ], [ 'D', 'E', 'B' ], [ 'D', 'E', 'C' ],
  [ 'E', 'A', 'B' ], [ 'E', 'A', 'C' ], [ 'E', 'A', 'D' ],
  [ 'E', 'B', 'A' ], [ 'E', 'B', 'C' ], [ 'E', 'B', 'D' ],
  [ 'E', 'C', 'A' ], [ 'E', 'C', 'B' ], [ 'E', 'C', 'D' ],
  [ 'E', 'D', 'A' ], [ 'E', 'D', 'B' ], [ 'E', 'D', 'C' ]
]
*/

case 2. 순서를 생각하지 않고 3장을 선택할 때의 모든 경우의 수

  • 2번 조건에서 모든 경우의 수를 구할 때는 3장을 하나의 그룹으로 선택해야 합니다.
  • 다음과 같은 방법으로 경우의 수를 구합니다.
  1. 순열로 구할 수 있는 경우를 찾습니다.
  2. 순열로 구할 수 있는 경우에서 중복된 경우의 수를 나눕니다.
  • 먼저, 조합은 순열과 달리 순서를 고려하지 않습니다. 만약 순열처럼 순서를 생각하여 경우의 수를 센다면, 조합으로써 올바르지 않을 겁니다.
  • 예를 들어 순열에서는 [A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A]의 여섯 가지는 모두 다른 경우로 취급하지만, 조합에서는 이 여섯 가지를 하나의 경우로 취급합니다. 다시 말해 순열에서처럼 순서를 생각하여 선택하면, 중복된 경우가 6배 발생합니다.
  • 여기서 나온 여섯 가지 경우의 수는 3장의 카드를 순서를 생각하여 나열한 모든 경우의 수입니다.
  • 3장의 카드를 순열 공식에 적용한 결과가 3! / (3-3)! = (3 X 2 X 1) / 1 = 6 입니다. 순서를 생각하느라 중복된 부분이 발생한 순열의 모든 가짓수를, 중복된 6가지로 나누어 주면 조합의 모든 경우의 수를 얻을 수 있습니다.
  • 따라서 (5 X 4 X 3 X 2 X 1) / ((3 X 2 X 1) X (2 X 1)) = 10 입니다.
    - 5장에서 3장을 무작위로 선택하는 조합에서 모든 경우의 수 = 5C3 = 5! / (3! 2!) = 10
    - 일반식: nCr = n! / (r!
    (n - r)!)
  • 그렇다면, 조합의 모든 경우의 수를 나열하고 싶다면 어떻게 해야 할까요?
    예) [A, B, C], [A, B, D]\, [A, B, E], [B, C, D] ... 등
// 반복문 코드
function combinationLoop() {
	// 조합 요소가 인자로 주어질 경우, 인자 그대로 사용하면 되지만, 인자가 주어지지 않고
	// 문제 안에 포함되어 있을 경우 이런 식으로 직접 적어서 사용합니다.
  let lookup = ['A', 'B', 'C', 'D', 'E'];
  let result = [];
  console.log(lookup);
  for (let i = 0; i < lookup.length; i++) {
    for (let j = i + 1; j < lookup.length; j++) {
      for (let k = j + 1; k < lookup.length; k++) {
        result.push([lookup[i], lookup[j], lookup[k]]);
      }
    }
  }
  return result;
}
combinationLoop();
  • 순열과 마찬가지로 result 배열 안에 순열의 경우의 수를 삽입한 뒤, 반환하는 함수입니다.
순열과 다른 점은, 반복의 조건에 있습니다. (i = 0, j = i + 1, k = j + 1)
  • 한 번 조합한 요소는 다시 조합하지 않습니다. 하나의 요소로 만들 수 있는 모든 경우의 수를 다 구한 다음, 그 요소를 반복에 포함하지 않고 다음 요소부터 시작합니다.
결과
/*
[
  [ 'A', 'B', 'C' ], [ 'A', 'B', 'D' ], [ 'A', 'B', 'E' ],
  [ 'A', 'C', 'D' ], [ 'A', 'C', 'E' ], [ 'A', 'D', 'E' ],
  [ 'B', 'C', 'D' ], [ 'B', 'C', 'E' ], [ 'B', 'D', 'E' ], 
	[ 'C', 'D', 'E' ]
]
*/
반복문으로 순열과 조합을 만들어낼 수는 있지만, 분명한 한계점이 존재한다.
  1. 개수가 늘어나면 반복문의 수도 늘어난다.
  2. 뽑아야 되는 개수가 n개 처럼 변수로 들어왔을 때 대응이 어렵다.

GCD와 LCM - GCD와 LCM을 이용한 문제들

유클리드 호제법을 이용한 공식

유클리드 호제법을 이용해 최대공약수를 구하는 로직
function gcd(a, b){
	while(b !== 0){
		let r = a % b;
		a = b;
		b = r;
	}
	return a;
}
  • while문은 b는 0이 아니어야 함을 조건으로 받고 있는데, 왜 0이 아니어야 하냐면 모든 자연수를 0으로 나누게 되면 리턴되는 값이 Infinity이기 때문이다.
    값이 무한대로 나오면 안 되기 때문에 해당 조건을 걸어둠으로써 값이 제대로 나오지 않는 상황을 방지한다.
  • 해당 조건을 지키며 b 가 0이 될 때까지 계속 while문은 돌아간다.
    변수 r 은 a와 b의 나머지가 할당이 되어 있는 그 밑으로 a는 b로 재할당을 시키고, b는 r로 재할당을 시키고 있습니다. 그리고 마지막으로 리턴하는 값은 a로, 이 a를 리턴하는 이유는 while문이 돌아가면서 나누는 수를 재할당을 하기 때문이다.
유클리드 호제법을 이용해 최소공배수를 구하는 로직
function lcm(a, b){
	return a * (b / gcd(a, b));
}
  • 최대공약수의 값은 위에서 만들었던 함수 gcd를 이용해 구할 수 있다.

멱집합 - Power Set

  • 집합 S가 있을 때, Power Set인 P(S)는 집합 S의 거듭제곱 집합으로, S의 모든 부분 집합의 집합을 의미합니다.
  • 예를 들어 S가 {a, b, c} 으로 요소가 3개일 때,
  • P(S)는 {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}} 으로 요소가 8개임을 알 수 있습니다.
  • 즉 S에 n개의 요소가 있다면 P(S)에는 2^n의 요소가 있음을 의미합니다.

  • Input : Set[], set_size
    1. 모든 집합의 크기를 가져옵니다. power_set_size = pow(2, set_size)
    2. 0에서부터 power_set_size까지의 반복문 실행
    a. i = 0에서 set_size까지 크기를 지정해 반복문을 돌립니다. 그리고 집합에서 i번째 요소에 해당하는 하위 집합을 출력합니다.
    b. 하위 집합을 구하면 개행을 통해 집합을 구분합니다.
  • 주어진 집합 S에 대해 거듭제곱 집합은 0과 2^n-1 사이의 모든 이진수를 생성하여 찾을 수 있습니다. 여기서 n은 집합의 크기입니다. 예를 들어 집합 S {x, y, z}에 대해 0부터 2^3-1까지의 모든 이진수를 생성하고, 생성된 각 숫자에대해 해당 숫자의 집합 비트를 고려하여 해당 집합을 찾을 수 있습니다.
  • 아래는 위에서 소개한 접근 방식을 구현한 것입니다.
let inputSet = ['a', 'b', 'c'];
function powerSet (arr) {
	const result = [];
	function recursion (subset, start) {
		result.push(subset);
		for(let i = start; i < arr.length; i++){
			recursion([...subset, arr[i]], i+1);
			//이렇게도 구현할 수 있습니다.
			recursion(subset.concat(arr[i]), i+1);
		}
	}
	recursion([], 0);
	return result;
}
poserSet(inputSet);
  • Output
[
  [],
  [ 'a' ],
  [ 'a', 'b' ],
  [ 'a', 'b', 'c' ],
  [ 'a', 'c' ],
  [ 'b' ],
  [ 'b', 'c' ],
  [ 'c' ]
]
  • powerSet 로직은 재귀함수를 이용하여 구현한 것입니다. 재귀함수에 부분집합을 만들기 위한 빈배열과 시작할 숫자를 지정합니다. 이어 숫자가 커지게끔 하면서 중심 로직인 반복문을 돌려 부분집합을 만든 뒤, 최종적으로 배열 result에 push한다.

정규표현식

  • 문자열에서 특정한 규칙에 따른 문자열 집합을 표현하기 위해 사용되는 형식 언어

정규 표현식 예시

  • 이메일 유효성 검사
const email = 'kimcoding@codestates.com';
let result = '올바릅니다.';
// 1. 정규표현식 사용
let regExp = /^[0-9a-zA-Z]([-_.]?[0-9a-zA-Z])*@[0-9a-zA-Z]([-_.]?[0-9a-zA-Z])*.[a-zA-Z]{2,3}$/i;
if(regExp.test(email) === false) result = '올바르지 않습니다.';
result; // '올바르지 않습니다.'
-----------------------------------------------------------------------------
// 2. 정규표현식이 아닌 경우, 이메일 아이디가 영문 소문자인지 확인하는 코드
let idx = email.indexOf('@');
if(idx === -1) result = '영문 소문자가 아닙니다.';
let ID = email.slice(0,idx);
ID.split('').forEach(e => {
	e = e.charCodeAt(0);
	if(e < 97 || e > 122){
	result = '영문 소문자가 아닙니다.';
	}
});
result; // '올바릅니다.'
  • 휴대전화 번호 유효성 검사
let regExp = /^01([0|1|6|7|8|9]?)-?([0-9]{3,4})-?([0-9]{4})$/;

정규표현식 사용하기

리터럴 패턴

  • 정규표현식 규칙을 슬래시(/)로 감싸 사용합니다. 슬래시 안에 들어온 문자열이 찾고자 하는 문자열이며, 컴퓨터에게 '슬래시 사이에 있는 문자열을 찾고 싶어!'라고 명령을 내리는 것
let pattern = /c/;
// 'c 를 찾을 거야!' 라고 컴퓨터에게 명령을 내리는 것입니다.
// 찾고 싶은 c를 pattern 이라는 변수에 담아놨기 때문에 이 변수를 이용하여 c 를 찾을 수 있습니다.

생성자 함수 호출 패턴

  • RegExp 객체의 생성자 함수를 호출하여 사용

정규식 패턴

정규식 패턴설명
^줄(Line)의 시작에서 일치 /^abc/
</td><td>(Line)의끝에서일치/xyz</td><td>줄(Line)의 끝에서 일치 /xyz/
.(특수기호, 띄어쓰기를 포함한) 임의의 한 문자
a|ba or b 와 일치, 인덱스가 작은 것을 우선 반환
0회 이상 연속으로 반복되는 문자와 가능한 많이 일치. {0,} 와 동일
?0회 이상 연속으로 반복되는 문자와 가능한 적게 일치. {0} 와 동일
+1회 이상 연속으로 반복되는 문자와 가능한 많이 일치. {1,} 와 동일
+?1회 이상 연속으로 반복되는 문자와 가능한 적게 일치. {1} 와 동일
{3}숫자 3개 연속 일치
{3,}3개 이상 연속 일치
{3, 5}3개 이상 5개 이하 연속 일치
()캡쳐(capture)할 그룹
[a-z]a부터 z 사이의 문자 구간에 일치(영어 소문자)
[A-Z]A부터 Z 사이의 문자 구간에 일치(영어 대문자)
[0-9]0부터 9 사이의 문자 구간에 일치(숫자)
(역슬래쉬)escape 문자. 특수 기호 앞에 \를 붙이면 정규식 패턴이 아닌, 기호 자체로 인식
\d숫자를 검색함. /[0-9]/와 동일
\D숫자가 아닌 문자를 검색함. /[^0-9]/와 동일
\w영어대소문자, 숫자, (underscore)를 검색함. /[A-Za-z0-9]/ 와 동일
\W영어대소문자, 숫자, (underscore)가 아닌 문자를 검색함. /[^A-Za-z0-9]/ 와 동일
[^][]안의 문자열 앞에 ^이 쓰이면, []안에 없는 문자를 검색함

정규표현식 내장 메소드

RegExp 객체의 메소드

exec()
  • 원하는 정보를 뽑아내고자 할 때 사용합니다. 검색의 대상이 찾고자 하는 문자열에 대한 정보를 가지고 있다면 이를 배열로 반환하며, 찾는 문자열이 없다면 null을 반환
let pattern = /c/; // 찾고자 하는 문자열
pattern.exec('codestates') // 검색하려는 대상을 exec 메소드의 첫 번째 인자로 전달합니다.
// 즉, 'codestates' 가 'c' 를 포함하고 있는지를 확인합니다.
// 이 경우 'c' 가 포함되어 있으므로, ['c'] 를 반환합니다
test()
  • 찾고자 하는 문자열이 대상 안에 있는지의 여부를 boolean 으로 리턴
let pattern = /c/;
pattern.test('codestates');
// 이 경우는 'codestates'가 'c'를 포함하고 있으므로 true 를 리턴합니다.

String 객체의 메소드

match()
  • RegExp.exec() 와 비슷한 기능을 하며, 정규 표현식을 인자로 받아 주어진 문자열과 일치된 결과를 배열로 반환합니다. 일치되는 결과가 없으면 null을 리턴
let pattern = /c/;
let str = 'codestates';
str.match(pattern);
// str 안에 pattern 이 포함되어 있으므로, ['c'] 를 반환합니다.
replace()
  • '검색 후 바꾸기'를 수행합니다. 첫 번째 인자로는 정규표현식을 받고, 두 번째 인자로는 치환하려는 문자열을 받습니다. 문자열에서 찾고자 하는 대상을 검색해서 이를 치환하려는 문자열로 변경 후 변경된 값을 리턴
let pattern = /c/;
let str = 'codestates';
str.replace(pattern, 'C');
// str 안에서 pattern 을 검색한 후 'C' 로 변경하여 그 결과를 리턴합니다.
// 여기서는 'Codestates'가 반환됩니다.
split()
  • 주어진 인자를 구분자로 삼아, 문자열을 부분 문자열로 나누어 그 결과를 배열로 반환
"123,456,789".split(",")  // ["123", "456", "789"]
"12304560789".split("0")  // ["123", "456", "789"]
  • 정규표현식을 인자로 받아 가장 처음 매칭되는 부분 문자열의 위치를 반환합니다. 매칭되는 문자열이 없으면 -1을 반환
"JavaScript".search(/script/); // -1 대소문자를 구분합니다
"JavaScript".search(/Script/); // 4
"codestates".search(/ode/); // 1

flag

  • 정규표현식은 플래그를 설정해 줄 수 있으며, 플래그는 추가적인 검색 옵션의 역할을 해 줍니다. 이 플래그들은 각자 혹은 함께 사용하는 것이 모두 가능하며, 순서에 구분이 없다.
i
  • i를 붙이면 대소문자를 구분하지 않습니다.
let withi = /c/i;
let withouti = /c/;
"Codestates".match(withi); // ['C']
"Codestates".match(withouti); // null
g
  • global 의 약자로, g를 붙이면 검색된 모든 결과를 리턴
let withg = /c/g;
let withoutg = /c/;
"coolcodestates".match(withg); // ['c', 'c']
"coolcodestates".match(withoutg); // ['c'] g 가 없으면 첫 번째 검색 결과만 반환합니다
m
  • m을 붙이면 다중행을 검색한다.
let str = `1st : cool
2nd : code
3rd : states`;
str.match(/c/gm)
// 3개의 행을 검색하여 모든 c 를 반환합니다.
// ['c', 'c']
str.match(/c/m)
// m은 다중행을 검색하게 해 주지만, g 를 빼고 검색하면 검색 대상을 찾는 순간 검색을 멈추기 때문에
// 첫 행의 ['c'] 만 리턴합니다.

정규식 패턴(표현식)

Anchors : ^ and $

^
  • ^는 문자열의 처음을 의미하며, 문자열에서 ^뒤에 붙은 단어로 시작하는 부분을 찾습니다. 일치하는 부분이 있더라도, 그 부분이 문자열의 시작 부분이 아니면 null을 리턴
"coding is fun".match(/^co/); // ['co']
"coding is fun".match(/^fun/); // null
$
  • $는 문자열의 끝을 의미하며, 문자열에서 $앞의 표현식으로 끝나는 부분을 찾습니다. ^와 비슷하지만 ^는 문자열의 시작을 찾는 반면, $는 문자열의 마지막 부분을 찾습니다. 마찬가지로 일치하는 부분이 있더라도, 그 부분이 문자열의 끝부분이 아니면 null을 리턴
"coding is fun".match(/un$/); // ['un']
"coding is fun".match(/is$/); // null
"coding is fun".match(/^coding is fun$/);
// 문자열을 ^ 와 $ 로 감싸주면 그 사이에 들어간 문자열과 정확하게 일치하는 부분을 찾습니다
// ["coding is fun"]

Quantifiers : *, +, ? and {}

*
  • * 의 바로 앞의 문자가 0번 이상 나타나는 경우를 검색합니다. 아래와 같은 문자열이 있을 때에 /ode/g 을 사용하게 되면 "od" 가 들어가면서 그 뒤에 "e"가 0번 이상 포함된 모든 문자열을 리턴
"co cod code codee coding codeeeeee codingding".match(/ode*/g);
// ["od", "ode", "odee", "od", "odeeeeee", "od"]
+
  • * 와 같은 방식으로 작동하며, 다만 + 바로 앞의 문자가 1번 이상 나타나는 경우를 검색한다는 점이 과 다를 뿐
"co cod code codee coding codeeeeee codingding".match(/ode+/g);
// ["ode", "odee", "odeeeeee"]
?
  • ? 는 (쉬프트+8) 또는 + 와 비슷하지만, ? 앞의 문자가 0번 혹은 1번 나타나는 경우만 검색합니다. (쉬프트+8)? 또는 +? 와 같이 ?는 * 혹은 + 와 함께 쓰는 것도 가능하며, 함께 사용하였을 경우 검색 결과가 어떻게 달라지는지 아래 예시를 통해 비교
"co cod code codee coding codeeeeee codingding".match(/ode?/g);
// ["od", "ode", "ode", "od", "ode", "od"]
"co cod code codee coding codeeeeee codingding".match(/ode*?/g);
// ["od", "od", "od", "od", "od", "od"]
"co cod code codee coding codeeeeee codingding".match(/ode+?/g);
// ["ode", "ode", "ode"]
{}
  • {}는 (쉬프트+8), (쉬프트+8)?, +, +? 의 확장판으로 생각할 수 있습니다. (쉬프트+8), (쉬프트+8)?, +, +? 가 '0개 이상' 또는 '1개 이상' 검색이 전부였던 반면, {}는 직접 숫자를 넣어서 연속되는 개수를 설정할 수 있습니다. 아래 예시와 함께 위 표에서 {}와 (쉬프트+8), *?, +, +? 의 차이를 다시 한 번 비교
"co cod code codee coding codeeeeee codingding".match(/ode{2}/g);
// 2개의 "e"를 포함한 문자열을 검색합니다.
// ["odee", "odee"]
"co cod code codee coding codeeeeee codingding".match(/ode{2,}/g);
// 2개 이상의 "e"를 포함한 문자열을 검색합니다.
// ["odee", "odeeeeee"]
"co cod code codee coding codeeeeee codingding".match(/ode{2,5}/g);
// 2개 이상 5개 이하의 "e"를 포함한 문자열을 검색합니다.
// ["odee", "odeeeee"]

OR operator

|
  • or 조건으로 검색하여 | 의 왼쪽 또는 오른쪽의 검색 결과를 반환
"Cc Oo Dd Ee".match(/O|D/g); // ["O", "D"]
"Cc Oo Dd Ee".match(/c|e/g); // ["c", "e"]
"Cc Oo Dd Ee".match(/D|e/g); // ["D", "e"]
"Ccc Ooo DDd EEeee".match(/D+|e+/g); // + 는 1번 이상 반복을 의미하기 때문에
// ["DD", "eee"] 를 반환합니다.

Bracket Operator - []

  • 대괄호 [] 안에 명시된 값을 검색
[abc] // a or b or c 를 검색합니다. or(|) Operator 로 작성한 a|b|c 와 동일하게 작동합니다.
[a-c] // [abc] 와 동일합니다. - 로 검색 구간을 설정할 수 있습니다.
"Ccc Ooo DDd EEeee".match(/[CD]+/g); // [] 에 + 등의 기호를 함께 사용할 수도 있습니다.
// C or D 가 한 번 이상 반복된 문자열을 반복 검색하기 때문에
// ["C", "DD"] 가 반환됩니다.
"Ccc Ooo DDd EEeee".match(/[co]+/g); // ["cc", "oo"]
"Ccc Ooo DDd EEeee".match(/[c-o]+/g); // - 때문에 c ~ o 구간을 검색하여
// ["cc", "oo", "d", "eee"] 가 반환됩니다.
"AA 12 ZZ Ad %% Az !# dd 54 zz".match(/[A-Za-z]+/g);
// a~z 또는 A~Z 에서 한 번 이상 반복되는 문자열을 반복 검색하기 때문에
// ["AA", "ZZ", "Ad", "Az", "dd", "zz"] 를 반환합니다.
"AA 12 ZZ Ad %% Az !# dd 54 zz".match(/[A-Z]+/gi);
// flag i 는 대소문자를 구분하지 않기 때문에 위와 동일한 결과를 반환합니다.
// ["AA", "ZZ", "Ad", "Az", "dd", "zz"]
"AA 12 ZZ Ad %% Az !# dd 54 zz".match(/[0-9]+/g);
// 숫자도 검색 가능합니다.
// ["12", "54"]
"aAbB$#67Xz@9".match(/[^a-zA-Z]+/g);
// [] 안에 ^ 를 사용하면 anchor 로서의 문자열의 처음을 찾는것이 아닌
// 부정을 나타내기 때문에 [] 안에 없는 값을 검색합니다.
// ["$#67", "@9"]

Character classes

\d 와 \D
  • \d의 d 는 digit 을 의미하며 0 ~ 9 사이의 숫자 하나를 검색합니다. [0-9] 와 동일
  • \D 는 not Digit 을 의미하며, 숫자가 아닌 문자 하나를 검색합니다. [^0-9] 와 동일
"abc34".match(/\d/); // ["3"]
"abc34".match(/[0-9]/) // ["3"]
"abc34".match(/\d/g); // ["3", "4"]
"abc34".match(/[0-9]/g) // ["3", "4"]
"abc34".match(/\D/); // ["a"]
"abc34".match(/[^0-9]/); // ["a"]
"abc34".match(/\D/g); // ["a", "b", "c"]
"abc34".match(/[^0-9]/g); // ["a", "b", "c"]
\w 와 \W
  • \w 는 알파벳 대소문자, 숫자, (underbar) 중 하나를 검색합니다. [a-zA-Z0-9]와 동일
  • \W 는 알파벳 대소문자, 숫자, (underbar)가 아닌 문자 하나를 검색합니다. [^a-zA-Z0-9]와 동일
"ab3_@A.Kr".match(/\w/); //["a"]
"ab3_@A.Kr".match(/[a-zA-Z0-9_]/) // ["a"]
"ab3_@A.Kr".match(/\w/g); //["a", "b", "3", "_", "A", "K", "r"]
"ab3_@A.Kr".match(/[a-zA-Z0-9_]/g) // ["a", "b", "3", "_", "A", "K", "r"]
"ab3_@A.Kr".match(/\W/); // ["@"]
"ab3_@A.Kr".match(/[^a-zA-Z0-9_]/); // ["@"]
"ab3_@A.Kr".match(/\W/g); // ["@", "."]
"ab3_@A.Kr".match(/[^a-zA-Z0-9_]/g); // ["@", "."]

Grouping and capturing

()
  • 그룹으로 묶는다는 의미 이외에도 다른 몇 가지 의미가 더 있다.
그룹화
  • 표현식의 일부를 ()로 묶어주면 그 안의 내용을 하나로 그룹화할 수 있다.
let co = 'coco';
let cooo = 'cooocooo';
co.match(/co+/); // ["co", index: 0, input: "coco", groups: undefined]
cooo.match(/co+/); // ["cooo", index: 0, input: "cooocooo", groups: undefined]
co.match(/(co)+/); // ["coco", "co", index: 0, input: "coco", groups: undefined]
cooo.match(/(co)+/); // ["co", "co", index: 0, input: "cooocooo", groups: undefined]
  • co+ 는 "c"를 검색하고 + 가 "o"를 1회 이상 연속으로 반복되는 문자를 검색해 주기 때문에 "cooo"가 반환되었습니다. 하지만 (co)+ 는 "c" 와 "o" 를 그룹화하여 "co"를 단위로 1회 이상 반복을 검색하기 때문에 "coco"가 반환되었습니다. 여기서 특이한 점은 일치하는 문자열로 반환된 결과가 2개이다.
캡처
  • () 로 그룹화한다고 하였고, 이를 캡처한다 라고 한다.
co.match(/(co)+/); // ["coco", "co", index: 0, input: "coco", groups: undefined]
  1. () 로 "co"를 캡처
  2. 캡처한 "co" 는 일단 당장 사용하지 않고, + 가 "co"의 1회 이상 연속 반복을 검색
  3. 이렇게 캡처 이외 표현식이 모두 작동하고 나면, 캡처해 두었던 "co"를 검색
  • 따라서 2번 과정에 의해 "coco" 가 반환되고, 3번에 의해 "co"가 반환되는 것
non-capturing
  • (?:)로 사용하면 그룹은 만들지만 캡처는 하지 않는다.
let co = 'coco';
co.match(/(co)+/); // ["coco", "co", index: 0, input: "coco", groups: undefined]
co.match(/(?:co)+/);
// ["coco", index: 0, input: "coco", groups: undefined]
// 위 "캡처" 예시의 결괏값과 비교해 보시기 바랍니다.
lookahead
  • (?=) 는 검색하려는 문자열에 (?=여기) 에 일치하는 문자가 있어야 (?=여기) 앞의 문자열을 반환
"abcde".match(/ab(?=c)/);
// ab 가 c 앞에 있기 때문에 ["ab"] 를 반환합니다.
"abcde".match(/ab(?=d)/);
// d 의 앞은 "abc" 이기 때문에 null을 반환합니다.
negated lookahead
  • (?!) 는 (?=) 의 부정
"abcde".match(/ab(?!c)/); // null
"abcde".match(/ab(?!d)/); // ["ab"]
profile
선한 영향력을 주는 사람

0개의 댓글