컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 알고리즘 dfs를 이용해 자리를 바꿔보고 K번 만큼 바꾼 후 가장 큰 값을 출력한다. 이 때 같은 수가 나올 수 있으므로 visited배열을 이용해 중복되는 값은 배제한다. 소스 코드 #include using namespace std; bool check[1000001][11]; string str; int m; int result = 0; void dfs(int K){ if(str[0] == '0') return; if(K == 0){ result = ..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 문제 해결 알고리즘 최댓값을 찾는 세그먼트 트리와 최솟값을 찾는 세그먼트 트리를 각각 만들어 범위내 최댓값 최솟값을 출력해준다. 소스 코드 #include using namespace std; const int MAX = 100001; int arr[MAX], minTree[4*MAX], maxTree[4*MAX]; int maxinit(int start, i..

https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 문제 해결 알고리즘 최솟값이 있는 인덱스를 계속 업데이트해주는 세그먼트 트리를 이용해 풀 수 있는 문제 소스 코드 #include #define ll long long int using namespace std; #define MAX 100001 int N; ll arr[MAX], tree[4*MAX]; int minIndex(int x, i..

https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제 해결 알고리즘 최소 스패닝 트리를 구하는 문제이다. 크루스칼 알고리즘으로 문제를 풀었다. https://kimmessi.tistory.com/74?category=871925 [알고리즘] 그리디 알고리즘 - 최소비용신장트리, 스케줄 짜기 탐욕 알고리즘이란? 작은 사례로 나누지 않고 탐욕스러운 선택을 sequence로 계속하면 답에 가까워진다. 선택과정(selection procedure) : 집합에 추..

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 문제 해결 알고리즘 위상 정렬문제인데 인접리스트를 이중배열로 구현해야한다는 점과 "?"과 "impossible"을 구분해주어야하는 점이 어려웠다. (두 팀의 순서를 바꿀 때 좀 복잡하기 때문에 이중배열이 더 편했다.) q에 원소가 2개 이상이면 "?"를 출력해주고 q에 원소가 없고 방문하지 않은 노드가 있다면 "impossible"을 출력해준다. 2개 이상도 아니고 모든 노드를 방문했다면 ..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 해결 알고리즘 다익스트라 + 경로 출력해줘야하는 문제. 다익스트라 알고리즘에서 더 값이 적은 경로가 나왔을 때, 해당 위치가 어떤 위치에서 왔는지 기록하는 배열을 만들어서 추적했다. 아래의 링크에 다익스트라 알고리즘에 대한 설명되어있다. https://kimmessi.tistory.com/185?category=871925 [알고리즘] 다익스트라 - 선형 탐색..

https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 문제 해결 알고리즘 전형적인 다익스트라 문제이다. 아래 링크에 다익스트라 알고리즘에 대한 설명이 나와있다. https://kimmessi.tistory.com/185?category=871925 [알고리즘] 다익스트라 - 선형 탐색, 우선순위 큐 다익스트라 알고리즘 (Dijkstra's algorithm) 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘 다익스트라 알고리즘은 음의..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 문제 해결 알고리즘 문제에 나온 조건을 응용한 다익스트라 알고리즘 문제이다. 아래의 링크에 다익스트라 알고리즘에 대해 설명되어있다. https://kimmessi.tistory.com/185?category=871925 [알고리즘] 다익스트라 - 선형 탐색, 우선순위 큐 다익스트라 알고리즘 (Dijkstra's algorithm) 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 구해주는 알고..

골드 1에서 9개월 정도 걸려서 겨우 플레 찍었네요 ㅠㅠ