스택의 기본적인 연산 5가지인 push,pop,top,empty,size를 구현하는 문제이다. 별다른 풀이 전략이 필요하지 않다, 그냥 구현만 해내면 그만인 문제이다 스택을 클래스나 구조체로 만들려고 했으나, 굳이 그렇게 할 필요까진 없어 보여 배열과 위치를 갖은 변수하나로 구성하였다. 앞으로 자주 사용된다면 클래스화하여 작성할 예정이다. 참고로, 온라인저지는 컴파일 옵션에 -DONLINE_JUDGE 가 들어가기 때문에 이것을 활용해 예시문을 테스트하는 것을 간편히 만들 수 있다. freopen()을 이용해 인풋과 아웃풋의 스트림을 컴파일 옵션에 따라 바꾼다. ...
큐를 구현하는 문제이다. push,pop,empty,size,front,back 함수를 구현해야 한다. 배열을 이용해 구현하였다. 고려해야 할 것은 앞과 끝을 가르키는 위치를 갖고 있어야 된다는 정도이다. 정해진 배열의 크기에서 큐가 원형으로 자라나고 줄어들게 만들었다. ...
RGB 색상별로 가중치가 주어질 때, 가장 값이 낮게 집을 칠하는 문제입니다. 전략 : 특별한 전략은 필요 없네요. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include <stdio.h> #include <string.h> using namespace std; int dp[1000][3]; int main(void) { memset(dp, -1, 0); int n; int t; int min = 100000; #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif scanf("%d", &t); for (int i = 0; i < t; i++) { scanf("%d %d %d", &dp[i][0], &dp[i][1], &dp[i][2]); } for (int i = 0; i < t; i++) { dp[i + 1][0] = dp[i+1][0] + (dp[i][1] < dp[i][2] ? dp[i][1] : dp[i][2]); dp[i + 1][1] = dp[i+1][1] + (dp[i][0] < dp[i][2] ? dp[i][0] : dp[i][2]); dp[i + 1][2] = dp[i+1][2] + (dp[i][0] < dp[i][1] ? dp[i][0] : dp[i][1]); } for (int i = 0; i < 3; i++) { if (dp[t - 1][i] < min) min = dp[t - 1][i]; } printf("%d\n", min); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }
트리의 지름은 두 vertex간의 길이가 가장 긴 값입니다. 이 문제에서는 간선에 가중치가 있기 때문에 멀어도 길이가 짧은 수 있고 그 반대가 될 수도 있습니다. 트리의 지름을 구하는 방법은 ...
연결된 두 vertex의 정보가 주어질 때 각 노드의 부모를 찾아서 2번부터 출력해주는 문제입니다. 처음에 접근할때는 행렬로 풀려고 했는데, 다익스트라 알고리즘 공부하면서 인정리스트의 장점을 실감하게 되어서 vector를 사용해 인정리스트를 만들었고, 큐를 사용해 BFS로 풀었습니다. 재귀함수를 이용해 DFS로 풀 수도있겠지만 뭔가 함수를 계속 호출하는건 성능에 안좋을꺼같아 BFS로 풀었습니다. ...
다익스트라 알고리즘을 공부하기 위해서 풀어본 문제입니다.. 어렵네요 어려웠어요 휴.. 구현할때 주의하실 점은 인접리스트랑 우선순위큐 꼭 쓰세요! 노드의 갯수가 커지면 인접행렬의 경우 메모리엄청 잡아 먹고 순회하는데 시간이 많이 걸립니다! ...
이번 문제에서는 스택을 클래스로 만들어 사용했다. 1n까지의 수로 이루어진 수열을 스택을 이용해 재현해내는 문제이다. push를 할때는 1부터 순서대로 진행된다. 1n까지 순서대로 push가 되기 때문에 수열을 재현해내기 불가능한 경우도 나온다. 만약 수열이 일부분이 5, 3 일 경우 5를 pop한 후에 바로 3을 pop하는 것은 불가능하다.(이전 단계에서 4를 pop해 놓지 않은 경우) 일반적으로 고려를 하자면 임의의 k를 pop한 경우 그 다음에 k를 넘어서는 값들이 올 경우 그만큼 push한 후에 pop을 하면 문제가 되지 않지만 k-1보다 작은 값들이 온다면 재현이 불가능한 경우가 된다. 아래 코드의 특이한 점은 변수를 이용해 1부터 n까지 순서대로 push한것이 아니라, 1~n까지의 값을 스택에 넣어 넣고 하나씩 pop하면서 사용했다. 스택 2개를 만들어 사용하는 것을 확인할 수 있을것이다. 전략: m을 pop해야 하는 경우 top이 m보다 작다면 m까지 push한후 pop. 크다면 불가능. ...
피라미드 형태의 삼각형이 주어질때 아래로 내려가면서 최대의 값을 찾는 문제입니다 전략 : 별다른 전략 필요가 없네요 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include <stdio.h> #include <string.h> using namespace std; int dp[500][500]; int main(void) { memset(dp, -1, 0); int t; int max = -1; #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif scanf("%d", &t); for (int i = 0; i < t; i++) { for(int j=0;j<i+1;j++) scanf("%d", &dp[i][j]); } for (int i = 1; i < t; i++) { for (int j = 0; j < i + 1; j++) { if (j == 0) { dp[i][j] = dp[i][j] + dp[i-1][j]; } else if (j == i) { dp[i][j] = dp[i][j] + dp[i-1][j-1]; } else { dp[i][j] = dp[i][j] + (dp[i - 1][j] > dp[i - 1][j - 1] ? dp[i - 1][j] : dp[i - 1][j - 1]); } } } for (int i = 0; i < t; i++) { if (dp[t - 1][i] > max) max = dp[t - 1][i]; } printf("%d\n", max); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }
그래프와 트리쪽 알고리즘이 약해서 요즘 이 파트를 공부하고있습니다. 2진 트리의 원소를 입력받아 순회 종류별로 출력해주는 문제입니다. 재귀적으로 깔끔하게 푸는 것이 중요하겠죠! ...
1~N 까지의 수를 임의로 입력 받아 정렬하는 문제 입니다. 버블, 삽입, 선택 정렬 3가지를 이용해 풀어봤습니다. 버블 정렬만 알고 있었는데 이번 기회로 삽입, 선택 정렬에 대해서 알게 되었네요. Bin-O로 표기할 경우 시간복잡도는 모두 n^2 으로 동일합니다. ...