알고리즘

1. 정의 우선 DFS와 BFS의 정의부터 간략하게 다시 알고 가도록 하자. DFS 깊이 우선 탐색이라는 이름에 맞게 탐색할 노드를 깊이를 우선으로 탐색하는 알고리즘이다. DFS의 구현은 Stack 또는 재귀적인 특징을 이용해 구현한다. BFS 너비 우선 탐색은 넓게 바로 아래 하위 노드를 모두 넓게 탐색한 뒤 그 아래의 노드들을 탐색하는 알고리즘이다. 큐를 이용해 탐색을 관리한다. 2. 구분 방법 그렇다면, 실제 코테나 문제를 해결할 때 무엇을 언제 사용해야하나? 우선 그 문제를 분석해봐야한다. 그래프 탐색에서 모든 정점을 방문하는가? DFS와 BFS 둘 다 가능하다. 경로의 특징을 저장 혹은 조합, 순열을 구해야 하는 문제인가? 고로타면 DFS를 이용하는게 유리하다. 최단 경로, 최단 거리를 구해야 ..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 이번 문제는 큐를 이어붙여 투포인터 알고리즘을 이용해 풀었다. 시작포인터와 끝 포인터는 각각 0과 첫번째 큐의 끝으로 설정해 두었다. 그 이유는 한개의 큐의 합이 전체 큐의 합의 절반이 되는 것을 감지해야하기 때문에 첫번째 큐의 합을 기준으로 크다면 lp에 해당하는 수를 빼고, 작다면 rp에 해당하는 수를 더해주면서 문제를 풀었다. 코드 const solution = (qu..

슬라이딩 윈도우(Sliding Window) 알고리즘 고정된 윈도우(특정 범위를 나타내는 말)의 내부 요소값을 이용하여 문제를 풀이하는 알고리즘 위의 사진에서는 윈도우의 범위가 5이다. 첫번째는 1, 3, 2, 6, -1 이 윈도우 내에 있고 두번째에는 3, 2, 6, -1, 4 가 윈도우 내에 존재한다. 첫번째에서 두번째로 넘어갈 때, 맨 앞에 위치한 1은 윈도우 내에서 제거되고, 1을 제외한 3, 2, 6, -1 은 재사용되며 그 뒤로 새로운 요소인 4가 추가가 된다. 슬라이딩 윈도우 알고리즘는 재사용이 중요하다고 생각한다. 고정된 범위를 가지고 움직이는 윈도우 내에 있는 요소들을 움직이는 만큼 앞에 있는 요소를 제거하고 나머지 값은 재사용하며 그 뒤에 새로운 값들을 배정해 사용한다. 시간복잡도 : ..

동적 계획법의 배경 피보나치 수열 동적 계획법의 등장 배경에는 피보나치 수열이 있다. 피보나치 수열은 제2항까지는 1, 3항부터는 앞의 두 항을 더한 수로 저의 된다. 제 0항은 생략되기도 한다. (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89... 프로그래밍에서 피보나치 수열은 보통 재귀를 통해 표현이 가능하다. 피보나치 수열을 함수로 구현해 보자. const fibo = (n) => { if (n { if (n { if (n { fiboData[0] = 0; fiboData[1] = 1; for (let i = 2; i

자료구조란? 🔰자료구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것이다. 데이터(data)는? 1️⃣ 데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다. ◾이름, 나이, 키, 등 데이터로 분류가 가능하다. 2️⃣ 데이터는 그 자체만으로 어떤 정보를 가지기 힘들다. ◾나이라는 데이터를 갖고있으면, 사람의 나이인지 동물의 나이인지 알 정보가 없다. 3️⃣ 데이터는 분석하고 정리하여 활용해야만 의미를 갖는다. ◾분석, 정리, 활용 4️⃣ 데이터는 사용하려는 목적에 따라 형태를 구분하고, 분류하여 사용한다. 5️⃣ 필요에 따라 데이터의 특징을 잘 파악(분석)하여 정리하고, 활용해야 한다. 데이터를 체계적으로 정리하여 저장하면 데이터 활용에 있어 훨씬 유리하다. ..