빅맥좋아요

https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 백준 16118번 달빛 여우 문제를 풀었다. 시작 노드에서 다른 노드까지의 최단 비용을 구하고, 간선의 가중치가 양수라서 다익스트라를 사용했다. 여우는 모든 노드를 같은 속도로 이동한다. 늑대는 2배 빠르게 이동했다가 1/2배 느리게 이동하는 것을 반복한다. 여우의 속도를 2로 두고 늑대가 빠르게 이동할 때는 1, 느리게 이동할 때는 4의 ..

https://www.acmicpc.net/problem/1486 1486번: 등산 첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000 www.acmicpc.net 백준 1486번 등산 문제를 풀었다. 특정 노드에서 특정 노드까지의 최단 거리를 구하고, 간선의 가중치가 양수여서 다익스트라를 사용했다. 이 문제의 경우 가장 높은 산을 갔다가 다시 호텔로 돌아와야 하므로 호텔 -> 산 -> 호텔 이런 식으로 하나의 산에 대해 다익스트라를 두 번 실행하면 된다. 실제로는 호텔 -> 산 다익스트라는 한 번 실행하면 모두 구할 수 있고, 산 -> 호텔..

https://www.acmicpc.net/problem/1584 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 백준 1584번 게임 문제를 풀었다. 게임에는 안전한 구역, 위험한 구역, 죽음의 구역 총 세 개의 구역이 있다. 생명력을 비용으로 생각하면 안전한 구역은 이동 비용이 0인 구역이다. 위험한 구역은 이동 비용이 1인 구역이다. 죽음의 구역엔 들어갈 수 없다. 이렇게 비용이 0과 1로 이루어졌을 때 0-1 BFS를 deque와 함께 사용할 수 있다. 다음에 이동할 구역이 방문한..

https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 백준 10423번 전기가 부족해 문제를 풀었다. 최소 비용으로 연결하는 문제라서 크루스칼 알고리즘을 사용했다. plant 배열은 발전소 도시의 숫자를 저장한다. city 배열은 도시의 숫자와 전기가 공급됐는지 체크해주는 변수를 저장한다. graph 배열은 BFS 탐색용이다. 우선순위 큐와 parent 배열은 크루스칼 알고리즘용이다. 먼저 입력을 받으면서 ..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 백준 12100번 2048 (Easy) 문제를 풀었다. 처음에 백트래킹으로 구현을 했는데 promising한 조건을 정하지 못해서 그냥 구현 문제를 푸는 것 처럼 됐다. Move함수는 입력받은 좌표와 방향으로 숫자를 옮긴다. 재귀적으로 구현을 했다. 왼쪽으로 Move한다면 1. 입력받은 좌표의 숫자가 0인지 체크한다. 1.1 입력받은 좌표의 숫자가 0일 때, 1.1.1..

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 백준 1162번 도로포장 문제를 풀었다. 간선의 가중치가 모두 양수이고 특정 노드까지의 최단 비용을 구하는 문제라서 다익스트라를 사용해야겠다고 생각했다. 기본적인 다익스트라 문제에서 추가된 것은 도로가 포장될 수 있다는 점이다. 따라서 노드 구조체에 포장된 도로의 개수를 저장하는 paved 변수를 추가해서 사용했다. dist[i][j] 배열은 포장된 도로의 개수..

서버는 aws ec2, 데이터베이스는 aws rds를 사용했다. 둘 다 프리티어로 사용했다. 사용자가 입력한 질문과 데이터베이스에 있는 질문들의 유사도를 측정한 뒤, 사용자의 질문과 비슷한 질문들을 출력해주는 기능을 만들고 싶었다. 추천 시스템과 비슷하게 모든 문서의 tf-idf를 구한 후 코사인 유사도 검사를 하면 될 것 같아서 그대로 진행했다. 우선 비교 데이터로 사용하기 위해 OKKY라는 사이트의 Q&A게시판을 크롤링했다. 10000개 게시글의 질문과 내용을 크롤링해서 csv파일로 만든 후 데이터베이스에 넣어두었다. 테이블의 칼럼은 bid, title, content 로 만들었다. 그 다음 데이터베이스에 있는 데이터들을 사용하기 위해서 지난 번에 만들어둔 tf-idf-test 모듈을 최적화한 후에 ..

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 백준 1719번 택배 문제를 풀었다. 간선의 가중치가 양수이고 최단 경로를 찾는 문제라서 다익스트라를 사용했다. path 배열은 다익스트라를 수행할 때 이전 노드를 저장하는 배열이다. 예를 들어 1번 노드에서 다익스트라를 수행하면 path배열은 아래와 같이 저장된다. index 1 2 3 4 5 6 value 0 1 1 3 2 5 이 path 배열을 다르게 보면, index 노드로부터 1번 노드로 가기 위..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 백준 16236번 아기 상어 문제를 풀었다. 상어가 먹이를 찾는 부분은 BFS로 풀었다. 내가 사용한 변수는 아래와 같다. map배열 : 물고기와 아기상어의 위치를 저장 visited 배열 : BFS에서 방문했던 곳을 체크하는 용도 dist 배열 : BFS에서 좌표별로 아기 상어가 움직인 거리를 저장 Fish 구조체 : 물고기의 좌표와 거리를 저장 eatableFish 우선순위큐 : 먹을 ..

문서 유사도 검사를 위해 필요한 TF-IDF나 코사인 유사도 모듈을 찾아봤다. https://www.npmjs.com/ 위의 npm search 사이트에서 노드서버에서 사용할 모듈들을 찾아 봤지만 내가 원하는 입력에 원하는 출력을 해주는 모듈이 없었다. 그래서 간단한 자연어 처리 모듈을 직접 만들기로 했다. 형태소 분석기는 mecab-ya 라이브러리를 사용했다. 2022.06.25 - [JavaScript/자연어 처리] - [node.js] 형태소 분석기 mecab 사용하기 1. TF-IDF 아래 두 개의 사이트에서 TF-IDF에 관한 자세한 설명을 얻었다. https://wikidocs.net/31698 http://bigdata.dongguk.ac.kr/lectures/TextMining/_book/..