Category: computer science

2018
0
computer sciencealgorithms

백준[2749] - 피보나치 수3

문제백준 2749 문제 보기 접근 방법피보나치 수열을 푸는 방식은 여러가지가 존재한다. 재귀를 활용하여 O(N^2)으로 푸는 방법, dp를 활용해 O(N)으로 푸는 방법이 많이 알려진 방식이다.하지만 이번 문제는 입력이 10^18이라는 거대한 숫자이므로 저 두 가지 방법 모두 해답은 아니다.여러가지 방법을 찾다가 피보나치 수열을 특정 수로 나눌때 주기가 존

0
computer sciencealgorithms

백준[10830] - 행렬 제곱

문제백준 10830 문제 보기 접근 방법분할 정복으로 풀긴했지만 뭔가 삽질을 좀 많이한 문제다. 원인은 입력값을 제대로 신경쓰지 않았기때문이다.1000으로 행렬이 들어올 경우 제곱되는 B의 값이 1이라면 출력은 0으로 나와야하지만 1000으로 그대로 출력해 삽질 좀 했다.풀이 과정은 지수 법칙을 이용했다. B가 너무 크므로 행렬의 곱을 B번 진행한다면 당연

0
computer sciencealgorithms

백준[2470] - 두 용액

문제백준 2470 문제 보기 접근 방법처음에는 문제를 풀기위한 접근 방법을 생각하기 쉽지않았다. 입력된 숫자중 2개를 조합해여 0에 가장 가깝게 출력해야했다. 즉, 음수 또는 양수에 상관없이 0에만 가까우면 된다.그래서 생각해낸 방법이 정렬을 할때 음수와 양수를 고려하지 않고 정렬을 한뒤, 이웃한 숫자끼리 빼서 가장 작은 절대값을 출력하면 되지않을까 생각했

0
computer sciencealgorithms

백준[1629] - 곱셉

문제백준 1629 문제 보기 접근 방법모듈러의 분배 법칙을 이용하면 문제를 쉽게 풀수 있을것 같았다. 하지만 A와 B의 범위가 너무 커 O(N)으로 풀기에는 역부족이다. 따라서 지수 법칙을 같이 이용하여 O(logN)으로 문제를 해결했다. 지수가 짝수 : B/2로 분할 정복 지수가 홀수 : B-1로 분할 정복 코드#include <iostream&g

0
computer sciencealgorithms

백준[1012] - 유기농 배추

문제백준 1012 문제 보기 접근 방법dfs 방식을 활용하면 문제를 해결할 수 있다. 배추가 존재한다면 인접한 곳에 배추가 있는지 확인하는 방식으로 문제를 풀수 있다. 코드#include <iostream> #include <cstring> using namespace std; int T, M, N, K; int map[51][51]; int

0
computer sciencealgorithms

백준[7562] - 나이트의 이동

문제백준 7562 문제 보기 접근 방법주어진 점에서 도착지까지 몇 번만에 이동할 수 있는지 출력하는 문제로 bfs로 해결 가능하다. 한번에 움직일 수 있는 좌표 차이를 계산해 배열에 저장 이를 활용해 방문 여부를 체크하며 완전 탐색을 진행 도착지면 정답 출력 코드#include <iostream> #include <cstring> #incl