본문 바로가기

전체 글539

[Programmers] Lv 2. 가장 큰 정사각형 찾기 https://school.programmers.co.kr/learn/courses/30/lessons/12905 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr function solution(board) { return board.reduce((acc, rows, i, board) => { if (rows.length { if (!j) return; if (column) { board[i][j] = Math.min(board[i - 1][j - 1], board[i - 1][j], board[i][j - 1]) + 1; acc = Math.max(acc.. 2023. 3. 20.
[Algorithm] 완전 탐색과 종류 (Brute Force Search) 완전 탐색, Brute Force Search 란? 완전 탐색과 브루트 포스의 이름에서 유추할 수 있듯이 이 알고리즘의 방법은 발생 가능한 모든 경우의 수를 전부 탐색하면서 조건에 맞는 답을 찾아내는 방법이다. 이 알고리즘의 대표적인 장점은 모두 확인하기 때문에 100%의 확률로 정답만을 출력한다는 것이다. 하지만 확실하게 확인하는 만큼 시간이 오래 걸리는 탐색기법이다. 💡 Brute : 무식한, 짐승 같은 + Force : 힘 - 무식하게 풀기 완전 탐색의 종류 구조로 나누어보면 선형 구조를 전체적으로 탐색하는 방법인 순차 탐색과 비선형 구조를 전체적으로 탐색하는 방법인 DFS / BFS가 대표적인 탐색 방법이다. 1. 브루트 포스 (Brute Force) 브루트 포스는 반복문과 조건문을 사용하여 가능.. 2023. 3. 20.
[Algorithm] Tail Recursion (꼬리 재귀) 재귀 함수 재귀 함수는 '기저 사례(base case)'와 '재귀적 관계(recurrence relation)'만 알면 정말 간단하게 구현할 수 있다. 그리고 보통 코드가 짧아서 가독성도 좋다. 쪼개지지 않는 가장 작업들을 가리켜 재귀 호출의 기저 사례(base case) 자기 자신과 관계를 맺는 형식을 재귀적 관계(recurrence relation) 하지만 장점이 있으면 단점도 있는 법이다. 재귀 호출을 할 때마다 콜 스택에 새로운 프레임이 쌓이고, 각 프레임은 지역 변수나 인수를 저장하기 위해 메모리를 사용한다. 이게 보통은 문제가 되지 않지만, 만약 각 프레임에서 기가바이트 단위의 데이터를 받아 처리해야 하는 경우에는 문제가 심각해질 수도 있다. 혹은 콜 스택이 너무 깊어지면 스택 공간이 가득차 .. 2023. 3. 19.
[Daily Scrum] Meet 10. 2023-03-17 금요일 시간 : 22:00 ~ 22:30 진행 내용 : Todo list 공유, 내일 학습 계획 공유, 팀원간 소통 개인 학습 내용 : 프로그래머스 1문제(Lv. 2) 풀이 Union-Find 알고리즘 학습 2023. 3. 17.
[Algorithm] Disjoint Set의 표현: Union-Find (합집합 찾기) Disjoint Set (서로소 집합) 'Disjoint set'는 공통 원소가 없는 부분 집합들이다. 어떤 교양 대면 수업에 여러 학과 사람들이 모여있다고 해보자. 이때 교수님이 갑자기 같은 과 사람들끼리 조를 만들라고 한다. 그럼 학생들은 이리 저리 돌아다니다가 같은 과 사람을 찾으면 팀을 이뤄 같이 움직이게 될 것이다. 그리고 팀끼리도 같은 과인 것을 확인하면 두 팀은 합쳐진다. 만들어진 조들은 공통 원소가 없는 부분 집합들, disjoint set이 된다. 이 상황을 자료구조로 표현한 것이, 즉, disjoint set에 대한 정보를 저장하고 조작하는 자료 구조가 'Union-Find'다. Union-Find 알고리즘 (합집합 찾기) 대표적인 그래프 알고리즘으로 합집합 찾기라고도 불리며, 서로소 .. 2023. 3. 17.
[Programmers] (완전탐색) Lv 2. 전력망을 둘로 나누기 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr BFS 이용 const bfs = (graph, pivot, visited, vistedDuplication) => { const queue = [pivot]; let cnt = 0; while (queue.length) { const dest = queue.shift(); if (vistedDuplication[dest]) return Infinity; (visited[dest] = true),.. 2023. 3. 17.
[Data Structure] 비선형 - 우선순위 큐 '우선순위 큐'는 우선순위가 가장 높은 자료가 가장 먼저 꺼내지는 큐다. C++과 python은 내장 라이브러리로 우선순위 큐를 제공하지만, 자바스크립트는 직접 구현해 사용해야한다. 우선순위 큐는 보통 힙(heap)이라는 트리를 사용해서 구현한다. 힙은 가장 큰/작은 원소를 찾는 데 최적화된 형태의 이진 트리로, 힙을 사용하면 새 원소를 추가하는 연산과 가장 큰/작은 원소를 꺼내는 연산을 모두 O(lgN) 시간에 수행할 수 있다. 여기서는 가장 큰 원소를 찾는 최대 힙(max-heap)을 만들어보자. 힙의 정의 힙이 갖는 가장 중요한 규칙은 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소보다 크다는 것이다. 힙에서 이 규칙은 부모 자식 관계에만 적용된다. 이 규칙에 의하면 트리의 가장 큰 원소는 루.. 2023. 3. 16.
[Daily Scrum] Meet 09. 2023-03-16 목요일 시간 : 22:00 ~ 22:30 진행 내용 : Todo list 공유, 내일 학습 계획 공유, 팀원간 소통 개인 학습 내용 : 프로그래머스 1문제(Lv. 2) 풀이 다익스트라 알고리즘 학습 2023. 3. 16.
[Data Structure] 선형 자료구조 배열 배열은 가장 기초적인 선형 자료구조다. 배열의 원소들은 메모리 상의 연속된 위치에 저장된다. 이 특성 덕분에 캐시의 효율성을 극대화 할 수 있다. 캐시는 보통 메모리의 일정 영역을 저장해놓기 때문에 배열같이 연속적인 위치에 저장된 데이터의 경우 더 빠른 속도로 접근이 가능하다. 배열의 원소들은 각각 인덱스로 구분 가능하다. 주어진 인덱스에 있는 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다. 배열은 선언할 때 배열의 크기를 지정해야 한다는 문제점을 가지고 있다. 처음 선언한 크기보다 더 많은 자료를 집어넣을 수 없다. 동적 배열 (Dynamic Array) 배열의 크기를 변경할 수 없다는 문제를 해결하기 위해 크기가 변경되는 '동적 배열'이 고안됐다. 배열의 특성을 그대로 이어받지만 추가.. 2023. 3. 16.
[Programmers] (Summer/Winter Coding(~2018)) Lv 2. 배달 https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr DFS(재귀)로 풀었지만, 32번 테스트가 시간 초과 실패. function solution(N, road, K) { const graph = road.reduce((obj, [p1, p2, t]) => { (obj[p1] = obj[p1] || {}), (obj[p2] = obj[p2] || {}); obj[p1][p2] = obj[p2][p1] = Math.min(obj[p1][p2] ? ob.. 2023. 3. 16.

티스토리툴바