시나위

1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 요약 모든 컴퓨터를 연결하는데 필요한 최소 비용을 출력한다. 접근 1. BFS 최소 비용이면 BFS라고 생각할수 있겠지만 시작점에서 특정 지점까지의 최소 거리이므로 조건과 맞지않다. (몇몇 조건은 만족할수 있다.) 2. MST(Minimum Spanning Tree) 최소신장트리 사용된 간선들의 가중치 합이 최소인 트리이다. 신장트리를 만들때 최소의 간선을 사용해서 모든 노드를 방문해야 하고, 사이클을 만들지 않아야한다. Kruskal 낮은 비용의 간선부터 차례로 선택함 사이클이 생기는 간선은 제거함(cycle이 만들어지는지 확인 필요, ex. ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 1번 노드에서 가장 멀리 떨어진 노드 찾기 접근 1. 그래프 탐색 BFS로 탐색하면 1에서부터 각 노드마다의 거리가 나온다. 가장 마지막 구해진 거리(가장 먼 거리)와 같은 개수를 구하면 된다. max_dist = max(max_dist, visit[adj]); 모든 노드를 탐색할때 가장 큰 값을 저장해놓고 int ret = 0; for (auto v:visit) { if (v == max_dist) ret++; } return ret; 해당 값을 사용해서 같은 거리인 노드의 개수를 센다. 전체 코..

17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 요약 두칸짜리 파이프를 옮겨 (N,N) 위치까지 옮기는 방법의 개수 구하기 파이프는 세가지 방향으로만 움직일수 있음 접근 및 알고리즘 1. 메모리 제한이 512MB인거보면 DP다. 세가지 방향으로 움직일수 있는지 확인 (checkMove) Top Down 방식으로 해당 위치에 값이 있으면 값 리턴, 끝에 도착하면 1을 저장하고 리턴 전체 코드 #include #include #include using namespace std; #de..

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 요약 트리의 지름 출력 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것 접근 1. 생각의 흐름 그래프 탐색 두번으로 진행하면 될 것 같다. 아무 점에서 시작해서 가장 먼 지점까지 탐색한다. 첫번째 탐색이 끝나면 가장 먼지점에서 두번째 탐색을 시작한다. // 1. 아무 노드에서 시작해서 가장 먼노드까지 간 다음, pair tmp; tmp = bfs({1, 0}); // 2. 가장 먼노드 노드에서 가장 먼노드까지 탐색 tmp = bfs({t..

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 요약 진실을 모르는 파티의 최대 개수 출력 접근 1. union find union find로 풀어야될거같았다. 입력받을 때 같은 파티에 있는 사람들끼리 union 시킨다. for (size_t i = 1; i > length; party[i][0] = length; for (size_t j = 1; j > party[i][j]; if (j == 1) contin..

2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 요약 주어진 길이 N의 숫자에서 K개를 제거해서 가장 큰 수를 만들어야함 접근 1. 앞에 있을수록 9에 가까워야하고 뒤에 있을수록 0에 가까워야한다고 생각이 들었다. 하지만 K가 작으면 만들기기 어렵다고 생각이 들었다. 이쯤 도저히 머리가 안돌아가서 힌트를 봤다. 스택을 사용하라고 되어있어서 어떻게 풀어야할지 고민을 꽤 했다. 그러다가 갑자기 스택에 넣고 뺄때 비교하면 될거같다고 생각이 들었다. 스택의 최상위 값이랑 index 가 가리키는 값을 비교해서 최상위 값이 크거나 같을때까지 스택에서 pop하고, K 개의 원소를 뺄 때까지 계..

문제 요약 현재 탑의 크기보다 큰 탑 중 왼쪽으로 가장 가까운 탑찾기 접근 1. 생각의 흐름(Greedy) 출력 아무것도 없을때 0 값이 있으면 해당 인덱스 값 출력 -> (value, index ) 같이 넣어야할듯 저장한 값보다 값이 크면 큰값이 나올때까지 pop 저장한 값보다 값이 작으면 push 전체 코드 #include #include #define MAX_N 500000 using namespace std; int N; int arr[MAX_N]; int main() { cin >> N; for (size_t i = 0; i > arr[i]; stack s; // value, index for (size_t i = 0; i < N; i++) { if (s.empty()..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 알파벳 aeiou 로 만들어지는 단어에 대한 사전순 위치 구하기 접근 1. 완전탐색 생각없이 완전탐색으로 구현했다. 모든 값을 구해서 map에 저장한다. for문으로 구현하는데 실패해서 재귀함수를 사용했다. void make(int ind, string word) { if (ind == 6) { return; } if (word != "" && !dict.count(word)) { // dict[word] = index++; 아래 두줄을 하나로 합쳐도 된다. dict[word] = index; in..

2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 문제 요약 두 배열이 주어졌을때 각각의 배열로 만들수 있는 부배열의 합이 T가 되는 부배열쌍의 개수 구하기 접근 1. 생각의 흐름 각 배열의 부배열합을 구해서 저장해야한다. 원소가 1개인 것부터 모든 원소가 들어간 것 까지의 부배열을 만들고 그의 합을 저장했는데 누적합을 사용했다. void makeArr( vector& arr, vector& cumArr, int size ) { a..

1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 문제 요약 무한 수열 A의 N 번째 값 구하기 A0 = 1, Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1) (⌊x⌋는 x를 넘지 않는 가장 큰 정수이다.) 접근 1. 구현 주어진 조건에 대해 구현하기. N 에 대해서 구해야하므로 Top Down 방식이 나을듯 했다. 그리고 max(N) = 10^12 이므로 꽤 많은 연산이 있을 것이고 중복 되는 값이 있을 것이므로 Dynamic Programming으로 구현한다. DP을 위해 배열을 사용해서 메모리를 잡으면 공간복잡도는 O(N)이나 최대값이 4*10^12이므로 메모리 제한을 초과한다. -> 해시(unordered_map)를 사용해서 필요한 값만 저장..