백준인강

알고리즘을 풀때 가장 중요한것은 효율성효율성을 따질때는 먼저 문제의 크기를 살펴봐야한다.문제의 크기 예는 상품의 개수, 접속자 수가 있고 문제의 크기를 N이라고 할때 문제의 크기 N에 따라 걸리는 시간이 다르다.!!문제를 해결할때 문제의 크기를 먼저보고 방법을 생각해야

(A + B) % M == (A % M + B % M) % M(A x B) % M == (A % M x B % M) % M(A - B) % M == (A % M - B % M + M) % M(A / B) % M != (A % M / B % M) % M숫자마다 매번 나눠

a = bc 를 만족하는 자연수c를 a의 약수라고 한다.ex) 24의 약수 : 1, 2, 3, 4, 6, 8, 12, 24for(int i=1; i<=n; i++){ if(n%i==0) { //i는 n의 약수 }}시간 복잡도 : O(n)c가 a의

최대공약수를 구하는 빠른 방법약수가 1과 자기 자신 밖에 없는 수N이 소수가 될려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.방법 1) 어떤 수 N이 소수인지 아닌지 판별하는 방법2부터 N-1까지의 숫자로 나누어 떨어지는 확인 ->

모든 경우의 수를 다 해보는 알고리즘브루트 포스에서 가장 중요한것은 경우의 수가 모두 몇가지인지 미리 아는것이다.브루트 포스는 방벙의 개수가 크지 않은 경우에만 사용할수있다.문제의 가능한 경우의 수를 계산해본다.가능한 모든 방법을 다 만들어본다.for문순열재귀 호출 ★

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 &l

재귀로 풀수 있는 브루트포스 문제는 1.순서 N중에 M개를 뽑을때 순서가 중요한 문제 -> N! 시간복잡도를 가짐 2.선택 N가지 중에 어떤것을 선택하고 어떤것은 선택하지 않는 문제 -> 2^N 문제 1 ) N과 M(1) 문제 자연수 N과 M이 주어졌을 때, 아래

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1,

문제1 ) 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2,

DFS의 시간복잡도->O(V^2) 정점을 한번씩 들릴것이고 정점에 가서 다른 정정에 갈수있는지를 검사 BFS 너비 우선 탐색 • 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식 • 큐에 넣을 때 방문했다고 체크해야 한다 • 인접 행렬: O(V^2)

최단 거리를 구하는 알고리즘이다.BFS는 모든 가중치가1일때, 최단 거리를 구하는 알고리즘이다.최소 비용 문제이어야 한다간선의 가중치가 1이어야 한다정점과 간선의 개수가 적어야 한다. (적다는 것은 문제의 조건에 맞춰서 해결할 수 있다는 것을의미한다)수빈이는 동생과 숨

크기가 N x M 인 배열 - Ai배열돌리기 연산을 구현하는 문제연산을 R번 수행한 결과 값을 구하는 문제연산을 적용한 배열을 Bi배열을 상하반전 시키는 연산1 6 2 9 8 4 → 4 2 9 3 1 87 2 6 9 8 2 → 9 2 3 6 1 51 8 3 4 2 9

\- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.Overlapping Subproblem - 겹치는 작은 문제 Optimal Substructure -최적 부분 구조• Fn = Fn-1 + Fn-2

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.전설카드레

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.1+2+11+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를

45656이란 수를 보자.이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉,

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “1

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.첫째 줄에 두 정수 N(1 ≤ N ≤ 200),

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.동물원 조련사의 머리가 아

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.수의 길이 N이 주어졌을 때, 오르막 수의 개수를

크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다.육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다.어떤 칸을 색칠해야 하는지 주어졌을 때, 필요한 색의 최소 종류를 구

문제BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는

문제게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.크

문제N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.각각의 벽에 대해서 다음을 구해

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을