[코딩 챌린지 11기 새싹반] 백준 2417 - 정수 제곱근 (Java)
·
알고리즘, 자료구조
📌 문제문제명백준 2417 - 정수 제곱근Linkhttps://www.acmicpc.net/problem/2417분류이분 탐색난이도S4풀이 일자2025-04-27 📌 문제 탐색하기문제를 탐색했을때, 고민해야할 부분은 지난 문제와 마찬가지로 이분 탐색을 이용하여 문제를 접근하면 된다.단, 숫자가 크기 때문에 오버플로우 발생할 수 있으므로 long타입으로 선언하거나 캐스팅 주의 이분 탐색 구현시 1. 중간값(mid)의 제곱이 n보다 크거나 같으면 탐색 범위에서 우측을 줄이고2. 중간값(mid)의 제곱이 n보다 작으면 탐색 범위에서 좌측을 늘린다📌 코드 설계하기1. n 입력받기2. 이분 탐색 메소드 정의하고 탐색 3. 결과값 출력📌 시도 회차 수정 사항 (Optional)1. 출력시 오류 - 결과값에 ..
[코딩 챌린지 11기 새싹반] 백준 1920 - 수 찾기 (Java)
·
알고리즘, 자료구조
📌 문제문제명백준 1920 - 수 찾기Linkhttps://www.acmicpc.net/problem/1920분류이분 탐색난이도S4풀이 일자2025-04-26 📌 문제 탐색하기문제를 탐색했을때, 고민해야할 부분은 순차적 탐색으로 탐색을 하면 시간이 오래 걸려 이분(이진) 탐색 사용하기 이분 탐색이란? 순차적 탐색보다 빠른 탐색을 위해 나온 탐색 방법으로 실제로 이분 탐색의 시간 복잡도가 순차적 탐색보다 낮음- 정렬된 배열 안에서 특정 원소를 찾을때 인덱스 i부터 j의 중간값과 비교- 중간값이 찾는 원소가 아니라면 인덱스 i와 j 다시 정해줌- 인덱스 i와 j의 정할때마다 탐색 범위를 반으로 줄어듦 이분 탐색을 적용시 반복문 또는 재귀를 통해 구현하는데 해당 문제에서는 반복문을 통해 구현하겠다.📌 코..
[코딩 챌린지 11기 새싹반] 백준 1904 - 01타일 (Java)
·
알고리즘, 자료구조
📌 문제문제명백준 1904 - 01타일Linkhttps://www.acmicpc.net/problem/1904분류DP난이도S3풀이 일자2025-04-25 📌 문제 탐색하기문제를 탐색했을때, 고민해야할 부분은 시간 제한이 짧기 때문에 DP를 이용하여 구하기 점화식 : arr[i] = (arr[n-1] + arr[n-2])📌 코드 설계하기1. 자연수 n을 입력 받음2. 2진 수열의 개수를 담을 배열 선언.. +2는 n이 1일때 안전3. 반복문을 통해 DP 점화식 적용4. 결과값 출력📌 시도 회차 수정 사항 (Optional)없음📌 정답 코드package org.example.day19;import java.io.*;/** * description : 백준 1904 - 01타일 * package..
[코딩 챌린지 11기 새싹반] 백준 2747 - 피보나치 수 (Java)
·
알고리즘, 자료구조
📌 문제문제명백준 2747 - 피보나치 수Linkhttps://www.acmicpc.net/problem/2747분류DP난이도B2풀이 일자2025-04-24 📌 문제 탐색하기 문제를 탐색했을때, 고민해야할 부분은 DP(Dynamic Programming)으로 풀었을때 재귀보다 얼마나 빠른지가 중요하다.DP(Dynamic Programming) : 복잡한 문제를 작은 문제로 나눠서 푸는 방법 그리고 이미 푼 작은 문제의 결과를 저장해서 같은 계산을 반복하지 않도록 최적화하는 기법재귀로 피보나치를 구현한다고 하면 비효율적인 부분이 발생.. 같은 계산이 중복됨f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2)f(5)= f(4) + f(3)= (f(3) + f(2)) + (f(2) ..
[코딩 챌린지 11기 새싹반] 백준 10815 - 숫자 카드 (Java)
·
알고리즘, 자료구조
📌 문제문제명백준 10815 - 숫자 카드Linkhttps://www.acmicpc.net/problem/10815분류자료구조난이도S5풀이 일자2025-04-23 📌 문제 탐색하기숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.셋째 줄에는 M(1 ≤..
[코딩 챌린지 11기 새싹반] 백준 7785 - 회사에 있는 사람 (Java)
·
알고리즘, 자료구조
📌 문제문제명백준 7785 - 회사에 있는 사람Linkhttps://www.acmicpc.net/problem/7785분류자료구조난이도S5풀이 일자2025-04-22 📌 문제 탐색하기상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오. 문제를 탐색했을때, 고민해야할 부분은 이름을 중복없이 관리하고, 이름..
[코딩 챌린지 11기 새싹반] 백준 28279 - 덱2 (Java)
·
알고리즘, 자료구조
📌 문제문제명백준 28279 - 덱2Linkhttps://www.acmicpc.net/problem/28279분류자료구조난이도S4풀이 일자2025-04-21 📌 문제 탐색하기정수를 저장하는 덱을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 여덟 가지이다.1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.5: 덱에 들어있는 정수의 개수를 출력한다.6: 덱이 비어있으면 1, 아니면 0을 출력한다.7: 덱에 정수가..
[코딩 챌린지 11기 새싹반] 백준 18258 - 큐2 (Java)
·
알고리즘, 자료구조
📌 문제문제명백준 18258 - 큐2Linkhttps://www.acmicpc.net/problem/18258분류자료구조난이도S4풀이 일자2025-04-20 📌 문제 탐색하기정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 여섯 가지이다.push X: 정수 X를 큐에 넣는 연산이다.pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 큐에 들어있는 정수의 개수를 출력한다.empty: 큐가 비어있으면 1, 아니면 0을 출력한다.front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.back: 큐의 가장 뒤에 있는 정수를..
[코딩 챌린지 11기 새싹반] 백준 10828 - 스택 (Java)
·
알고리즘, 자료구조
📌 문제문제명백준 10828 - 스택Linkhttps://www.acmicpc.net/problem/10828분류자료구조난이도S4풀이 일자2025-04-19 📌 문제 탐색하기정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 다섯 가지이다.push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 스택에 들어있는 정수의 개수를 출력한다.empty: 스택이 비어있으면 1, 아니면 0을 출력한다.top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 문제를 탐색했을때, 고민해..
[코딩 챌린지 11기 새싹반] 백준 2231 - 분해합 (Java)
·
알고리즘, 자료구조
📌 문제문제명백준 2231 - 분해합Linkhttps://www.acmicpc.net/problem/2231분류브루트포스난이도B2풀이 일자2025-04-18 📌 문제 탐색하기어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 문제를 탐색했을때, 고민해야할 부분은 m을 자리수별로 분해하여 합하..