골드90 [백준 5430] AC [C] 풀이 입력부터 애먹은 문제다. "[ , , ]"를 문자열로 입력받아서 해결해도 되지만, 정수만 입력받기 위해 ' [ ', ' ] '가 입력될 때는 getchar()로 buffer를 비워 다음 입력에 영향이 안가도록 했다. getchar(); for (int i = 0; i < n; i++) scanf("%d,", &x[i]); getchar(); error가 뜨는 경우는 다음과 같다. n = 0일 때 n = 0이 아니지만, p에 입력받은 D의 개수보다 n이 작을 때 2번째 조건을 확인하기 위해 n을 감소시켜 반복문이 끝나기 전에 1번째 조건으로 유도하는 방법으로 구현했다. for (int i = 0; p[i] != '\0'; i++){ if (p[i] == 'R') reverse = reverse ? 0.. 2021. 8. 9. [백준 10942] 팰린드롬? [C] 풀이 Dynamic Programming의 Memorization 방식으로 풀이했다. (S~E) 구간이 팰린드롬인지 알기 위해서는 (S+1 ~ E-1), (S+2 ~ E-2), ... (X, X+1) or (X, X)구간의 수들이 팰린드롬인지 알아내는 과정을 반복해야한다. 길이가 3이상일 때, 요소가 홀수개인 팰린드롬은 최종적으로 길이가 1인 팰린드롬의 여부에 따라, 요소가 짝수개인 팰린드롬은 최종적으로 길이가 2인 팰린드롬의 여부에 따라 결정되기 때문에 다음과 같이 나누었다. 입력을 받을 때 길이가 1, 2인 펠림드롬을 확인하고, for (int i = 1; i 1 && arr[i] == arr[i-1]) dp[i-1][i] = 1; } 입력이 끝난 후 길이가 3 이상인 팰린드롬을 구했다. for (i.. 2021. 8. 9. [백준 10993] 별 찍기 - 18 [C] 풀이 별로 만들어지는 삼각형의 높이와 너비는 각각 2^(N) -1, 2^(N+1) -3이다. 다음은 N=3일 때의 예제이다. 빨간 사각형은 mark_star(x, y, n)을 Recursive Call할 때 해당하는 영영이고, (x, y)는 맨 좌측상단이며, N=1때 는 (x, y)와 영역이 일치하므로 별을 찍어주고 함수를 종료한다. 연두색과 하늘색 공간의 별은 다음과 같이 찍었다. for (int i = 0; i < width; i++) arr[x+(n%2 ? height-1 : 0)][y+i] = '*'; // 연두색 for (int i = 0; i < height; i++){ if (n%2) arr[x+i][y+width/2-i] = arr[x+i][y+width/2+i] = '*'; // 하늘색 .. 2021. 8. 8. [백준 2749] 피보나치 수 3 [C] 풀이 Pisano Period를 이용해 풀이했다. 위의 내용 처럼 피보나치 수를 특정 수(n)으로 나눌 때 나머지들은 일정 주기마다 반복되는 것을 알 수 있다. 이러한 주기를 Pisano Period라고 부른다. Pisano Period는 다음과 같이 이용된다. n번째 피보나치 수를 MOD로 나눈 나머지는, N % (Pisano Period) 번째 피보나치 수를 MOD로 나눈 나머지와 같다. Pisano Period번 째의 피보나치 수가 필요하며, 이번 문제에 필요한 Pisano Period를 구하는 방법은 다음과 같다. MOD가 10의 6승이므로 Pisano Period는 1500000 = 15 * 10 ^(5) 이다. 소스코드 #include #define MOD 1000000 #define P 15.. 2021. 8. 2. [백준 9663] N-Queen [C] 풀이 하나의 행에는 하나의 퀸만 존재한다는 점을 이용해, 배열의 index는 행, value는 퀸의 위치로 구현했다. nQueen() 0행 부터 Brute Force 방식으로 퀸이 놓일 수 있는지 확인하고, cnt값을 조작한다. put_check() 현재 행(index)의 value(퀸의 위치)가 다음 행의 value와 일치한다면, 동일한 열에 퀸이 놓인 것 이므로, 다음 열에 퀸을 놓는 경우로 넘어간다. 현재 행(row)에서 이전 행(i)들을 뺀 값이 현재 행의 value(퀸의 위치)에서 이전 행의 value를 뺀 절대값과 동일하다면, 동일한 대각선 상에 퀸이 놓인 것 이므로, 다음 열에 퀸을 놓는 경우로 넘어간다. 소스코드 #include #include int N, board[15], cnt; in.. 2021. 7. 24. [백준 2448] 별 찍기 - 11 [C] 풀이 출력 할 삼각형의 맨 위의 좌표(빨간 원)를 (0, N-1)이라고 하자. 이진트리 처럼 좌측 하단 삼각형의 맨 위 좌표(왼쪽 초록 원)는 (0 + N/2, N-1 - N/2), 우측 하단 삼각형의 맨 위 좌표(오른쪽 초록 원)는 (0 + N/2, N-1 + N/2)이다. 분할정복을 시행할 때마다, 입력받은 크기를 2로 나누어 건네주며, 전달받은 크기가 3이 될 때 배열에 빨간원 - 좌측 초록원 - 우측 초록원 이 순서대로 가장 작은 삼각형 내부에 별을 채워 넣는 것이다. 출력형식에 약간의 장난(?)이 숨어있다. 예제 출력을 드래그 해보니, 각 행의 마지막 별을 찍고 개행이 아니라, 공백을 출력해줘야 한다. memset()를 사용해 배열을 빠르게 초기화하고, 별을 채워 넣자. 소스코드 #include.. 2021. 7. 23. 이전 1 ··· 12 13 14 15 다음
