Algorithm (4) 썸네일형 리스트형 [백준] 21608 상어초등학교 (JAVA) 백준 21608 상어초등학교 (JAVA) 전형적인 구현문제로 별 다른 알고리즘 로직이 필요하진 않다. 아래와 같이 문제에서 제시한 조건대로 구현해주면 된다. 1. 학생의 번호와 좋아하는 숫자 저장 2. N^2 배열 생성 후 자리 배치 시작 3. 좋아하는 학생이 가장 많이 포함되는 자리에 배치 4. 3을 만족하는 자리가 많으면 빈자리가 많은 칸에 배치 5. 4를 만족하는 자리가 많으면 행의 번호가 작은자리로 6. 5를 만족하는 자리가 많으면 열의 번호가 작은자리로 7. 학생 만족도 구하기 (1명 : 1점, 2명 : 10점, 3명 : 100점, 4명 : 1000점) 고찰 각 학생마다 객체 배열을 생성하고 좋아하는 학생과 공백의 수를 넣어 비교해 주었다. 비교하고 값을 갱신하는 과정에서 비교값을 제외한 객체의.. [알고리즘] 순열, 조합, 부분집합 순열 (Permutation) - 서로 다른 n개의 원소중 r개를 골라 한줄로 나열 하는 것 (nPr) - 순서를 고려해야함 구현 재귀를 활용 cnt를 하나씩 증가시켜 선택수 배열에 값 저장 중복체크를 하기 위해 입력수 배열과 같은 크기의 Boolean 배열을 만들어 사용 기저조건(r개를 만큼 선택 완료) 만족 시 선택수 배열 리턴 구현코드 public static void permutation(int cnt) { if(cnt==R) { System.out.println(Arrays.toString(numbers)); return; } for (int i = 0; i < N; i++) { // 기존자리의 수들과 중복되는지 체크 if(isSelected[i]) continue; numbers[cnt] = .. [백준] 2467 용액 (JAVA) 백준 2467 용액 (JAVA) 2개 이상 100,000개 이하로 이루어진 정수 중 2개를 골라 조합하여 0에 가장 가까운 값을 찾는 문제 하나하나 비교하면 시작복잡도가 O(n^2)가 되어 시간초과가 발생한다. 배열에 모든 정수값을 입력받아 넣고 투포인터를 사용하여 풀이하였음. 고찰 정수가 오름차순으로 주어져 별도로 정렬할 필요 없이 풀이하였다. 두 정수의 합이 양수인 경우 오른쪽 포인터를 왼쪽으로 이동시키고 (오름차순 정렬이므로) 두 정수의 합이 음수인 경우 왼쪽 포인터를 오른쪽으로 이동시킨다. 투포인터 문제를 처음 접해서 다른 코드를 조금 참고하였다. 코드 import java.util.*; import java.io.*; public class Main_bj_2467_용액 { public stati.. [백준] 2580 스도쿠 (JAVA) 백준 2580 스도쿠 (JAVA) 9x9 숫자를 입력받아 스도쿠를 완성하는 전형적인 백트래킹 문제 고찰 오랜만에 알고리즘을 풀어서 조금 헤맸다. 백트래킹만 잘 활용하면 크게 어려움은 없는 문제. 추가적으로 StringBuilder를 사용하지 않으면 시간초과가 발생함. 코드 import java.io.*; import java.util.*; public class Main_bj_2580_스도쿠 { static int map[][]; static int flag = 0; public static void main(String[] args) throws Exception { System.setIn(new FileInputStream("res/input_2580.txt")); BufferedReader br =.. 이전 1 다음