728x90 ProgramSolve/Softeer8 [Softeer] Lv3. 택배마스터 광우 (Java) 1. 문제 문제 링크 : Lv3. 택배마스터 광우 주제 : 완전탐색, 백트래킹 2. 풀이 과정 및 정리 이 문제에서는 레일을 어떤 순서로 돌아서 최소한의 무게로 일할 수 있는지 찾아야한다. 위의 그림과 같이 레일을 돌면서 바구니 무게를 초과하기 전까지는 무조건 1번으로 시행되어야 한다. 이는 딱히 규칙성이나 공식을 찾을 수 없다. 그래서 내가 선택한 방식은 완전탐색을 하여 레일의 순서를 모두 구했다. 이를 구하기 위해서 아래와 같이 백트래킹 방식으로 순서를 구했다. static void dfs(int count, int[] result) { if(count == n) { //순서가 정해졌을 경우 int w = getWeight(result); minWeight = Math.min(w, minWeight).. 2024. 2. 25. [Softeer] Lv3. GINI야 도와줘 (Java) 1. 문제 문제 링크 : Lv3. GINI야 도와줘 주제 : BFS 2. 풀이 과정 및 정리 예전에 비슷한 문제를 풀었던 기억이 나서 또 비슷하게 풀었다. (문제 풀이 기록 - 3055번 탈출) https://soo-note.tistory.com/52 [TIL] Algorithm - 다익스트라 + 그래프 문제 풀이(BFS) 1. 다익스트라 알고리즘(Dijkstra algorithm) 모든 간선에 대한 가중치가 항상 0이상임을 가정하고 두 꼭짓점 간의 가장 짧을 경로를 찾는 알고리즘 간선 완화(Edge Relaxation) 시작 정점 s에서 다른 정점 v soo-note.tistory.com 저번에는 파이썬으로 풀었는데 이번에 자바로 풀어보았다. 이번에도 핵심은 비오는 시간을 구하고 이에 따른 이동방법을 .. 2024. 2. 22. [Softeer] Lv3. 비밀메뉴2 (Java) 1. 문제 문제 링크 : Lv3. 비밀메뉴2 주제 : LCS, DP 2. 풀이 과정 및 정리 이 문제는 두 수열 사이에 공통적으로 포함된 연속된 수열의 최대 길이를 구해야 한다. 여기서 가장 먼저 생각난 것은 LCS 즉, 가장 긴 공통 부분 문자열이다. [LCS 문제 풀이 연습] https://soo-note.tistory.com/56 [TIL] 동적 프로그래밍 문제 풀이 1. DP 문제 풀이 1. 9084번 - 동전 import sys T = int(sys.stdin.readline()) for _ in range(T) : N = int(sys.stdin.readline()) coin = list(map(int, sys.stdin.readline().split())) M = int(sys.stdin.r.. 2024. 2. 20. [Softeer] Lv2. 지도 자동 구축 (Java) 1. 문제 문제 링크 : Lv2. 지도 자동 구축 주제 : Math 2. 풀이 과정 및 정리 내가 이 문제에서 핵심으로 잡은 것은 정사각형의 한 변에 포함되어 있는 점의 개수이다. 이 문제는 정사각형의 중앙에 점을 추가하여 작은 정사각형이 또 생겨난다. 그러므로 단계가 올라갈수록 한 변에 포함되어 있는 점의 개수가 증가한다. 위의 그림은 1단계에서 2단계로 올라갈 때 점의 개수 변화를 나타낸 그림이다. 이 그림을 통해 특징을 생각해보면 두 점 사이에 1개의 점이 추가된다. 즉, 한 변에 점 n개가 있을 경우 n-1개의 점이 추가된다. 모든 점의 개수는 한 변의 개수의 제곱이다. 즉, n의 제곱이다. 그러므로 나는 한 변의 점의 개수가 어떻게 변하는지에 집중했다. 1단계 → 2단계 기본 3개의 점이 존재한.. 2024. 2. 16. [Softeer] Lv3. 성적평가 (Java) 1. 문제 문제 링크 : Lv3. 성적평가 주제 : 정렬, 구현 2. 풀이 과정 및 정리 이번 문제의 핵심은 정렬이었던 것 같다. 학생들의 점수를 정렬하여 순위를 매겨야 한다. 단, 점수가 입력된 순서대로 순위를 출력해야하므로 정렬을 해도 원래 위치를 기억해야한다. 나는 여기서 Student라는 클래스를 만들어 위치와 점수를 저장하도록 했다. class Student { int idx, score; //학생 인덱스, 점수 public Student(int idx, int score) { this.idx = idx; this.score = score; } } 이제 Student 타입의 배열을 생성했으므로 이를 정렬해야한다. 나는 이차원 배열을 정렬하기 위해 Comparator 인터페이스를 활용해 왔다. 하.. 2024. 2. 4. [Softeer] Lv3. 순서대로 방문하기 (Java) 1. 문제 문제 링크 : Lv3. 순서대로 방문하기 주제 : 백트래킹 2. 풀이 과정 및 정리 이 문제에서는 탐색을 할 때 꼭 순서대로 방문해야하는 지점이 있다. 그래서 생각한 방법은 현재 위치에서 도착해야할 지점을 저장하여 확인하는 것이다. 즉, 분홍색 지점에서 초록색 지점까지 가고 그 후 파란색 지점까지 마저 탐색할 수 있도록 한다. 경로 탐색 함수에서 두가지의 경우가 존재한다. 중간 지점에 도달한 경우 → 다음 지점까지 경로 탐색 마지막 도착 지점에 도달한 경우 → 경로 1개를 찾았으므로 count 증가 3. 코드 import java.io.*; import java.util.*; public class Main { static class Node { int x, y; public Node(int .. 2024. 2. 3. [Softeer] Lv3. 자동차 테스트 (Java) 1. 문제 문제 링크 : Lv3. 자동차 테스트 주제 : 이분탐색 2. 풀이 과정 및 정리 임의의 3개를 선택하여 중앙값 m이 나오는 서로 다른 경우의 수를 구해야한다. → m보다 작은 연비 1개, m보다 큰 연비 1개를 선택하는 경우의 수를 구해야한다. 단, 주어지는 자동차의 연비는 서로 다름을 가정해도 좋습니다. → 중복된 연비는 없으므로 모두 서로 다른 경우의 수를 구할 수 있다. 그러므로 우선 입력받은 연비 배열을 오름차순으로 정렬했다. 여기서 중앙값의 인덱스를 구해야하는데 여기서 이분탐색을 사용했다. 이분탐색으로 구한 인덱스를 기준으로 위의 그림처럼 각각 앞과 뒤의 원소의 수를 곱해 문제를 해결했다. 3. 코드 import java.io.*; import java.util.*; public cl.. 2024. 2. 2. [Softeer] Lv2. 회의실 예약 (Java) 1. 문제 문제 링크: Lv2. 회의실 예약 주제 : 구현 2. 풀이 과정 및 정리 구현 문제라서 차근차근 해나아가면 된다. 이번에 쓰인 헷갈린 java 문법을 정리해보려고 한다. 1. 리스트 배열 List[] arrList = new ArrayList[n]; 위와 같이 리스트 배열을 선언한다. 주의 : new 이후에는 배열의 크기만 쓴다. → 리스트 속 타입을 쓸 수 없다. for(int i = 0; i < n; i++) { arrList[i] = new ArrayList(); } 그 후 각 리스트를 초기화해준다. 2. HashMap key 값으로 정렬하기 HashMap map = new HashMap(); List keyList = new ArrayList(map.keySet()); Collectio.. 2024. 2. 2. 이전 1 다음 728x90
