10986. 나머지 합
·
PS/Baekjoon
📜 문제 설명N개의 숫자가 주어질 때, 연속된 부분 구간 합이 M으로 나누어 떨어지는 구간의 개수배열 [1, 2, 3, 1, 2]에서 3으로 나누어 떨어지는 구간?👉 [1, 2], [1, 2, 3], [3], [2, 3, 1], [3, 1, 2], [1, 2] = `7개`N: 숫자 개수 (N ≤ 백만)M: 나누는 수 (M A₁ 숫자가 백만 개까지 주어질 수 있어서 `O(NLogN) 이하`의 시간 복잡도로 풀어야 시간 초과가 나지 않는다.부분 구간의 개수를 구해야 하므로 계산 할 때마다 합을 구해 나가는 게 아닌, `누적합`을 이용해 풀어야 한다.M으로 나누어 떨어지는, 즉 M으로 나눈 나머지가 0인 구간을 구하려면 `(A+B) % M == 0` 수식으로 풀면 된다.📌 나머지 연산(A+B)%C 는 {..
139. Word Break
·
PS/LeetCode
📜 문제문자열 `s`, 단어 사전 `wordDict`가 주어짐wordDict에 있는 단어들로 s를 분할할 수 있는지 확인 (≒ 단어들로 s를 만들 수 있는지 확인)wordDict내의 단어들은 여러번 재사용 가능생각 하기40분 정도 고민하다가 답을 봤다.나는 단어 사전에 있는 단어들의 첫글자를 key로 하여 Map에 저장 하여 접근하도록 했다.예시) wordDict =[cats, sand, dog, and, cat]Map: [a - and], [c - cat, cats], [d - dog ], [s- sand]dfs를 이용하여 접근했지만, 시간초과에 걸려서 틀렸다. (∵ 중복 탐색)이 문제를 풀기 위해선, 이전 값의 결과를 저장해 중복 탐색을 하지 않도록 `memoization`을 이용해야한다.`DFS`..
함수 vs 메서드
·
Dev Trivia
함수 (Function)독립적인 코드 블럭으로 특정 작업 수행객체 (클래스)에 속하지 않고, 전역적 또는 모듈 단위로 존재function greet(name) { return "Hello, " + name;}console.log(greet("Alice"));메서드 (Method)클래스 또는 객체에 속하는 함수특정 객체에 대한 동작을 정의객체를 통해 호출됨const person = { name: "Alice", greet: function() { return "Hello, " + this.name; }};console.log(person.greet());함수와 메서드의 차이 구분함수 (Function)메서드 (Method)소속클래스와 무관 (독립적)클래스 또는 객체 내부에..
735. Asteroid Collision - Java
·
PS/LeetCode
📜 문제행성의 크기와 방향을 나타내는 정수 배열(`asteroids`)이 주어짐음수는 왼쪽, 양수는 오른쪽으로 이동행성의 인덱스는 상대적인 위치를 나타낸다.같은 방향으로 이동하는 행성을 절대 충돌하지 않는다.`행성이 충돌하는 경우` 더 작은 행성만 파괴 되고, 크기가 같으면 둘 다 파괴 된다.요구사항: 살아남은 소행성들을 출력하기 생각하기어떤 경우에 소행성들이 충돌하는지 알아 보자위 그림에서 보면 `양수, 음수` 순서대로 주어졌을 때만 소행성이 충돌한다.충돌하는 경우를 알았으니, 예제를 통해서 접근 방식을 알아보자. asteroids = `[-1, -2, 12, 11, 6, 5, -10, 4, -4, 6, 7]` 일 때,[5,-10] 구간에서 아래와 같이 충돌이 연쇄적으로 발생한다.|5| [6] |11..