Algorithm & Data Structure54

• [Algorithm] 백준 1005번(BOJ 1005) ACM Craft 문제풀이 (Java) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 1005번 ACM Craft문제를 풀어보겠습니다. 아래에 있는 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/1005 1. 문제 설명 해당 문제는 특정 건물을 가장 빨리 건설하는 시간을 구해야 하는 문제입니다. 건물을 건설하는 데는 건설 규칙이 있습니다. 예를 들어 4번 건물을 짓고 싶으면 1,2,3번이 모두 지어져야 한다던가, 8번을 짓고 싶으면 9번과 5번을 지어야 한다던가 등 이런 선후관계가 규칙으로 정해져 있습니다. 각각의 건물들을 노드로 본다면 선후관계가 있는 그래프가 되고, 이럴 때 위상 정렬(Topological Sort)을 사용할 수 있습니다. 위상 정렬은 말 그대로.. Algorithm & Data Structure/문제풀이 2021. 7. 31.

• [Algorithm] 백준 2252번(BOJ 2252) 줄 세우기 문제풀이 (Java) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 2252번 줄 세우기 문제를 풀어보겠습니다. 1. 문제 설명 문제를 설명하기에 앞서 아래 링크로 가셔서 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/2252 해당 문제는 학생들을 키 순서대로 세우면 되는 문제입니다. 이를 위해 문제에서는 어떤 학생이 어떤 학생 앞에 서야 하는지 조건도 주고 있습니다. 가장 단순하게 구현을 하면 학생수만큼의 길이를 가진 배열을 만들고 문제에서 조건이 주어질 때마다 배열의 원소들의 위치를 바꿔주면 됩니다. 그러나 이렇게 하면 시간 복잡도에서 당연히 초과 판정을 받게 될 겁니다. 그렇기 때문에 알고리즘을 써야 하고 이때 사용할 수 있는 알고리즘은 위상.. Algorithm & Data Structure/문제풀이 2021. 7. 31.

• 

  [Algorithm] 위상정렬(Topological Sort)을 Java로 구현해보자!! 안녕하세요 Coding-Knowjam입니다. 오늘은 그래프 알고리즘인 위상 정렬을 Java로 구현해보겠습니다. 1. 위상 정렬(Topological Sort)이란? 1.1 개념 우리가 알고리즘을 공부할 때 그래프에 관련된 문제를 많이 접하게 됩니다. 위상 정렬(Topological Sort) 또한 그래프와 관련된 알고리즘 중 하나입니다. 그렇다면 위상 정렬(Topological Sort)은 언제 사용할까요?? 바로 선후관계가 정의된 그래프 구조에서 정렬을 하기 위해 사용할 수 있습니다. 글로만 보면 이해가 잘 되지 않으실 테니 그림과 함께 설명하겠습니다. 위와 같은 그래프가 있을 때, 노드마다 연결된 간선에 방향이 있고 어떤 특정 노드를 방문하기 위해서는 해당 노드에 진입 가능한 노드들을 모두 방문한 후.. Algorithm & Data Structure/이론 2021. 7. 31.

• [Algorithm] 백준 15683번(BOJ 15683) 감시 (Java) 안녕하세요 Coding-Knowjam입니다. 이번에 풀어볼 문제는 백준 온라인 저지 15683번 감시 문제입니다. 1. 문제 설명 문제를 설명하기 전에 아래에 있는 링크를 통해 문제를 읽고 와 주시길 바랍니다. https://www.acmicpc.net/problem/15683 문제 풀기 위해서는 내용 그대로 구현을 하면 됩니다. 구현을 할 때 신경 써야 할 부분은 CCTV가 동서남북 방향으로 회전을 할 수 있다는 점입니다. 문제에서 테스트 케이스마다 주어지는 CCTV의 개수가 다를 텐데 이를 고려해서 모든 경우의 수를 체크해야 합니다. 예를 들어 CCTV가 2개가 주어지고, 하나가 북쪽을 바라보고 있을 때 다른 하나는 동서남북을 모두 체크해야 합니다. 이어서 서쪽을 바라볼 때도 다른 하나의 동서남북을 .. Algorithm & Data Structure/문제풀이 2021. 7. 29.

