본문 바로가기

자바스크립트18

이분 탐색 문제 풀어보기 빈말로라도 알고리즘 문제를 잘 풀진 못하지만(...) 특히나 잘 접하지 않았던 유형의 문제들을 풀어보고자 과거에 풀었던 문제들을 돌아보던 중, 이분 탐색 문제를 엄청나게 안 풀어봤다는 것을 깨달았다.개념적으로는 이분 탐색이 어떤 것인지 알고 있지만, 알고리즘 문제 풀이에 대해서는 확실히 익숙하지 않다는 느낌이 들어, 이분 탐색 문제를 풀고 문제 유형에 익숙해지고자 글을 남기기로 했다.이분 탐색 문제이분 탐색 형식의 풀이를 요구하는 알고리즘 문제들은 주로 방대한 범위의 수에서 특정 조건을 만족하는 값을 찾는 문제에서 많이 쓰이는 듯 하다.이분 탐색의 이론은, 정렬된 배열 혹은 리스트 내에서 탐색 범위(인덱스)를 절반으로 나누어 가며 탐색 대상의 범위를 좁혀나가는 것이다.이를 알고리즘 문제 풀이에 대입하면,.. 2024. 12. 13.
함수형 자바스크립트 훑어보기 함수형 프로그래밍이 정확히 어떤 것일까 했는데, 자세히 공부하려고 사놨던 책(함수형 자바스크립트)을 이제서야 읽어보기 시작했다(ㅎㅎ).이전의 내 짧은 지식으로는 함수를 위주로 구성하는 프로그래밍(?) 정도의 얕팍한 이해 정도만 하고 있었는데, 1장을 읽어보며 조금의 이해를 쌓아보기로.함수형 프로그래밍이 무엇인가요?말 그대로 ‘함수의 사용을 강조하는 프로그래밍 스타일’이다.다만, 단순히 ‘함수를 사용하자’는 것은 아니고 고려하고 반영해야 하는 원칙이 존재한다. 함수형 프로그래밍의 원칙부수 효과 (Side Effect)를 방지한다.상태 변이를 줄이기 위해 데이터의 제어 흐름 및 연산을 추상화한다.⇒ 이 원칙을 준수하기 위해 ‘재사용성 & 신뢰성(Reliability)’을 고려하여, 가능한 작게 기능을 나눈.. 2024. 11. 26.
백준 17837번 새로운 게임 2 풀이 solved.ac 의 그래프를 간만에 보니 시뮬레이션이나 구현 쪽 문제를 많이 안 풀어본 것 같길래? 간만에 알고리즘 문제 풀이를 재개했다.문제 풀이 - 백준 17837번 새로운 게임 2  구현/시뮬레이션 문제로, 주어진 룰에 맞춰 게임을 진행한 후, 게임 종료 조건을 만족하는 턴이 언제인지를 구하는 문제이다. 조건은 아래와 같다.N x N 체스판이 주어진다. 이 체스판은 각 칸이 흰색(0), 빨간색(1), 파란색(2)중 한 색으로 칠해져있다.1번부터 K번 까지의 말이 존재하고, 이 말은 각각 진행할 수 있는 방향이 정해져있다.체스판 한 칸 위에 복수의 말이 존재할 수 있다. 이 때, 말을 아래에서 위로 차례로 쌓는다.1번부터 K번 까지의 말은 순서대로 자신의 정해진 방향에 따라 한 칸씩 이동하는데, 이.. 2024. 11. 17.
비트마스킹 간단 정리하기 지난 게시글에서도 언급했지만, 비트마스킹을 개념적으로는 알고 있는데 아직 활용 예나 실 구현에서 망설이고 헷갈리는 모습을 보이길래 한 번 정리해두면 좋겠다는 생각이 들었다.자바스크립트 기준으로 비트마스킹에 대해 정리하고, 나중에 참고할 수 있도록 자주 사용되는 일례를 기록해두기로.비트마스킹이란? 데이터를 비트, 즉 2진수의 형태로 표현하는 것을 의미한다.집합이나 배열, 부분집합 등을 표현할 때 활용할 수 있다.ex) 5개의 원소를 갖는 집합의 부분집합은 아래와 같이 표현할 수 있다.const arr = [1, 2, 3, 4, 5];/* {1, 3, 5} 를 원소로 갖는 부분 집합 -> 10101 {2} 를 원소로 갖는 부분 집합 -> 10000*/  왜 사용할까?빠르다. 기본적으로 비트 연산을 수행하기 .. 2024. 11. 11.
외판원 순환 문제 알아보기 몇 달 내려놓았던 알고리즘을 다시 풀고자 문제를 찾아보던 중 처음 보는 문제를 접하게 되었다.외판원 순환 문제라는 것인데, 문제를 풀고 이해한 것을 남겨보고자 한다.외판원 순환 문제(Traveling Salesman Problem - TSP)란?  여러 도시와 도시 사이의 이동 비용이 주어질 때, 어느 한 도시에서 시작하여 모든 도시를 순회한 후 처음 시작점이 되는 도시로 돌아올 때까지 걸리는 최소 비용을 구하는 문제이다.  외판원 문제 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전.ko.wikipedia.org  해결 방법에 대한 고민  처음 문제를 딱 봤을 때 떠오른 점을 나열하자면 아래와 같다.도시와 도시 사이의 이동 비용이 주어진다.도시가 노드, 도시 사이의 이동 비용이 가중.. 2024. 11. 10.
위상 정렬 알아보기 위상 정렬(Topological Sorting)이란?방향 그래프의 정점들을 방향을 거스르지 않도록 나열하는 것.각 정점에 순서를 매기고, 그 순서를 거스르지 않도록 정점들을 정렬하는 것을 의미한다. ex) 선수 과목 구조(과목마다 먼저 들어야 하는 과목의 순서가 정해져 있음)여기서 순서란, 그래프의 정점 순서를 가리킴.ex) 정점 v1과 v2이 v1 → v2 방향으로 연결되어 있으면, v1이 선행된다고 본다.위상 정렬에 사용될 그래프는 순환이 없어야 함(비순환 방향 그래프여야 함). 알고리즘Kahn 알고리즘자신을 향하는 간선(즉, 자신으로 들어오는 간선)이 없는 정점을 찾는다.이러한 정점이 여러 개라면, 그 중 아무거나 한 개를 고른다.해당 정점을 그래프에서 제거한다.남은 그래프에서 정점이 더 이상 존재.. 2024. 8. 31.

티스토리툴바