hojak99 의 블로그

BFSBFS 의 목적은 임의의 정점에서 시작해서, 모든 정점을 한 번씩 방문하는 것이다. 그렇지만 BFS 는 최단거리를 구하는 알고리즘으로 사용된다.BFS 로 최단거리를 구하려면 우선 모든 가중치가 1일 때라는 전제조건이 있어야 한다.왜냐하면 BFS 는 모든 간선을 큐에 넣고 그 연결된 모든 간선을 탐색하기 때문이다.그렇기 때문에 우리는 BFS 를 이용해서 최단거리를 구할 수가 있다.BFS 를 이용해 해결할 수 있는 문제BFS 를 이용해 해결할 수 있는 문제는 다음과 같은 조건을 만족해야 한다.최소 비용 문제간선의 가중치가 1정점과 간선의 개수가 적어야 함. (시간 제한, 메모리 제한)최소 비용 = 최단 거리의 거리 는 같아야 한다.예제백준 2178 문제를 살펴보자. 미로찾기 문제다.#include #i..

백준 문제 10971백준 문제 10971 문제는 외판원 순회 문제로, TSP(Traveling Salesman Problem) 문제이다.위와 같은 문제는 순열을 이용해 문제를 해결 할 수 있는데, 그 이유는 (2 w[i][q]; } } std::vector a(n); for (int i = 0; i < n; ++i) { a[i] = i; } int result = 999999999; do { int sum = 0; bool isOk = true; for (int i = 0; i < n - 1; ++i) { // 여기서 vector a 는 수열이라서 n+1 로 해도 모두 돈다. if (w[a[i]][a[i + 1]] == 0) { // [i][j] 가 0일 때 못 가기 때문 isOk = false; } e..

백준 2609 문제이다 최소 공배수와 최대 공약수를 구하는 문제이다. 우리는 여기서 유클리드 호제법을 사용할 수 있다. 얼마 전 내가 유클리드 호제법 증명하는 것을올렸으니 한 번 찾아보자. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int a = scanner.nextInt(); int b = scanner.nextInt(); int g = gcb(a, b); System.out.println(g); System.out.println((a*b) / g); } public static int gcb(int a, int b..

#include /** (A * B) * C 일 때 (A * C) + (B * C) 와 같다. 하지만 나머지 연산은 다르다(고 한다). (A * B) % C 일 때 (A % C) + (B % C) % C 와 같다. % c 일 땐 그렇다고 한다. 뺄셈일 때는 음수가 나올 수 있어서 (A - B) % C 일 때 (A % C) - (B % C + C) % C */ int main() { int a = 0, b = 0, c= 0; std::cin >> a >> b >> c; if (2

일곱 난쟁이 문제다. [https://www.acmicpc.net/problem/2309] 문제를 읽고 나면 알 수 있듯이, 아홉 명의 난쟁이 중에 일곱 난쟁이를 찾으면 된다. 이 말인 즉슨, 2명을 찾아서 제외를 하면 되는 것이다. 그러면 2명이면 n제곱으로 찾을 것이다. 3명이면 n 세제곱 , ...... 한 번에 모든 난쟁이 키를 더한 뒤에 한 명, 한 명 빼주면 언젠간 100 이 딱 떨어지면 그 수를 제외하고 출력을 하면 된다. for ( int i = 0; i < 9; ++i ) { for ( int q = i + 1; q < n; ++q ) { if (sum - arr[i] - [arr- q] == 100 ) { // arr[i], arr[q] 를 제외하고 출력 } } }

Graph이번엔 그래프에 대해서 알아보도록 하겠다. Introduction일련의 정점(node, vertex, 꼭짓점) 집합 V와 간선(edge, 변) 집합 E로 구성된 자료구조의 일종이다. 일반적으로 정점엔 데이터, 간선엔 정점과 정잠 사이의 관계 정보가 포함되어 있다.여기서 []는 정점이다([V1]). 정점 사이에는 간선이다(e1). [V1] ------ e1 ------- [V2]------e3------[V4] | [V3] ---- e2---- | | e4 | [V5] G = (V, E) V = {V1, V2, V3, V4, V5} E = {E1, E2, E3, E4} e1 = (V1, V2) e2 = (V2, V3) e3 = (V2, V4) e4 = (V3, V5) 쉽게 한 마디로 말하면 사물들..

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 진짜 좋은데 내가 이해가 안감

codility 사이트에서 나온 난이도 중간의 알고리즘 문제이다.문제 이해하기 조금 어려웠던 것도 있어서 이 문제는 예외적으로 블로그에서 설명하려고 한다. /* * 0으로 초기화 되어 있는 N 개의 카운터가 주어지며, * increase(X) 는 해당 카운터 를 1 증가시킨다. * max counter 는 모든 카운터를 가장 큰 카운터의 값으로 설정 한다. * * 비어있지 않는 M개의 요소를 가진 배열 A가 주어지며 * 만약 A[K] = X, 1

문제 : N개의 정수로 구성된 배열 A가 있는데 이 배열은 홀수 개의 원소들을 가지고 있다. 그리고 딱 한 원소를 제외한, 나머지 원소들은 다른 원소와 같은 값을 가지고 짝을 이룬다. 여기서 짝을 이루지 않는 원소를 알아내라. {9,3,9,3,9,7,9} 에서는 7이 짝을 이루지 않는 원소이다. 처음에 나는 o(n)2 의 시간 복잡도를 가진 알고리즘을 작성했다. for 문을 두 번 돌려서 똑같은 숫자가 있다면 -1로 값을 바꾸고 -1이 아닌 값들을 특정 변수에 저장하도록 해서 문제를 풀었는데 시간 초과로 점수가 66점을 맞았다. o(n)2 알고리즘 밖에 생각이 안나서 결국 구글을 했는데 xor을 사용하라는 어떤 블로그를 보았다. public class OddOccurrencesInArray { publi..

'o'와 'x' 표시를 해서 점수를 매기는데 여기서 점수는 'o'가 누적되는 방식으로 채점된다. 자신을 포함한 연속된 'o'의 개수만큼 점수로 채점. Ex) oooxoo 일 때 1+2+3+0+1+2 = 9 #include #include#include int main(){char arr[100];int cnt = 1;int sum = 0;scanf("%s", arr); int aaa= strlen(arr);int *arrSize = (int*)malloc(sizeof(int)*aaa); for (int i = 0; i < strlen(arr); i++) {if (arr[i] == 'o') {sum += cnt;cnt += 1;continue;}else if (arr[i] == 'x') {cnt = 1;c..