• [Algorithm] 백준 14891번(BOJ 14891) 톱니바퀴 문제풀이 (Java) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 14891번 톱니바퀴 문제를 풀어보겠습니다. 1. 문제 설명 문제 설명하기 전에 아래 링크로 가셔서 문제를 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/14891 해당 문제는 특별한 알고리즘보다는 구현을 잘하면 되는 문제입니다. 구현을 하는 방법은 여러 가지가 있겠지만 저는 1차원 배열을 이용해서 톱니바퀴의 극 정보를 저장해서 구현했습니다. 또한 회전을 하는 경우는 미리 저장한 인덱스의 위치를 변경해가면서 톱니바퀴의 회전을 구현했습니다. 저와 같은 방법으로 구현을 하실 때 주의하실 점은 인덱스의 계산과정에서 배열을 벗어날 경우에는 다시 처음 혹은 마지막 인덱스로 계산되도록 하는 것입니다. 추.. Algorithm & Data Structure/문제풀이 2021. 7. 28.

• [Algorithm] 백준온라인저지 6588번(BOJ 6588) 골드바흐의 추측 Java 풀이!! (에라토스테네스의 체) 안녕하세요 Coding-Knowjam입니다. 이번에 풀어볼 문제를 백준 온라인 저지에 있는 6588번 골드바흐의 추측입니다. 1. 문제 설명 문제를 설명하기에 앞서 아래 링크로 가셔서 문제를 읽고 오시길 바랍니다. https://www.acmicpc.net/problem/6588 해당 문제는 백만 이하의 숫자 중 4보다 큰 짝수를 홀수 소수의 합으로 나타내는 문제입니다. 문제에서 요구하는 두 개의 수를 구하는 것과 출력 서식에 맞게 출력하는 건 그냥 내용에 맞춰서 구현을 하면 됩니다. 중요한 건 백만 이하의 숫자에서 소수를 찾아내는 것이며, 소수 찾기의 대표적인 알고리즘 에라토스테네스의 체를 사용해서 문제를 풀어야 합니다. 에라토스테네스의 체 알고리즘만 알고 계시다면 어렵지 않게 풀 수 있습니다. 그럼 .. Algorithm & Data Structure/문제풀이 2021. 7. 27.

• [Algorithm] 백준온라인저지 14501번(BOJ 14501) 퇴사 Java풀이!! (DP) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 14501번 퇴사문제를 풀어보겠습니다. 1. 문제 설명 설명하기에 앞서 아래 링크를 통해서 문제를 읽고 와 주시길 바랍니다. https://www.acmicpc.net/problem/14501 해당 문제의 접근법은 2가지가 있습니다. 동적 계획법(Dynamic Programming)을 이용해서 푸는 방법 완전 탐색을 통해서 푸는 방법 완전 탐색으로 푼 사람들의 코드를 보면 재귀 함수의 형태로 많이 구현하시는 것 같습니다. 둘 중 어느 방법을 통해서 구현해도 상관없지만 저는 동적 계획법(Dynamic Programming)을 이용해서 풀어보겠습니다. 우선 문제에서 주어진 조건을 다시 한번 살펴보겠습니다. 문제에서 N+1일에 퇴사를.. Algorithm & Data Structure/문제풀이 2021. 7. 27.

• [Algorithm] 백준온라인저지 1978번(BOJ-1978) 소수 찾기 Java로 문제 풀이!! (수학) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 1978번 소수 찾기 문제를 풀어보겠습니다. 1. 문제 설명 문제에 대한 링크는 아래에 있으니 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/1978 해당 문제는 주어진 n개의 수가 소수인지 아닌지 판별해서 소수인 숫자의 개수를 출력하면 되는 문제입니다. 소수를 찾는 방법에는 여러 가지가 있겠지만, 대표적으로 에라토스테네스의 체 알고리즘이 있습니다. 해당 알고리즘을 간단하게 설명하면 소수의 배수들은 소수가 아니기 때문에 가장 작은 소수인 2부터 시작해서 소수의 배수들을 하나씩 배제해나가면 마지막에는 소수들만 남게 되는 알고리즘입니다. 그럼 알고리즘을 사용해서 문제를 풀어보겠습니다. 2. .. Algorithm & Data Structure/문제풀이 2021. 7. 25.

