본문 바로가기

공부/알고리즘37

이분 탐색 문제 풀어보기 빈말로라도 알고리즘 문제를 잘 풀진 못하지만(...) 특히나 잘 접하지 않았던 유형의 문제들을 풀어보고자 과거에 풀었던 문제들을 돌아보던 중, 이분 탐색 문제를 엄청나게 안 풀어봤다는 것을 깨달았다.개념적으로는 이분 탐색이 어떤 것인지 알고 있지만, 알고리즘 문제 풀이에 대해서는 확실히 익숙하지 않다는 느낌이 들어, 이분 탐색 문제를 풀고 문제 유형에 익숙해지고자 글을 남기기로 했다.이분 탐색 문제이분 탐색 형식의 풀이를 요구하는 알고리즘 문제들은 주로 방대한 범위의 수에서 특정 조건을 만족하는 값을 찾는 문제에서 많이 쓰이는 듯 하다.이분 탐색의 이론은, 정렬된 배열 혹은 리스트 내에서 탐색 범위(인덱스)를 절반으로 나누어 가며 탐색 대상의 범위를 좁혀나가는 것이다.이를 알고리즘 문제 풀이에 대입하면,.. 2024. 12. 13.
프로그래머스 단어 변환 풀이 지난 글에서 프로그래머스 문제도 많이 풀어봐야 겠다고 다짐했었는데, 오늘에서야 건드려보기 시작했다(^^...문제 풀이 - 프로그래머스 단어 변환  DFS/BFS 문제. 단어 배열이 주어지고 시작 단어와 타겟 단어가 주어지면 시작 단어를 단어 배열 내에 주어진 단어로 차례차례 바꿔가며 타겟 단어를 만드는 것이 문제의 목표이다. 문제에서 주어지는 조건은 다음과 같다. 시작 단어에서 시작하여 주어진 단어 배열 내의 단어로 단어를 바꿔가며 타겟 단어를 만들어야 한다.이 때, 글자를 한 글자만 바꿀 수 있다. 즉 다음 단어로 고를 수 있는 단어는 바꾸기 전 단어와 '딱 한 글자만 차이나는 단어'이다.ex) lot에서 get(2글자가 차이난다)으로의 변환은 불가능하지만, let으로의 변환은 가능하다.변환을 완료하였.. 2024. 11. 24.
백준 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.

티스토리툴바