알고리즘/알고리즘 구현 (7) 썸네일형 리스트형 피보나치 수열 www.acmicpc.net/blog/view/28 [BOJ 9663] N-Queen 문제 : https://www.acmicpc.net/problem/9663 분류 : 백트래킹 N * N 체스판에 N개의 퀸을 놓는 경우의 수를 찾는 문제이다. 가장 빠른 방법은 미리 구해놓은 값을 리턴하는 경우이다. N이 15 이하의 자연수 이므로 15개의 값만 미리 배열에 저장해 놓고 입력값에 따른 경우의 수를 리턴한다. 다음 그림은 n의 값에 따른 경우의 수의 개수이다. 예를 들어 N = 8일 경우, 8*8체스판에 8개의 퀸을 놓을 수 있는 경우의 수는 총 92가지가 된다. 가장 빠른 방법이긴 하지만, 알고리즘을 공부를 하는 입장에서는 도움이 되지 않는 방법이므로 백트래킹 방법으로 문제에 접근해보자 퀸 배치하기 우선, 퀸을 놓을 수 있는 상황에 대해 알아보자 퀸은 가로, 세로, 대각선 방향으로 이동이.. [BOJ 2231] 분해합 , [BOJ 4673] 셀프 넘버 분해합 : https://www.acmicpc.net/problem/2231 분류 : 브루트 포스 셀프 넘버 : https://www.acmicpc.net/problem/4673 분류 : 에라토스테네스의 체 두 문제가 유사한 부분이 있어서 같이 설명하려고 한다. 분해합 입력된 수가 되게 하는 생성자를 찾는 문제이다. (생성자 : 원래 수와 각 자리 수의 합 => 분해합) 예를 들어 216의 생성자로 198과 207이 될 수 있다. 198 + 1 + 9 + 8 = 216 207 + 2 + 0 + 7 = 216 생성자를 찾기 위해서 1~n까지 모든 수의 분해합이 N이 되는지 확인하는 방법도 있겠지만, 좀 더 최적화 할 수 있는 방법이 있다. 각 자리숫자가 최대 9라는 점을 이용하면 좀 더 쉽게 풀 수 있다... [BOJ 1002] 터렛 문제 : https://www.acmicpc.net/problem/1002 문제 분류 : 수학 원의 위치 관계를 따져보는 문제이다. 두 원의 위치 관계 두 원이 일치하는 경우 => d = 0, r1 = r2 만나지 않는 경우 1) 내부에서 만나지 않는 경우 : d 차 차 < d < 합 */ while (T--) { scanf("%d %d %d %d %d %d", &x1, &y1, &r1, &x2, &y2, &r2); if (x1 == x2 && .. [BOJ 3009] 네 번째 점 문제 링크 : https://www.acmicpc.net/problem/3009 문제 분류 : 수학 문제 자체가 어렵진 않지만, XOR연산으로도 풀 수 있다는 걸 생각 못했다. 처음 구현한 코드 #include int x, y; int point[3][2]; int main() { for (int i = 0; i < 3; i++) { scanf("%d %d", &point[i][0], &point[i][1]); } point[0][0] == point[1][0] ? x = 2 : point[0][0] == point[2][0] ? x = 1 : y = 0; point[0][1] == point[1][1] ? y = 2 : point[0][1] == point[2][1] ? y = 1 : y = 0; pr.. [BOJ 15552] 빠른 A+B 문제 링크 : www.acmicpc.net/problem/15552 문제 분류 : 입출력 사용 언어에 맞는 빠른 입출력을 요구하는 문제이다. 문제 풀이는 했지만, 다른 사람들의 풀이를 보고 새롭게 알게된 내용이 있어서 정리 차원에서 기록을 남긴다. 속도 향상을 위한 방법 컴파일 속성 조정 (최적화 옵션 및 타겟 설정) 빠른 입출력 사용 참고) 더보기 register 변수를 사용하는 경우도 있는데, C++17부터 이 키워드는 사용되지 않는다고 한다. 기존 코드에 register 키워드가 있어도, 실제 레지스터를 사용하는 것은 컴파일러나 CPU에 따라 다르다고 한다. C언어의 경우 해당 키워드가 적용된다. RAM대신 CPU의 Register를 사용하게 되어 자주 사용 되는 변수를 register키워드로 선언.. [BOJ 1799] 비숍 문제 링크 : https://www.acmicpc.net/problem/1799 문제 분류 : 백트래킹 참고 : https://j2wooooo.tistory.com/80 풀이 방법이 생각이 안나서 참고하면서 풀었다. ㅠ.ㅠ 문제 풀이 핵심은 하나는 체스판을 두 부분으로 나누어서 보는 것이다! 위 그림과 같이 체스판을 흰색과 검은색으로 칠하고 보면, 흰색 영역과 검은색 영역은 대각선으로 이동으로는 절대 겹칠 수 없는 영역이다. 즉, 하나의 체스판을 2부분으로 나눠서 생각해볼 수 있다. 최종적으로 검은색 영역 최대 개수 + 흰색 영역 최대 개수 로 답을 구할 수 있다. 한 부분에 대한 시간 복잡도는 다음과 같이 계산될 수 있다. 하나의 칸에 비숍을 놓는경우, 놓지 않는 경우가 존재 => 2가지 흑, 백 각각.. 이전 1 다음
