연결리스트 연결리스트(Linked List)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 각 노드는 다음 노드를 가리키는 포인터를 포함한다. 연결리스트의 종류 단순(단방향) 연결리스트 단일 연결 리스트(Singly linked list)는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다. 이중(양방향) 연결리스트 단순 연결 리스트(Singly Linked List)는 next로 현재 노드에서 다음 노드로 갈 수 있지만 이전 노드로는 갈 수 없다. 이러한 단점을 해결하기 위해 노드에 앞 노드의 메모리 주소를 보관하는 포인터 prev를 만들어준 형태를 이중 연결 리스트(Doubly Linked List)라..
다이나믹 프로그래밍은 동적 계획법이라고도 부른다. 일반적인 프로그래밍 분야에서의 동적(Dynamic)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미하지만, 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어다. 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 바텀업)으로 구성된다. 탑다운 vs 바텀업 function fibonacci(n, dp) { if (n === 0) return 0; if (n === 1) return 1; if (dp[n] !== u..
문제 보기 DFS/BFS 문제는 지도 형식으로 주어진 문제만 풀어봐서 이 문제처럼 인접 리스트로 주어진 문제가 낯설었다. 이 문제를 기회로 인접 리스트에 대해서도 알게 되고 인접 행렬도 구현해 볼 수 있어서 아주 유익했다. DFS 풀이 /* 인접 행렬 이용한 방법 */ function solution(n, wires) { const graph = Array.from({length: n + 1}, () => Array(n + 1).fill(0)) const dfs = (arr, node) => { let res = 0 for (let i = 1; i { graph[wire[0]][wire[1]] = graph[wire[1]][wire[0]] = 1 }) // 와이어를 하나씩 끊고 끊어진 각 노드 2개에 ..
완전탐색: 말 그대로 가능한 모든 경우들을 탐색하는 방법. 완전탐색 기법 - 단순 Brute-Force - 비트마스크(Bitmask) - 재귀 함수 - 순열 (Permutation) - BFS / DFS 1. 단순 Brute-Force 어느 기법을 사용하지 않고 단순히 for문과 if문 등으로 모든 case들을 만들어 답을 구하는 방법이다. 이는 아주 기초적인 문제에서 주로 이용되거나, 전체 풀이의 일부분으로 이용하며, 따라서 당연히 대회나 코테에서는 이 방법만을 이용한 문제는 거의 나오지 않는다. 2. 비트마스크(Bitmask) 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식이다. 완전 탐색에서 비트마스크는 문제에서 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택..
BFS, DFS 두가지 모두 그래프를 탐색하는 방법입니다. 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다. DFS 깊이 우선 탐색 (Depth-First Search) 출처 https://developer-mac.tistory.com/64 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다. 예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 ..
스택/큐 스택과 큐는 추상적 자료구조(Abstract Data Type)에 속한다. 이것은 자료구조의 방법이 코드로 정의된 것이 아니라 그 구조의 행동 양식만 정의된 것을 말한다. 스택과 큐는 배열을 기반으로 어떤 규칙을 설정한 것이라 할 수 있다. 스택은 배열이 수직으로 쌓여있는 식이라고 생각하면 된다. 배열에 어떤 요소를 추가하거나 배열에서 어떤 요소를 제거할 때는 맨 위에서부터 한다. 후입선출(Last In, First Out) 구조라고 할 수 있다. 실생활의 예로는 웹페이지 뒤로가기 버튼을 누르는 것을 들 수 있다. 뒤로가기는 곧 히스토리 스택의 맨 위에서 한 페이지씩 가져가는 것이다. Ctrl + Z로 최근의 실행 작업을 되돌리는 것도 스택 자료구조이다. 큐는 말 그대로 줄서기를 생각하면 된다...
LeetCode: Greatest Common Divisor of Strings 문제 보기 1트 var gcdOfStrings = function(str1, str2) { /*함수 안의 새로운 함수 gcdGen이 있습니다. 이 함수는: 한쪽이 다른 한쪽에 전혀 포함되지 않으면 일단 빈 문자열을 리턴합니다. 그렇지 않으면 s1이 s2의 '배수'인지 확인하고(즉, s2를 여러번 더하면 s1이 되는지 확인하고) 맞다면 s2를 리턴, 아니라면 s1에서 s2를 제거하고 다시 s2와 gcdGen을 돌려 주는 재귀함수입니다. */ const gcdGen = function (s1, s2) { if(!s1.includes(s2) && !s2.includes(s1)) return '' return (s1.replaceA..
그리디 알고리즘 현재 상황에서 가장 좋아 보이는 것만 선택하기를 반복하는 방법. 부분의 최적 해가 전체의 최적 해에 가까워진다. 마지막에 최적의 해에 도달했는지 검토하고 최적의 해가 구해지지 않았다면 처음으로 돌아간다. 프로그래머스: 체육복 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr function solution(n, lost, reserve) { //양쪽에 있는 경우 let newLost = lost.filter((x) => !reserve.includes(x)); let newReserve = reserve.filter((x) => !lost.i..
