전체 글

문제 링크 : https://www.acmicpc.net/problem/1707 위의 문제는 그래프를 2개의 집합으로 나누었을 때 각각의 집합에 인접한 정점이 없는지를 확인하는 문제이다.단순히 생각해 보면 한 정점의 바로 옆에 있는 정점을 다른 집합으로 정했을 때 문제가 없을지 확인하면 된다.경우의 수를 생각해 보면 아래와 같은 경우가 있다. 첫 번째로 만약 일직선의 경우 1번 노드를 0 집합에 넣고2번 노드를 1 집합 3번 노드를 0 집합에 넣는다면 해당 그래프는 이분 그래프라고 할 수 있다. 따라서 일직선의 경우에는 이분 그래프의 조건을 만족한다. 두 번째로 순환그래프 중 문제가 발생하는 경우이다.홀수개로 이루어진 정점이 순환되는 위와 같은 형태의 그래프에서는1번과 3번 노드가 둘 다 0 집합에 들어..

문제 링크 : https://www.acmicpc.net/problem/18352 위의 문제는 전형적인 그래프를 이용한 문제이다.정점과 정점 사이의 간선의 길이가 모두 1이기 때문에 가중치가 없는 그래프라고 생각하면 된다. ArrayList []로 그래프를 표현하고 시작 정점으로부터 BFS로 순회하며 시작 정점과 떨어진 거리가 K인 정점을 찾으면 된다.시간을 좀 더 줄이기 위해 break에 라벨을 달아 바로 while 문이 종료될 수 있도록 했다. (방문배열을 -1 로 초기화하여 방문여부를 판단해도 괜찮다.)package boj;import java.util.*;import java.io.*;public class BOJ18352 { static int K; static int N; st..

문제 링크 : https://www.acmicpc.net/problem/1850 이 문제는 최대공약수를 구해야 하는 문제이다. 입력값 A, B 가 3, 4일 때 각각 111, 1111으로 변환된다고 생각하면입력값이 너무 커지기 때문에 1 로 변환하지 않고 그대로 최대공약수를 구한 다음해당 최대 공약수만큼 1을 출력해 주면 된다. 여기서 최대공약수를 구할 때는 유클리드 호제법을 사용하면 된다.유클리드 호제법이란 두 숫자 a, b의 최대 공약수를 구하는 알고리즘으로두 수중 더 큰 값 % 작은 값을 하여 나머지가 나오면해당 나머지가 0 이면 이때의 작은 값을 최대공약수로 리턴하고나머지가 0이 아니라면 이번에는 기존의 작은 값을 큰 값에 대입,작은 값에는 나머지를 넣고 나머지연산을 반복하는 알고리즘이다. pac..

문제 링크 : https://www.acmicpc.net/problem/1456 이 문제는 소수를 적절히 구하고 해당 소수를 N 제곱하면서 A와 B 사이의 값의 개수를 찾는 문제이다.에라토스테네스의 체를 이용하여 소수를 구한다.이때 최댓값은 문제의 조건에 따라 10^14의 제곱근인 10^7 까지만 구하면 된다. 소수를 구했으면 소수를 하나씩 순회하면서제곱 중 문제 조건에 맞는 소수가 있을 때마다 answer 값을 하나씩 늘려준다.이때 제곱을 구하면서 long 타입의 최댓값보다 값이 커질 수 있기 때문에 조건문을 활용하여 오버플로우를 방지해야 한다. package boj;import java.util.*;import java.io.*;public class BOJ1456 { public static ..