16 Feb 2021
투 포인터 알고리즘
2개의 포인터를 옮겨 가면서 복잡도를 최소한으로 하여 문제를 해결하는 방법입니다.
대표예제
https://www.acmicpc.net/problem/2003
문제
N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
투 포인터 알고리즘을 활용하는 문제 중 두 개의 포인터가 같은 위치에서 이동하는 대표 예제 입니다.
N, target = list(map(int, input().split()))
arr = list(map(int, input().split()))
def solution(N, target, arr):
start = 0
end = 0
answer = 0
while end < N:
if sum(arr[start: end + 1]) < target:
end += 1
elif sum(arr[start: end + 1]) > target:
start += 1
else:
answer += 1
end += 1
return answer
start와 end사이를 하나의 부분집합이라고 봤을때 그 부분집합의 합과 target 값을 비교하여서 target 값보다 작으면 end++ 하고 크면 start ++ 하는 방식으로 해서 end의 값이 배열의 인덱스를 벗어나면 종료하는 방식의 알고리즘 입니다.
이와 같은 방식의 투 포인터 알고리즘이 가능한 이유는 일단 모든 원소가 자연수이기 때문에 가능하다고 할 수 있습니다.
https://leetcode.com/problems/container-with-most-water/
Container With Most Water
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
이 문제는 같은 index에서 출발하는 투 포인터가 아닌 양 끝에서 출발하는 투 포인터의 대표 예제 입니다.
def maxArea(self, height):
start = 0
end = len(height) - 1
answer = 0
while end - start > 0:
answer = max(answer, height[end] * (end - start) if height[start] > height[end] else height[start] * (end - start))
if end - start == 1:
break
if height[start] == height[end]:
if height[end - 1] < height[start + 1]:
start += 1
else:
end -= 1
elif height[start] > height[end]:
end -= 1
else:
start += 1
return answer
양 끝을 기준으로 start와 end를 설정하고 한 칸씩 움직여 가면서 최대값이 될 수 있는 값을 갱신해 나가면서 최대로 담을 수 있는 물의 양을 구하는 것입니다.
이 문제에서 가장 중요하게 생각해야할 부분은 어떠한 기준으로 start와 end를 움직일 것인가라고 생각합니다.
- start와 end 중에 낮은 벽에 의해 물의 양이 정해진다는 것
- 두 벽중에 높은 벽을 계속 해서 유지해야 가장 높은 효율을 낼 수 있을 것
이 2가지 를 기준으로 생각해봤을때 start와 end를 움직이는 기준은 더 낮은 벽을 바꾸는 식으로 진행 하면 된다는 것을 알 수 있습니다.
투 포인터 알고리즘 원리 자체는 어렵지 않기 때문에 원리에 대한 이론 보다는 예제를 통해 알아 보았습니다.
03 Feb 2021
이벤트 버블링
이벤트 버블링은 상위 element에 event를 설정하면 하위element에서 상위element까지 순서대로 event가 실행되는 것을 의미합니다.
Example
<div class="test">
<s class="test">
<p class="test">test</p>
</s>
</div>
<script>
document.querySelectorAll(".test").forEach(element =>
element.addEventListener('click', (event) => console.log(event.currentTarget.tagName)
))
</script>
이렇게 element구성 한 후에 ptag를 클릭하면
이런식으로 출력이 됩니다. p -> s -> div 순으로 event가 전달되기 때문입니다. 하지만 모든 event가 버블링 되는 것은 아닙니다. focus()와 같은 event는 버블링 되지 않습니다.
버블링 중단하기
<body>
<button onclick="event.stopPropagation()">클릭해 주세요.</button>
</body>
이와 같이 하면 버블링을 중단시킬 수 있습니다. 버블링 중단이 꼭 필요한 경우가 아니면 중단 시키지 않는 것이 좋습니다.
이벤트 캡처링
이벤트 캡처링은 이벤트 버블링과의 반대 방향으로 흘러 갑니다. 타겟 element에서 이벤트를 발생시키면 상위 element부터 타겟 element로 단계별로 event가 전달되는 것을 의미합니다.
Example
<div class="test">
<s class="test">
<p class="test">test</p>
</s>
</div>
<script>
document.querySelectorAll(".test").forEach(element =>
element.addEventListener('click', event => console.log(event.currentTarget.tagName), {capture : true}
))
</script>
이렇게 element구성 한 후에 ptag를 클릭하면
이런식으로 출력이 됩니다.
이벤트 위임
캡쳐링과 버블링을 배운 것은 바로 이벤트 위임을 위한 준비 단계라고 할 수 있습니다.
이벤트 위임이란 상위 element에 핸들러를 설정한 후에 event.taget에 따라 다른 행동을 하게 할 수 있습니다. 즉 상위 element에 정한 이벤트 핸들러가 하위element에 전달되는 것 입니다.
Example
<html>
<head>
<meta charset="utf-8">
<title>My test page</title>
</head>
<body>
<div class="test">
<p>test1</p>
<p>test2</p>
<P>test3</P>
</div>
<script>
document.querySelector(".test").addEventListener('click', event => console.log(event.target.textContent))
</script>
</body>
</html>
각 ptag를 클릭하면 자신이 가지고 있는 textContent를 출력할 수 있습니다.
ptag의 상위 element인 div에 이벤트 핸들러를 설정했지만 ptag도 그 이벤틀 핸들러를 위임 받아 사용했다고 할 수 있겠습니다.
event.target을 잘 이용하면 하나의 핸들러로 많은 종류의 이벤트를 설정할 수 있습니다.
정리
표준 DOM 이벤트가 전달되는 과정 3가지
- 캡쳐링 - 상위
element에서 하위element로 전달
- 타겟 - 타겟
element에 전달
- 버블링 - 하위
element에서 상위element로 전달
캡쳐링은 쓸일이 거의 없기 때문에 크게 개의치 않아도 되지만 버블링은 자주 사용된다. 그리고 버블링 중단은 꼭 필요한 경우가 아니면 사용하지 않는 것이 좋다.
캡쳐링과 버블링은 이벤트 위임을 위한 초석이었다.
이벤트 위임을 잘 이용하면 매우 간단하게 많은 이벤트를 구현할 수 있습니다.
출처
https://ko.javascript.info/bubbling-and-capturing
https://ko.javascript.info/event-delegation
28 Jan 2021
호이스팅
ES6가 도입되기전 함수 내에서 변수를 선언할때 let을 도입하기 전 var를 사용했습니다. let으로 변수를 선언할 경우 선언이 되어지기 전에는 변수를 사용할 수 없습니다. 하지만 var로 변수를 선언하면 변수를 선언하기 전에 사용할 수 있습니다.
Example
var1; // Error
let var1; // undefined
x; // undefined
var x = 3;
x; // 3
이와 같이 선언되지 않은 변수가 에러가 나지 않는 이유는 호이스팅 때문입니다. 호이스팅이라는 것은 변수가 적용되는 스코프 내에서 가장 위에서 var를 이용한 변수 선언이 적용된는 것입니다. 하지만 선언과 할당을 같이 한다고 해서 할당까지 함께 끌어 올려지는 것이 아닌 오직 선언만이 끌어올려집니다.
함수 호이스팅
함수도 마찬가지로 호이스팅이 됩니다. 하지만 함수를 변수에 할당하면 호이스팅 되지 않습니다.
f();
function f() {
console.log(1)
} // no Error
f2();
let f2 = function() {
console.log(2)
} // f2 is not a function
아까도 얘기했다시피 호이스팅은 피하는 것이 가장 좋다. 호이스팅이 적용될 경우 코드의 가독성이 떨어지기 때문에 좋지 않은 영향을 끼칠 수 있다. 그래서 ES6에서 let을 새로이 내놓았고 가급적이면 let이나 const변수를 이용하는 것이 좋을 것이다. 하지만 ES5로 트랜스 컴파일을 해야함으로 우리는 var와 호이스팅에 대한 이해를 해야합니다.
출처
https://gmlwjd9405.github.io/2019/04/22/javascript-hoisting.html
러닝 자바스크립트 : 한빛미디어
27 Jan 2021
말 그대로 즉시실행 함수이다. 함수의 선언과 실행을 동시에 한다고 보면된다.
Example
(function () {
console.log(1)
})(); // 1
그럼 왜 쓰는 것일까?
전역 스코프를 오염시키지 않기 위해서 사용합니다. 이를 다른말로 표현하면 private 스코프를 사용하기 위함이다.
IIFE의 가장 흔한 예는 counting함수이다. 우리가 어떤 버튼을 만들고 이 버튼이 몇번 눌렸는지에 대해 기억하고 싶다고 생각을 해보자. 가장 쉬운 방법은 전역 스코프에 count변수를 선언한 후에 누를때 마다 count+1하는 방법이 있을 것이다. 하지만 count라는 변수가 실수에 의해 오염되어 정확하지 않은 수치로 변할 수가 있다. 하지만 IIFE를 이용하면 이를 막을 수 있을 것이다.
var buttonCount = (function(){
let count = 0
return function(){
count += 1
return count
}
})();
console.log(buttonCount()); // 1
console.log(buttonCount()); // 2
console.log(buttonCount()); // 3
이와 같이 buttonCount()를 실행 할때마다 함수 내부에 있는 count변수가 1씩 늘어 납니다. 하지만 count변수를 제어 할 수 있는 것은 buttonCount()밖에 없기 때문에 아주 private하다고 할 수 있겠습니다. 그리고 전역 스코프에 선언하 변수도 아니기에 전역 스코프도 오염되지 않았습니다.
IIFE에 대해 간단하게 알아보았다. 나는 아직 JavaScript에 심도있는 경험이 없어서 그런지 완벽하게 어떤 때에 사용해야 할지에 대해서는 감이 잘 오지는 않지만 혹시 나중에 사용하게 된다면 이 포스팅에 보충 설명을 추가 하도록 하겠습니다.
참조
https://velog.io/@jakeseo_me/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EA%B0%9C%EB%B0%9C%EC%9E%90%EB%9D%BC%EB%A9%B4-%EC%95%8C%EC%95%84%EC%95%BC-%ED%95%A0-33%EA%B0%80%EC%A7%80-%EA%B0%9C%EB%85%90-8-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%ED%95%84%EC%88%98%EC%9A%94%EC%86%8C-IIFE-%EB%A7%88%EC%8A%A4%ED%84%B0%ED%95%98%EA%B8%B0
https://starkying.tistory.com/entry/Javascript-Closure-%EA%B7%B8%EB%A6%AC%EA%B3%A0-IIFE%EC%9D%98-%ED%99%9C%EC%9A%A9
러닝 스크립트 : 한빛미디어
25 Jan 2021
스코프란 ‘‘변수에 접근할 수 있는 범위’‘라고 할 수 있습니다.
변수와 상수, 매개변수가 언제 어디서 정의되는지 결정하는 것입니다.
Example
function f(x) {
return x + 3
}
f(5); // 8
x; // x is not defined
x의 스코프는 함수 f입니다.
변수가 스코프내에 있지 않다고 해서 존재하지 않는 것은 아니니 이 차이에 대해 인지 하고 있어야 합니다.
정적 스코프
자바스크립트는 정적 스코프 언어이다.
정적 스코프는 어떤 변수가 함수 스코프 안에 있는지 함수를 정의할 때 알 수 있다는 뜻입니다.
Example
const x = 5;
function f() {
console.log(x)
console.log(y)
}
{
const y = 10;
f();
}
// 5
// y is not defined
x 변수는 f함수를 정의 할 때 스코프 내에 존재 하였지만 y 변수는 존재하지 않았기 때문에 오류가 발생 하였습니다. f함수를 정의 할때 접근 할 수 있었던 변수에는 호출할 때도 여전히 접근할 수 있지만 호출할 때 스코프에 있는 변수에는 접근할 수 없습니다.
전역 스코프
자바스크립트 프로그램을 시작할 때, 즉 어떤 함수도 호출하지 않았을 때 실행 흐름은 전역스코프에 있습니다. 즉, 전역스코프에서 선언한 것은 무엇이든 프로그램의 모든 스코프에서 볼수 있습니다.
하지만 전역스코프에 의존하는 것은 매우 좋지 않습니다. 전역 스코프에 존재하는 변수는 어디서든 변경될 수 있기 때문에 문제가 발생하더라도 찾기 힘들뿐더러 가 생길 소지가 다분하기 때문입니다.
블록 스코프
let과 const는 식별자를 블록 스코프에서 선언합니다. 블록 스코프는 블록 내에서만 보이는 식별자를 의미합니다.
Example
{
let x = {color : "blue"};
let y = x;
let z = 3;
{
let x= 5;
console.log(x); // 5
console.log(y.color); // blue
y.color = "red";
console.log(z); // 3
}
console.log(x.color); // red 내부 블록에서 변경됨
console.log(y.color); // red
console.log(z); // 3
}
클로저
클로저는 외부함수에 존재하는 변수에 대해 내부함수를 할당하여도 그 변수를 참조할 수 있음을 의미한다.
쉽게 얘기하면 내부 함수를 할당받게 되면 내부 함수의 스코프자체도 함께 할당받게 되어 외부 함수의 변수도 함께 참조 가능한것이다.
Example
function makeFunc(){
var x = 1;
return function(y){
console.log(x+y)
}
}
var myFunc = makeFunc();
myFunc(5); // 6
myFunc에는 makeFunc의 내부함수가 할당 되었다. 일반적이라면 x는 내부함수에 존재하지 않는 변수 이므로 myFunc를 실행했을때 오류가 나야하지만 함수가 선언된 시점에 존재하는 스코프를 함께 가져가기때문에 x도 참조가능하게 된 것이다. 그저 숫자로서의 값이 전달되는 것이 아니라 x라는 변수자체가 전달되는 것이기 때문에 x를 변경하는 것도 가능하다.
출처
https://developer.mozilla.org/ko/docs/Web/JavaScript/Guide/Closures#%ED%81%B4%EB%A1%9C%EC%A0%80closure
러닝 자바스크립트 : 한빛미디어