codingtest

최백준 선생님의 코테인강 시작....꾸준히 열심히 제발^^효율성 \- 시간이 중요함. 메모리는 부족하면 램을 구매할 수 있음. 즉, 수행 시간이 젤 중요함. \- 복잡한 문제는 정답이 존재하지 않는 문제, 정말 복잡한 문제 등. \- 정답이 존재하고 / 시간 몇

모든 경우의 수를 다 해보는 것이다.brute force attack을 생각하면.. 쉬움0000부터 9999까지 다 입력해보는 것 -> 경우의 수가 10,000가지.O(방법의 개수\*시도하는 복잡도)브루트 포스 문제를 풀기 위해서는 3가지 단계를 생각해볼 수 있다.문제

- 소수 Prime Number 약수가 1과 자기 자신 밖에 없는 수. 소수가 N이라면, 약수로 1,N만 있어야함. 2-(N-1)로 나누어 떨어지지 않으면 N을 소수라고 함. 1. 어떤수 N이 소수인지 ? 소수의 정의 2-(N-1)까지 나누어 떨어지는지 확인

날짜 계산 > ( E,S,M ) 조합의 수 152819 = 7980 i년 : e, s, m 의 조합 i+1년 : e+1, s+1, m+1 e는 15, s는 28, m은 19까지 e가 16, s가 29, m이 20이 되었을 때 1으로 바꿔줌. //다른 풀이

M과 N보다 작거나 같은 두 자연수 x,y를 이용해서 년도를 <x:y>로 표현한다.첫 번째 해는 <1:1>, 두 번째 해는 <2:2>이다<x:y>의 다음 해는 <x':y'>이다. \- x < M 이면 x'=x+1, 아니면 x'=1

재귀함수1) 순서 N가지를 M개 뽑을건데 각서와 관련되어 있는 문제. N!의 시간복잡도를 가짐 N가지가 있으면 다 할 수는 있지만 M개를 어떤 순서로 할 것인지를 고르는 것.2) 선택 N가지가 있을 때 선택과 관련되어 있음 2^n의 시간복잡도를 가짐1부터 N

칸에 정수가 하나씩 들어있는 N행 M열의 격자판에서 K개의 칸을 선택하는 문제선택한 칸에 들어있는 수의 합을 최대로 하는 문제1<=N, M<=10, 1<=K<=min(4,N\*M)K개의 칸 -> 칸이 인접하면 안된다.재귀함수를 이용ex) 100개

1,2,3 더하기 정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제 전체 경우의 수는 3^n보다 작거나 같다. 3^10 = 59049, 모든 경우의 수를 체크해주면 됨. 기준을 정해서 코드를 짜야함. 1,2,3 더하기의 기준은 : 위치. 재귀함수로 풀

백트래킹 재귀 함수를 이용해 브루트포스를 하다 보면 더이상 호출이 의미 없음. 이 때, 이런 경우를 제외하고 브루트 포스를 진행하면 백트래킹이라고 함. 스타트와 링크 > N명을 N/2명씩 두 팀으로 나누려고 한다. (4<=N<=20,N은 짝수) 두 팀의 능력치를 구

임의의 수열을 다른 순서로 섞는 연산크기가 N인 수열이 있을 때 순열의 개수는 N(N-1).....\* 1크기가 N인 수열의 서로 다른 순열은 총N!개가 있다.모든 순열을 사전순으로 나열했을 때 A=1,2,3인 경우 사전순은 다음과 같다.1 2 31 3 22 1 32

수 N개가 주어졌을 때 (3&lt;=N&lt;=8)| A0-A1 | + | A1 - A2 | + ... + | AN-2- AN-1 | 를 최대로 하는 문제수를 변경할 수는 없음. 하지만 수의 순서를 변경은 가능함.N개의 수가 있을 때 순서를 변경할 수 있는 방법의 수는

