프로그래밍나무

유클리드 호제법(최대공약수) GCD(A, B)=GCD(B, A% B)이다. 계속하다가 A%B가 0이 될 때 B가 원래 A, B의 최대 공약수가 된다. EX) (6,4)->(4,2)->(2,0) 6,4의 최대 공약수는 2 최소공배수는 A*B/GCD(A, B)이다. 소수 구하기 제일 좋은 방법은 에라토스테네스의 체이다. 시간 복잡도는 N개의 수에 대한 소수를 구할 때 NlglgN이다. 2에서부터 N까지 수에서 제일 작은 수로 나누어지는 수를 삭제한다. 그럼 처음에는 4, 6, 8... 이 없어진다. 다음에는 제일 작은 수인 3으로 나누어지는 수를 삭제한다. 삭제되는 것을 잘 보다 보면 2를 삭제할 때는 삭제되는 처음 수가 2*2이고 3을 삭제할 때는 삭제되는 처음 수가 3*3인 것처럼 처음 삭제되는 수는 i..

cin.getline char a[100]; cin.getline(a,10); cin.getline(a,10,','); char 배열에 9글자까지 문자를 입력하게 된다.(마지막에 널문자가 들어가므로) 두 번째 문장은 엔터가 들어오기 전까지 저장하고 세 번째 문장은 i가 들어오기 전까지 저장하게 된다. getline string a; getline(cin, a); getline(cin, a, ','); #include 필요, getline의 경우 처음에 입력스트림 오브젝트가 오게 된다. 주의할 점 두개의 함수 모두 엔터를 무시하지 않고 그전까지 저장한 후 엔터를 버퍼에서 버린다. 그런데 cin은 엔터를 무시하고 진행하지만 버퍼에서 버리지는 않는다. 그래서 getline을 쓸때 cin이 버퍼에 엔터를 남기지..

cin의 리턴 값은 istream이지만 if나 while의 조건문 안에서는 operator에 의해 bool형으로 바뀐다. bool형으로 바뀌었을 때는 cin의 성공 여부가 리턴 값이 된다. int a; if(cin>>a){ } 이런 형태의 경우 cin에서 정수값이 a에 들어왔는지 확인 후 아니면 if문이 작동하지 않는다. 일반적인 경우 bool형태로 저장하려면 두가지 방법이 있다. bool b = static_cast(cin >> value); bool b(cin>>value); Reference skku.goorm.io/qna/4241

접근방법 동전을 전부 배열에 넣어놓고 하나씩 꺼내면서 전체 배열을 갱신한다. 배열을 갱신할 때 해당 동전의 크기만큼의 앞의 원소를 해당 원소에 더한다. 예를 들어, 동전의 크기가 2일 때 a[i]=a[i]+a[i-2] 왜냐하면 동전의 크기가 2이면 i=2일 때는 동전 하나로 나타낼 수 있지만 i=4일 때는 동전 두 개로 나타내야 하기 때문이다. 코드 #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); int n, k; int coin[101], arr[10001] = { 0, }; cin >> n >> k; for (int i = 0; i > coin[i]; for ..

www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 접근방법 백트래킹 문제이다. 다른 백트래킹 문제와 조금 다르게 하나의 답만 요구하므로 전체를 다 탐색할 필요가 없다. 또한 전체를 탐색하면서 값을 계속 변경할 경우 잘못된 값이 답에 들어갈 수 있다. 그러므로 빈 공간을 다 채워주는 해를 발견할 경우 바로 출력해야 한다. 코드 #include #include #include using namespace std; void DFS(int num); void Prom..

정의 인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식 인접 리스트는 각각의 정점에 인접한 정점들을 리스트로 표현한 방식 이런 그래프가 있을 때 각각의 방식으로 표현한다면 1 2 3 4 1 0 1 1 1 2 1 0 0 1 3 1 0 0 0 4 1 1 0 0 인접 행렬은 이런 방식으로 표현되고 1: 2, 3, 4 2: 1, 4 3: 1 4: 1, 2 인접 리스트는 이런 방식으로 표현된다. 장단점 인접 행렬 그래프에 간선이 많은 밀집 그래프의 경우 유리하다. 장점 두 정점을 연결하는 간선의 존재여부를 O(1)안에 알 수 있다. 정점의 차수를 O(N) 안에 알 수 있다. 단점 인접 행렬 전체를 검사할때 O(n^2)가 필요하다. 인접 리스트 그래프에 간선이 적은 희소그래프의 경우 유리하다 장점 인접..

힙 정렬 알고리즘 개념 과정 설명 오름차순을 구성하기 위해서는 배열을 최대힙으로 구성 최대 힙의 가장 첫번째 원소(배열에서 가장 큰 원소)를 하나씩 빼면서 정렬 힙의 원소가 하나 남을 때까지 반복 과정 상세 설명 정렬할 요소들을 가지고 배열에 하나씩 요소들을 넣으면서 최대 힙 구성 정렬할 요소 (4, 3, 2, 5, 1, 6) 맨 처음 원소 삽입 과정을 따로 처리할 과정이 없으므로 생략 인덱스 1 2 3 4 5 6 4 3 2 3 삽입 인덱스 2의 부모인 1과 비교, 인덱스 1의 원소가 더 크므로 pass 2 삽입시에도 동일 인덱스 1 2 3 4 5 6 4 3 2 5 ↓ 인덱스 1 2 3 4 5 6 4 5 2 3 ↓ 인덱스 1 2 3 4 5 6 5 4 2 3 5 삽입 인덱스 4의 부모인 인덱스 2의 원소와..