728x90 ProgramSolve42 [BOJ] 2230번 - 수 고르기 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램 → 차이를 비교할 두 수가 같은 수일 수도 있고 조건을 만족하는 최솟값을 구해야 한다. 두 수의 차이를 구해야하는데 입력된 수열이 정렬되어 있지 않으면 모든 원소끼리 비교해야 한다. 예를 들어 5개의 원소가 있으면 하나의 원소와 나머지 4개의 원소를 모두 비교해보아야 한다. 총 반복되는 횟수는 4 X 3 X 2 X 1 = 24 이다. 하지만 이 문제에서 수열의 길이는 최대 100,000까지 가능하기에 시간초과가 뜬다. 그렇다면 시간을 줄이기 위해 원소를 비교하는 반복 횟수를 줄여야한다. 먼저, 수열을 정렬한다. 그러면 아래의 그림과 같이 두 수의 차이가 어떻게 변화할지 .. 2024. 3. 22. [LeetCode] 155. Min Stack (Python) 1. 문제 문제 링크 : 155. Min Stack 문제 태크 : Stack 2. 문제 설명 Implement the MinStack class → MinStack의 클래스를 구현해야한다. MinStack() initializes the stack object. → 스택으로 사용할 객체 생성하기 → Python에서는 List를 사용하여 스택처럼 작업 수행 void push(int val) pushes the element val onto the stack. → 스택에 값을 넣기 void pop() removes the element on the top of the stack. → 가장 최근에 넣었던 값 제거하기 → 스택에 1개 이상의 값이 존재할 경우에만 가능 int top() gets the top e.. 2024. 3. 13. [BOJ] 2529번 - 부등호 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족하는 수열을 구해야한다. → 이 수열을 구하기 위해 백트래킹 방식을 사용한다. 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. → 백트래킹을 할 때 사용할 배열은 위와 같고 중복되지 않는 값들로 이뤄지도록 visited 배열을 사용한다. 이제 여기서 모든 부등호 관계를 만족하는 수열 중 가장 큰 값과 가장 작은 값을 구해야한다. 이때 주의할 점은 첫 자리가 0인 경우도 정수에 포함해야한다. 즉, 0123과 같이 출력해야한다. 나는 이를 쉽게 다루기 위해 문자열로 답을 구하기로 했다. 그러나 최솟값.. 2024. 3. 11. [BOJ] 13023번 - ABCDE (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. - A는 B와 친구다. - B는 C와 친구다. - C는 D와 친구다. - D는 E와 친구다. 우선 여기서 알 수 있는 것은 N명 중 5명이 이와 같은 관계를 가지고 있으면 된다. 이러한 친구 관계를 구하기 위해서는 깊이 우선 탐색을 하여 구할 수 있다. 그래프의 깊이가 5이상일 경우 위와 같은 관계가 존재한다는 것을 알 수 있다. 단, 이는 판별만 하면 되기 때문에 관계를 발견하면 모든 탐색을 멈출 수 있도록 했다. 🍀 풀이 🍀 package Baekjoon; import java.io.*; import java.util.*; public class DFS13023 { sta.. 2024. 3. 1. [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. [BOJ] 2477번 - 참외밭 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 참외밭은 ㄱ자 모양이거나 ㄱ자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향 → 밭의 모양은 항상 그림과 같은 육각형이다.(회전할 수 있다.) 그러므로 밭의 넓이는 [전체적인 사각형의 넓이 - 빠져야할 작은 사각형의 넓이] 이다. 우리는 가장 긴 가로의 길이와 세로의 길이, 빼야할 가로의 길이와 세로의 길이를 구해야한다. 1. 가장 긴 가로와 세로 구하기 입력받을 때 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4 이므로 1, 2일 경우 가로 확인, 3,4일 경우 세로 확인 2. 빼야할 가로와 세로 구하기 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 입력을 받는다... 2024. 2. 19. [Softeer] Lv2. 지도 자동 구축 (Java) 1. 문제 문제 링크 : Lv2. 지도 자동 구축 주제 : Math 2. 풀이 과정 및 정리 내가 이 문제에서 핵심으로 잡은 것은 정사각형의 한 변에 포함되어 있는 점의 개수이다. 이 문제는 정사각형의 중앙에 점을 추가하여 작은 정사각형이 또 생겨난다. 그러므로 단계가 올라갈수록 한 변에 포함되어 있는 점의 개수가 증가한다. 위의 그림은 1단계에서 2단계로 올라갈 때 점의 개수 변화를 나타낸 그림이다. 이 그림을 통해 특징을 생각해보면 두 점 사이에 1개의 점이 추가된다. 즉, 한 변에 점 n개가 있을 경우 n-1개의 점이 추가된다. 모든 점의 개수는 한 변의 개수의 제곱이다. 즉, n의 제곱이다. 그러므로 나는 한 변의 점의 개수가 어떻게 변하는지에 집중했다. 1단계 → 2단계 기본 3개의 점이 존재한.. 2024. 2. 16. [LeetCode] 74. Search a 2D Matrix (Python) 1. 문제 https://leetcode.com/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-interview-150 LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 2. 문제 설명 Each row is sorted in non-decreasing order. → 각 행은 오.. 2024. 2. 7. [Programmers] 조건에 부합하는 중고거래 상태 조회하기 (MySQL) https://school.programmers.co.kr/learn/courses/30/lessons/164672 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🗒️ ERD ✏️ 제출 정답 코드 SELECT BOARD_ID, WRITER_ID, TITLE, PRICE, ( CASE STATUS WHEN 'SALE' THEN '판매중' WHEN 'RESERVED' THEN '예약중' WHEN 'DONE' THEN '거래완료' ELSE 'ERROR' END ) AS STATUS FROM USED_GOODS_BOARD WHERE DATEDIFF('2022-1.. 2024. 2. 6. [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. [BOJ] 1068번 - 트리 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 트리의 구조는 부모와 자식의 관계를 가진다. 이 문제에서 입력으로 각 노드의 부모를 입력받기 때문에 부모 노드에 자식 노드를 추가해주었다. for(int i = 0; i < n; i++) { int p = Integer.parseInt(st.nextToken()); if(p == -1) { //루트노드 저장하기 root = i; } else { tree[p].add(i); //부모노드에게 자식노드 추가 } } 이와 같이 저장한 후 전체적으로 DFS를 이용하여 리프노드를 탐색했다. 그러나 여기서 내가 생각하지 못했던 경우가 존재해서 이를 정리해보려고 한다. 1. 루트 노드가 리프노드가 되는 경우 루트노드가 하나의 자식노드를 가지는데 그 자식 노드를 삭제 루트 노드는 리프 노.. 2024. 2. 1. [BOJ] 5397번 - 키로거 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ Cursor를 기준으로 왼쪽과 오른쪽을 구분하여 저장한다. 커서가 이동할 때마다 왼쪽과 오른쪽에 저장될 문자들이 변하기 때문에 이를 얼마나 효율적으로 관리할 수 있는지가 중요하다. 그러므로 커서를 기준으로 바로 왼쪽 문자와 오른쪽 문자가 가장 위에 있어 옮기기 쉽다. 이 문제에서 나는 스택을 사용하여 저장했다. 아래의 그림은 커서의 이동방향에 따라 동작 과정을 나타낸 것이다. 마지막으로 결과를 출력할 때 주의할 점! 왼쪽 스택에서 값을 꺼내면 뒤쪽의 비밀번호가 먼저 나오므로 꺼낸 후 뒤집어준다. 오른쪽 스택은 앞쪽의 비밀번호가 먼저 나오므로 그대로 해주면 된다. 🍀 풀이 🍀 package Baekjoon; import java.io.*; import java.util.St.. 2024. 1. 28. [Programmers] 성분으로 구분한 아이스크림 총 주문량 (MySQL) https://school.programmers.co.kr/learn/courses/30/lessons/133026 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🗒️ ERD ✏️ 제출 정답 코드 SELECT i.INGREDIENT_TYPE AS INGREDIENT_TYPE, SUM(f.TOTAL_ORDER) AS TOTAL_ORDER FROM ICECREAM_INFO AS i JOIN FIRST_HALF AS f ON f.FLAVOR = i.FLAVOR GROUP BY i.INGREDIENT_TYPE ORDER BY TOTAL_ORDER; 📌 SQL문 .. 2024. 1. 25. 이전 1 2 3 다음 728x90