비트는 0과 1 밖에 없음, &(and), |(or) , ~(not) , ^(xor)A=27=11011A=83=1010011not연산의 경우에는 자료형에 다라 결과가 달라진다. 또한 unsigned, signed에 따라서 보여지는 값은 다르다.shift left(&lt

다이나믹 프로그래밍큰 문제를 작은 문제로 나눠서 푸는 것.두 가지 속성을 만족해야 다이나믹 프로그래밍으로 풀 수 있음.Overlapping Subproblem 겹치는 작은 문제Optimal Substructure 최적 부분 구조Overlapping Subproblem피

1로 만들기 > 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 어떤 정수 N에 위와 같은 연산을 선택해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값

2 x n 직사각형을 1 x 2, 2 x 1 타일로 채우는 방법의 수아래 그림은 2 x 5를 채우는 방법의 수Dn = 2 x n 직사각형을 채우는 방법의 수가장 오른쪽에 올 수 있는 타일의 모양은 2가지 밖에 존재하지 않음.2 x n 직사각형이 있을 때, 가장 오른쪽에

원래 1,2,3더하기에서 점화식은 아래와 같다.Dn=n을 만드는 방법의 수 =Dn-1+Dn-2+Dn-3하지만, 여기서는 같은 수를 두 번 이상 연속해서 사용하면 안되기 때문에 해당 식을 쓸 수 없다.이런 경우에 사용하는 방법1\. 그 조건을 점화식에 넣어본다. Di=i

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제.LIS라고도 함.부분 수열 ? 수열 수를 선택해서 만드는 수열.수열에 있던 수의 순서는 변경할 수 없음.수열 A의 길이 : N, 가능한 부분 수열은 2^N가지연속을 처리하기 위해서는 마지막 수가 무엇인

주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제11 = 3^2 + 1^2 + 1^21,2,3 더하기 문제와 매우 유사한 문제.1,2,3 사용 N 방법의 개수\-> 제곱수를 사용해서 N 최소 개수DN=N을 제곱수의 합으로 나타낼 때의 항

정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제 (n&lt;=1,000,000)int에 들어갈 수 있는 수가 약 21억.d\[]를 선언할 때 int말고 long으로 선언해주어야 함.RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠함.또한

포도주가 일렬로 놓여져 있고, 다음과 같은 2가지 규칙을 지키면서 포도주를 최대한 많이 마시려고 한다.1\. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.2\. 연속으로 놓여 있는 3잔을 모두 마실 수는

순서가 있는 자료구조.한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조 pop &lt;- &lt;- pushpush : 큐에 자료를 넣는 연산pop : 큐에서 자료를 빼는 연산front : 큐의 가장 앞에 있는 자료를 보는 연산b

자료구조의 일종.정점(Node, Vertex)간선(Edge): 정점간의 관계를 나타냄.G = (V,E)로 나타낸다.경로 : 정점 A에서 B로 가는 경로.연결되어 있는 간선을 통해서만 이동 가능함.사이클 : 시작 정점 == 도착 정점.정점 A에서 다시 A로 돌아오는 경로

그래프 : 정점 / 간선을 저장. 정점이 6개, 간선이 8개 있다.간선에 방향이 없기 때문에, 방향이 없는 그래프.정점의 저장 : 개수 V ( 1-V or 0-(V-1) )간선의 저장 : 개수 E 간선의 저장 -> 효율 : 한 정점 V와 연결된 모든 정점을 구하는 시간

목적 : 한 정점에서 시작해서 연결된 모든 정점을 한 번씩 방문하는 것.DFS : 깊이 우선 탐색\-> 사람 1명(시작점) -> 돌아가야 할 스택BFS : 너비 우선 탐색\-> 사람1명 -> 사람을 복제해서 ,,,Depth First Search스택을 이용해서 갈 수

BFS의 목적은 임의의 정점에서 시작해서, 모든 정점을 한 번씩 방문하는 것.BFS는 최단 거리를 구하는 알고리즘.BFS는 모든 가중치가 1일 때, 최단 거리를 구하는 알고리즘임.모든 가중치가 1이 아닐 때는 Dijkstra임\*BFS를 이용해 해결할 수 있는 문제는