DOTY

1753번: 최단경로 (acmicpc.net) 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라 알고리즘을 사용했다. #include using namespace std; int vertex[20001]; // 정점으로 부터의 길이 int dij[20001]; int INF = 999999; int main(void) { fill_n(dij, 20001, 11); fill_n(vertex, 20001, 999999); vector dij(20001); int V,..

BFS의 응용버전 (BFS와 다이나믹이 합친 느낌이랄까..) 최단 거리를 찾는 알고리즘이다. 하나의 정점에서 모든 점으로 가는 최단 경로로 못 가는 경우에는 무한대로 끝난다. 필기로 정리한 것 또 쓰기가.. ㅎㅎㅎㅎㅎㅎ

1012번: 유기농 배추 (acmicpc.net) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 초기화 하는 방법을 헷갈려서 헤맨 문제 #include using namespace std; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int check[51][51]; int cab[51][51]; void cabbage(int x, int y) { int pos_x = x; int pos_y = y; queue position; position.push(make_pair(..

1874번: 스택 수열 (acmicpc.net) 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 2년 전에 풀었지만 왜인지 계속 시간 초과만 뜨던 문제. 생각보다 해결법은 간단했다. #include using namespace std; int main(void) { int num; int j = 0; int arr[100001] = {0, }; cin >> num; vector answer; stack s; for(int i =..

4949번: 균형잡힌 세상 (acmicpc.net) 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 작은 실수 하나 때문에 고민한 문제 방법은 여는 괄호는 스택에 넣고 닫는 괄호는 스택 top과 비교하여 괄호가 일치하면 pop 다르면 break. #include using namespace std; int main(void) { stack cover; while(1) { bool check = false; while(!cover.empty()) { cover.pop(); } string ..

www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 요즘 다른 공부를 좀 하고 있어서 코딩은 잘 안하는거 같다... ㅠㅠㅠ 틈틈히 해야하는데 ㅠ #include using namespace std; int memoi[1001] = {0, }; int cards[1001] = {0, }; int dp(int x) { memoi[1] = cards[1]; if(x == 1) { return memoi[1]; } for(int i = 2; i > n; for(int i = ..

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 뭔가 될거 같은데 안된 문제. 개인적으로 답답- 했던 문제. #include using namespace std; int main(void) { int num[100001] = {0, }; int high[100001] = {0, }; int N; cin >> N; int Max = -1000; for(int i = 1; i > num[i]; } int sum = 0; for(int i = 1; i

www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 예전에 한번 시도했다가 호되게 당하고 결국 이번에 풀어낸 문제. ㅎㅎㅎㅎㅎㅎㅎㅎㅎ #include #include using namespace std; int map[501][501] = {0, }; int memo[501][501] = {0, }; int Max = 0; void dp(int cnt){ for(int j = cnt; j > 0; j--){ for(int i = 0; i memo[j][i+1]) { memo[j-1..

www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 그동안 거의 웹만 했음...ㅎㅎㅎ...... 앞으로 자주 올...(크흠..)려야지 ㅎㅎㅎㅎㅎ #include using namespace std; int main(void) { int N; cin >> N; int stair[300] = {0, }; for(int i = 0; i > stair[i]; } int max_stair[300] = {0, }; max_stair[0] = stair[0..

www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 그냥 머리 가는대로 구하면 시간초과가 걸린다. 어떻게 해야할까....? #include using namespace std; int zero[41] = {1, 0, 1, 1, 0, }; int one[41] = {0, 1, 1, 0, }; int fibonacci_zero(int n) { if(zero[n] == 0 && n > 3) { zero[n] = fibonacci_zero(n-1) + fibonacci_zero(n-2); } return zero[n]; } int fibonacci_one(int n..