이름 못 정한 블로그

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반..

https://www.acmicpc.net/problem/1992 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서..

문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. 제한사항 격자의 크기 m, n은 1 이상 100 ..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 문제 피리 부는 사나이 성우는 오늘도 피리를 분다. 성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다. 이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000) 둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다. 먼저 정점 번호가 주어..

가장 먼 노드를 찾기 위해서 BFS를 적용할 수도 있었는데 나는 다익스트라 알고리즘을 적용해서 풀었다. 다익스트라는 한 노드에서 각 노드에 대해 가장 짧은 경로를 찾아준다. 따라서 다익스트라 결과에서 가장 큰 값을 찾고 같은 값이 몇개인지만 찾으면 된다. #include #include #include #define INF 1000000 using namespace std; int map[20001][20001]; int dist[20001]; bool visit[20001]; void Dijkstra(int start, int n){ int cur, min, min_idx; for(int i = 1; i

한문제만 풀기 섭섭해서 한 문제 더 풀었다. 원래는 DP에 있는 N으로 표현 문제를 풀다가 너무 어려워서 이 문제로 도망쳤는데 오히려 아까 푼 문제보다 더 빨리 푼 듯하다. 푸는데 5분 정도 걸린거 같다. 레벨3 치고는 너무 쉽거나 내가 DP를 겁나 못하거나 둘 중 하나겠지. 처음엔 union-find로 풀까 하다가 단순히 DFS만 돌려도 될 것 같길래 이렇게 풀었다. 어느 한 노드에서 DFS를 시작해서 끝났는데도 아직 방문하지 않은 노드는 다른 네트워크다. 따라서 모든 노드를 방문할 때까지 DFS를 돌리면 그 횟수가 네트워크의 개수가 된다. #include #include using namespace std; int visit[201] = { 0, }; void DFS(int cur, int n, ve..

백준만 풀기 섭섭해서 프로그래머스도 한문제 풀어봤다. 날먹하려고 가장 만만한 브루트포스로 풀었다. 근데 벡터 사용이 어색해서 좀 버벅였다...ㅋ 문제 자체는 아주 쉬웠다. #include #include using namespace std; vector solution(vector answers) { vector answer; int score[3] = {0, }; int idx[3] = {0, }; const int giver1[5] = {1, 2, 3, 4, 5}; const int giver2[8] = {2, 1, 2, 3, 2, 4, 2, 5}; const int giver3[10] = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; for(int i = 0; i < answers.siz..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net TSP 문제는 학교에서 배웠지만 실제로는 처음 풀어본다. hueristic 알고리즘으로 NN(Nearest Neighbor)도 배웠던 기억이 있다. 시작점에 대해서 고민해봤는데 어차피 circuit이 생기니까 어디서 시작하는지는 중요하지 않았다...ㅋ 입력을 보니 Floyd가 생각나서 이걸 쓸 수 있을까도 생각해봤지만 이 문제랑 관련은 1도 없었다. 고민해보다..

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 재귀함수와 DP를 이용하는 문제 왼발이랑 오른발이 따로 움직여서 처음엔 뭔가 싶었다. i번째에 왼발 오른발이 어디에 있는지 저장해서 풀 수 있었다. 그때 들이는 가장 적은 힘을 배열에 저장해뒀다. #define _CRT_SECURE_NO_WARNINGS #include int i; int order[100001]; int power[100001][5][5]; in..