#INFO 난이도 : SIVLER5 알고리즘 유형 : 자료구조_큐(Queue) 출처 : 1158번: 요세푸스 문제 (acmicpc.net) #SOLVE 큐(Queue)자료구조를 이용해서 문제를 풀이했다. 우선, 입력받은 N값까지 반복문을 돌려서 큐에 Push해준다. queue josephus; for (int i = 0 ; i < N ; i++) { josephus.push(i + 1); } 다음으로 큐의 front를 push해주고, pop해준다. 그러면 front에 있던 "1"이 가장 위로 올라가게 된다. 이 과정을 M-1(2)번 반복해 준다. 마지막으로 M번째 수는 출력해주고, 큐에서 pop 해준다. 이것을 N번 반복해주면 요세푸스 순열을 구할 수 있다. cout M; queue josephus; f..
#INFO 난이도 : SILVER1 문제유형 : 다이나믹 프로그래밍(DP) 출처 : 11660번: 구간 합 구하기 5 (acmicpc.net) #SOLVE N * N 크기의 표를 저장할 2차원 배열과, 표를 저장한 2차원 배열의 [i][j] 번째 까지의 합을 저장할 dp 배열을 선언한다. int arr[1025][1025] = {}; int dp[1025][1025] = {}; 다음으로 Arr 배열과 Dp 배열을 초기화한다. Arr 배열은 그냥 입력받으면 되기에 설명은 생략하도록 하겠다. Dp 배열의 점화식 원리는 다음과 같다. (1,1) 부터 (4,4) 까지의 합을 구하는 상황을 예시로 생각해보자. 1. dp[i-1][j] 값과 dp[i][j-1] 값을 더한다. 2. 그러면 1 ~ 36 사이의 값은 중..
#INFO 난이도 : SILVER3 알고리즘 유형 : 다이나믹 프로그래밍(DP) 출처 : 11659번: 구간 합 구하기 4 (acmicpc.net) #SOLVE 작은문제의 답으로 부터 큰 문제의 답을 도출하는 다이나믹 프로그래밍(DP) 알고리즘으로 풀이했다. arr[] = 원소를 저장할 배열 dp[] = arr[i] 까지의 합을 저장할 배열 이때 dp[0]의 값은 arr[i]의 값과 동일하니 미리 초기화해 두고, dp[i] = dp[i-1] + arr[i] 라는 점화식을 세워 dp[] 배열을 초기화한다. int arr[100001] = {0,}; int dp[100001] = {0,}; for (int i = 0 ; i > arr[i]; } dp[0] = arr[0]; f..
#INFO 난이도 : BRONZE1 출처 : 1193번: 분수찾기 (acmicpc.net) #SOLVE 1. N이 몇 번째 대각선에 위치하는지 구한다. 우선, 입력받은 N이 몇 번째 대각선에 위치하고 있는지 구해야 한다. 예를 들어 입력받은 N이 10이라면 N의 값은 4/1로, 4번째 대각선에 위치한다. 반복문을 돌려서 N의 값이 i보다 작아진 시점에 해당하는 i번째 대각선에 N번째 원소가 존재한다. //N이 몇 번째 대각선에 존재하는 지 판별 int i = 1; while (N > i) { N -= i; i++; } 2. N이 존재하는 대각선이 홀수번째인지, 짝수번째인지 구한다. 대각선이 홀수번째 대각선인지, 짝수번째 대각선인지에 따라서 식이 달라진다. 하지만 어차피 짝수번째 대각선의 형태는 홀수번째와..
#INFO 난이도 : SIVLER5 문제출처 : 2941번: 크로아티아 알파벳 (acmicpc.net) 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net #SOVLE 처음에는 단순 if의 나열로 문제를 풀이했다. 구현은 매우 간단했지만, 소스코드가 너무 난잡해졌다. #include #include using namespace std; int main() { string str =""; cin >> str; int cnt = 0; for (int i = 0 ; i < str...