전체글71

• [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.

• [Algorithm] 백준온라인저지 14499번(BOJ-14499) 주사위 굴리기 Java로 문제풀이(구현) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 14499번 주사위 굴리기 문제를 풀어보겠습니다. 1. 문제 설명 문제를 설명하기에 앞서 아래 링크를 통해 문제를 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/14499 이번 문제의 난이도는 골드 5로 크게 어렵지 않은 문제입니다. 문제풀이를 위해 특별한 알고리즘이 필요하지는 않고, 주어진 내용대로 구현만 하면 됩니다. 주사위가 굴러가면서 각각의 면에 위치하는 값들이 바뀌게 되는데, 이 부분만 주의해서 구현하면 다 푼 거나 다름없습니다. 그럼 코드를 살펴보겠습니다. 2. 문제 풀이 (Java) package study.blog.codingnojam.algorithm; import java.i.. Algorithm & Data Structure/문제풀이 2021. 7. 20.

• [Algorithm] 백준온라인저지 13458번(BOJ-13458) 시험 감독 Java로 문제풀이!! 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 13458번 시험감독 문제를 Java로 풀어보겠습니다. 1. 문제 설명 문제를 설명하기에 앞서 아래 링크를 통해서 문제를 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/13458 문제의 난이도는 브론즈 2로 상당히 쉬운 편에 속하는 문제입니다. 문제를 읽어보시면 아시겠지만 주어진대로 계산이 이루어지도록 구현만 하면 됩니다. 추가적으로 주의하실 점은 결괏값을 저장하는 변수를 int타입으로 하시면 안 된다는 점입니다. int의 경우는 보통 21억 정도까지 저장할 수 있는데, 해당 문제의 최악의 경우는 int의 범위를 벗어나기 때문입니다. 예를 들어서 모든 감독관은 1명만 감시할 수 있다고 하겠습니.. Algorithm & Data Structure/문제풀이 2021. 7. 18.

• [Algorithm] 백준온라인저지(BOJ) 14888번 연산자 끼워넣기 Java로 문제풀이!! (Backtracking) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 14888번 연산자 끼워넣기 문제를 풀어보겠습니다. 1. 문제 설명 문제에 대한 링크는 아래에 있으니 문제를 먼저 꼭 읽고 오시길 바랍니다. https://www.acmicpc.net/problem/14888 문제를 읽어보시면 아시겠지만 주어진 숫자와 연산자를 통해서 얻을 수 있는 최댓값과 최솟값을 구하면 되는 문제입니다. 주어진 숫자의 순서를 바꿀 수는 없으므로, 연산자의 조합을 통해서 문제를 해결하면 됩니다. 어떤 조합이 최댓값인지 최솟값인지 판단을 하는 게 중요한데, 애초에 주어진 숫자와 연산자의 개수가 많지 않기 때문에 모든 경우의 수를 확인해서 해결할 수 있습니다. (백트래킹, 브루트 포스 등등) 저는 연산자를 나열하는.. Algorithm & Data Structure/문제풀이 2021. 7. 15.

• [Algorithm] 백준온라인저지 13460번 구슬 탈출2 Java로 문제풀이!! (BOJ-13460) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 13460번 구슬 탈출 2 문제를 풀어보겠습니다. 해당 문제는 백준 온라인 저지 삼성 SW 역량테스트 기출문제집에 들어있는 문제입니다. 1. 문제 설명 설명에 앞서 아래에 있는 링크를 통해서 풀어볼 문제를 읽어보고 오시길 바라겠습니다. https://www.acmicpc.net/problem/13460 해당 문제는 빨간 구슬이 탈출하는데 보드판을 몇 번 움직였는지를 구하는 문제입니다. 기본적으로 이런 문제는 BFS알고리즘을 통해서 접근을 하는 것이 좋다고 생각합니다. BFS알고리즘을 통해서 보통의 탈출 문제는 문제에서 요구하는 객체에 대한 이동 횟수를 구하기 마련인데 해당 문제는 빨간 구슬과 파란 구슬이 동시에 움직여야 하므로 .. Algorithm & Data Structure/문제풀이 2021. 7. 12.

• [Algorithm] 백준온라인저지 1759번 암호 만들기 Java로 문제풀이!! (BOJ-1759) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지 1759번 암호 만들기 문제를 풀어보겠습니다. 1. 문제 설명 해당 문제의 링크는 아래에 있으니 읽고 오시길 바랍니다. https://www.acmicpc.net/problem/1759 문제 레벨 : 골드 5 문제 키워드 : 백트래킹, 순열 조합 문제에서 요구하는 조건은 2가지입니다. 1. 패스워드는 사전 순서로 정렬되어있을 것 2. 모음 1개 이상, 자음 2개 이상으로 구성되어있을 것 문제를 풀기 위해서는 제시하는 조건을 만족하는 경우의 수를 모두 출력해야 합니다. 경우의 수를 모두 구하는 방법은 여러 가지가 있겠지만, 저는 순열을 구하는 방법을 조금 응용해서 구현하였습니다. 정답처리를 받고 나서 다른 사람들의 정답을 보니까 조합을 .. Algorithm & Data Structure/문제풀이 2021. 6. 24.