목록알고리즘 (32)
우보천리 개발
https://www.acmicpc.net/problem/1546 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net package Chapter1; import java.util.*; public class BJ1546 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 시험 과목 개수 int[] scores = new int[N]; // 입력 for (int i=0; i
https://www.acmicpc.net/problem/11720 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net package Chapter1; import java.util.*; public class BJ11720 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int num = sc.nextInt(); String stringNum = Integer.toString(num); char[] charNum = stringNum.toCharArray(); i..
프로그래머스 단어 변환 https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 가장 짧은 변환 과정을 반환해야 하기 때문에 깊이 우선 탐색보다는 넓이 우선 탐색 BFS를 사용하는게 더 알맞다고 생각했다 큐에 단어와 몇번째 변환인지 저장하기 위해서 별도의 클래스를 정의했다 확인해야할 점은 한번에 하나의 단어만 변환할 수 있기 때문에 변환할 수 있는 단어인지 우선 확인해야한다 그렇기에 isConvert 함수를 통해서 다른..
프로그래머스 타겟 넘버 https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 DFS(깊이 우선 탐색) 을 활용해서 모든 경우의 수를 탐색해본다 깊이가 배열의 길이보다 커지면 스택오버플로우가 발생하기 때문에 DFS깊이가 배열의 크기와 같을 때 확인한다 크기가 같고 우리가 찾는 숫자인 'target' 이라면 count++ 증가 시킨다 그렇지 않으면 depth + 1 로 늘려주고, 배열의 다음숫자를 더하고, 뺄셈을 하여..
백준 2110 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 아이디어 집의 좌표가 입력으로 최대 10억개 들어올 수 있기에 시간초과에 걸릴 수 있다 이진탐색을 사용하면 매번 데이터의 개수를 절반으로 줄일 수 있기 때문에 이분탐색으로 풀어나간다 우선 좌표를 오름차순으로 정렬해야 이진탐색 가능 공유기 사이의 최소길이는 1이다. 최대길이는 배열의 가장 큰 값이다 공유기 배치를 주어진 ..
백준 1715 카드 정렬하기 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 아이디어 카드를 최소한의 비교로 합치기 위해서는 매번 묶음의 개수가 가장 적은 것들을 더해주면 된다 우선순위큐를 사용하여 매번 가장 낮은 숫자들을 더하면 결과를 확인할 수 있다 코드 import java.util.*; class BJ1715 { public static void main(String[] args) { Scanner sc = new Scan..
42889 프로그래머스 카카오 기출 실패율 https://school.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 실패율을 구하는 공식은 스테이지 클리어 못한 플레이어 수 / 스테이지 도달한 플레이어 수 그렇기 때문에 클리어를 못한 사람과, 도달한 플레이어를 카운팅 해주어야한다 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호를 출력해야 되기 때문에 스테이지 번호와 해당 스테이지의 실패율을 저장할 클래스를 만든다 더 자세한건 코드 내 주석을 통해 설명 ..
백준 18310 안테나 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 아이디어 안테나의 위치가 배열의 가운데 있으면 거리가 최소가 되는것을 확인할 수 있다. 즉 배열을 오름차순으로 정렬하고 배열의 가운데 있는 값을 찾으면 된다. 코드 import java.util.*; class BJ18310 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextIn..
백준 10825 국영수 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 아이디어 Comparator 을 재정의해서 문제에서 요구하는 기준으로 정렬을 하면 되는 문제이다 코드 import java.io.*; import java.util.*; class BJ10825 { // 문제에서 요구하는 점수와 이름을 저장하는 클래스를 정의하는데 // 정렬 기준을 정의해야하기 때문에 Comparable 클래스 구현 static clas..
백준 18428 감시 피하기 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 아이디어 백준 14502 연구소 문제와 비슷하게 접근했다 장애물을 3개 설치할 수 있다. 즉 장애물을 빈 곳에 넣으면서 경우의 수를 확인한다 그래프에서 선생님이 있는 곳은 따로 노드에 저장하고 먼저 큐에 넣어준다 큐에서 선생님이 있는 위치마다 상하좌우를 탐색 하고 조건에 따라 "YES" "NO"를 출력해주면 된다 나머지는 코드에서 코드 package baekj..