빅맥좋아요

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 백준 1766번 문제집 문제를 풀었다. 위상 정렬 문제를 처음 풀어봤다. 이 문제 처럼 순서가 정해져 있는 작업을 수행할 때 그 순서를 결정해주는 알고리즘이라고 한다. 아래의 블로그를 참고했다. https://yoongrammer.tistory.com/86 adjList 배열은 인접리스트를 저장하는 배열이다. in_degree 배열은 본인에게 들어오는 화살표의 개수를..

졸업 프로젝트를 진행하면서 자연어 처리를 해야할 일이 생겼다. 자연어 처리의 첫 단계가 형태소 분석기를 사용해서 문서를 형태소로 나누는 것이다. 1. 형태소란 ? 먼저 형태소에 대해 조금 알아보자면 형태소의 사전적 정의는 '의미를 가지는 요소로서는 더 이상 분석할 수 없는 가장 작은 말의 단위' 이다. 예를 들어, '아버지가방에들어가신다' 라는 문장을 형태소로 나눠보면 ['아버지', '가', '방', '에', '들어가', '신다'] 이런 식으로 나올 것이다. 명사, 동사, 조사, 접두어 등으로 문장을 나눈 다음 본인이 원하는 과정을 처리를 하면 된다. 2. 사용할 라이브러리 서버에서 사용할 예정이라 최대한 빠르고 가벼운 라이브러리를 선택하고 싶었다. 형태소 분석기를 간단하게 비교한 블로그가 있어서 그 글..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 백준 9466번 텀 프로젝트를 풀었다. 처음엔 단순하게 모든 학생들을 순회하면서 DFS를 실행하고 싸이클이 존재할 때 카운트를 세는 방식을 사용했는데 시간 초과가 나왔다. 고민을 하다가 구글에 검색해서 문제 풀이를 찾아봤는데 visited 배열 말고도 done 배열을 같이 사용하는 것을 확인했다. https://wooono.tistory.com/409 위의 블로그를 참고해서 문제를 풀었다. 배열의 설명..

https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 www.acmicpc.net 백준 1738번 골목길 문제를 풀었다. 특정 노드에서 특정 노드로 감 && 간선에 음의 가중치가 있음 -> 벨만 포드로 풀어야 겠다고 생각했다. 문제의 입력에서 cost에 -를 붙여서 음의 사이클 문제로 바꿨다. 문제를 풀기 위해 어떤 경우에 -1을 출력하고 어떤 경우에 경로를 출력하는지 생각해봤다. 1. 출발지점(1)에서 도착지점(n)까지 도달하는 경로가 없을 때 -> -..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 백준 5014번 스타트링크를 풀었다. 이동하는 비용이 버튼을 누르는 횟수이므로 위로 가나 아래로 가나 비용이 똑같다. 그래서 BFS를 사용해서 풀었다. map[i] 배열에는 i번째 층까지 가는데 드는 최소 비용을 저장한다. visited[i] 배열은 i번째 층에 온 적이 있는지 확인하는 용도이다. 아래는 전체 코드입니다. #include #include #include using namespace std; #..

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 백준 17472번 다리 만들기 2 를 풀었다. 문제에서 모든 섬을 연결하는 최소 비용을 구하라고 해서 최소 스패닝 트리로 풀어야 겠다고 생각했다. 문제를 풀기 전에 아래와 같이 생각하고 구현을 시작했다. 1. 섬에 번호를 매긴다. 2. 섬과 섬 사이에 놓을 수 있는 다리를 찾는다. 3. 크루스칼 알고리즘으로 최소 비용을 찾는다. 먼저 섬을 입력받은 후 섬마다 번호를 매겼다. ..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 백준 1937번 욕심쟁이 판다를 풀었다. 단순한 BFS/DFS 풀어보려 했는데 노드의 최대 개수인 250,000번을 수행해야 하므로 다른 방법을 사용해야 한다. 2차원 DP 배열과 DFS를 사용해서 풀었다. DP[i][j] 의 값은 판다가 (i, j) 좌표에 놓여졌을 때 살 수 있는 최대 일 수 이다. 어느 좌표에 놓이든 하루는 살 수 있으므로 DFS실행 시 해당 좌표의 DP값은 1로 ..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 백준 1167번 트리의 지름을 풀었다. 다익스트라를 두 번 사용해서 문제를 풀었다. 편의상 첫 번째 다익스트라는 1번 노드에서 시작하는 것으로 설정했다. 첫 번째 다익스트라를 실행하고 나면 1번 노드에서 가장 멀리 있는 노드를 리턴 값으로 넘겨주게 된다. 리턴되는 노드에서 다시 다익스트라를 실행하면 다시 그 노드로부터 가장 멀리 있는 노드를 넘겨준다. 넘겨준 노드와의 거리가 트리의..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 백준 9370번 미확인 도착지를 풀었다. 주어진 시작점에서 g->h 로 거쳐가거나 h->g 를 거쳐서 가는 루트가 도착 지점까지 최단 경로로 가는 루트인 도착 지점을 구하면 된다. s->g->h->d 또는 s->h->g->d 경로의 길이가 s->d인 경로의 길이와 같은 경우를 구하는 것이다. Dist배열을 3개 사용해서 다익스트라를 3번 수행했다. Dist_S[x] 의 값 = 시작점에서 x까..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 백준 16234번 인구 이동을 풀었다. BFS에 구현을 섞은 문제인 것 같다. 1. N * N 좌표 상의 모든 점을 순회하면서 BFS를 돌린다. 2. 인구 이동이 일어났으면 변경된 map을 저장하고 1번으로, 인구 이동이 일어나지 않았으면 count를 출력하고 끝낸다. BFS를 돌릴 때 방문했던 점은 다시 방문하지 않는다. BFS코드에서 next좌표가 유효한 값일 때 cur좌표와의 ..