• [Algorithm] 백준온라인저지 9613번(BOJ-9613) GCD합 Java로 문제풀이!! (수학) 안녕하세요 Coding-Knowjam입니다. 백준 온라인 저지 9613번 GCD합 문제를 Java로 풀어보겠습니다. GCD라는 것은 최대공약수를 의미합니다. 그럼 시작하겠습니다~ 1. 문제 설명 문제를 설명하기에 앞서 아래에 링크를 달아놓았으니 문제를 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/9613 문제에서 요구하는 바는 주어진 n개의 수에서 만들 수 있는 모든 2개의 쌍에서 최대공약수를 구해서 전부 합한 값을 구하는 것입니다. 최대공약수는 유클리드 호제법을 이용해서 쉽게 구할 수 있습니다. 유클리드 호제법을 잘 모르시는 분은 제가 설명한 글이 있으니 아래 링크를 통해서 참고해주시길 바랍니다. [Algorithm] 유클리드 호제법을 Java로 구현해보자!! (w.. Algorithm & Data Structure/문제풀이 2021. 7. 25.

• [Algorithm] 백준온라인저지 1934번(BOJ-1934) 최소공배수 Java로 문제풀이!! (수학) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 1934번 최소공배수 문제를 풀어보겠습니다. 1. 문제 설명 설명에 앞서 아래 링크를 통해 문제를 읽고 오시길 바랍니다. https://www.acmicpc.net/problem/1934 문제는 두 개의 수 사이의 최소공배수를 구하는 문제입니다. 최소공배수를 구하는 공식은 다음과 같이 표현할 수 있습니다. 최소공배수 = 두 개의 수 곱 / 최대공약수 왜 그런지는 소인수 분해를 해보시면 두 개의 수를 놓고 소인수 분해를 해보시면 쉽게 이해할 수 있습니다. 그렇다면 우리는 최대공약수를 구해야 합니다. 최대공약수를 구하는 알고리즘은 유클리드 호제법이 있습니다. 유클리드 호제법이 대해서는 제가 포스팅한 내용이 있으니 궁금하면 아래 링크.. Algorithm & Data Structure/문제풀이 2021. 7. 24.

• [Algorithm] 유클리드 호제법을 Java로 구현해보자!! (with BOJ 2609) 안녕하세요 Coding-Knowjam입니다. 오늘은 유클리드 호제법에 대해서 알아보고 코드로 구현해보겠습니다. 그리고 추가적으로 백준 온라인 저지에 있는 BOJ 2609번 최대공약수 문제도 같이 풀어보겠습니다. 1. 유클리드 호제법이란? (Euclidean Algorithm) 1.1 개념 유클리드 호제법은 두 개의 수가 주어졌을 때, 최대공약수를 구하는 알고리즘입니다. 일반적으로 우리가 수학을 배울 때, 두 수 사이의 최대공약수는 소인수분해를 하고 소인수들의 곱으로 구할 수 있었습니다. 소인수분해를 물론 코드로 구현할 수는 있겠지만 효율적이지는 않을 겁니다. 왜냐하면 우선 소인수분해를 위해 소수를 먼저 찾아야 하고, 찾은 소수가 두 개의 수를 공통적으로 나눌 수 있는지를 확인을 해야 하기 때문입니다. 만.. Algorithm & Data Structure/이론 2021. 7. 21.

• [Algorithm] 백준온라인저지 10430번(BOJ-10430) 나머지 Java로 문제 풀이 (수학) 안녕하세요 Coding-Knowjam입니다. 이번에 풀어볼 문제는 백준 온라인 저지에 있는 10430번 나머지 문제를 풀어보겠습니다. 1. 문제 설명 및 풀이 문제를 풀기 전에 아래 링크를 통해 문제를 읽고 오시길 바랍니다. https://www.acmicpc.net/problem/10430 문제풀이는 매우 간단하므로 바로 코드로 보여드리겠습니다. package study.blog.codingnojam.algorithm; import java.io.IOException; import java.util.Scanner; public class BOJ_10430 { // 백준온라인저지 10430번 나머지 Java로 문제 풀이 public static void main(String[] args) throws I.. Algorithm & Data Structure/문제풀이 2021. 7. 21.