공부의 발자취를 남기는 블로그

문제분석 목표: 어떤 간선을 잘랐을때, 나누어진 두개의 전력망의 차이가 최소가되는 경우구하기 간선을 잘랐을때, 두개의 전력망의 차이가 최소가 되는경우를 구해야하기때문에 일단, 간선을 하나씩은 다 잘라봐야한다. (완전탐색) 간선을 자르는행위는, wires간선에 원소를 없애버려야한다. 하지만, 입력값을 건드릴수는 없으니... wires배열의 복사본으로 List를 선언했다. BFS탐색을위해, Queue를 선언한다. (이유: 간선이 연결되어있는걸 탐색하기위해) 예시를 하나 들어보자면, wires간선에 [4,7]을 자르기로했다. 그러면, List=[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 이 되어야한다. 자르고나면, 왼쪽이든 오른쪽이든 갯수를 세어야한다. 본인은 부모..

문제분석 목표: 모든 명함을 넣을수있는 가장 작은 지갑 만들기 특수규칙: 명함은 회전할수있다. 전 이 문제를.. Set과 3차 반복문으로 40줄넘겨가면서 삽질하면서 풀었습니다... 가로와 세로에대한 틀에 너무 집중하시면 자칫하다 개고생합니다(하드모드). 가로: 두 변중에서 긴 부분 세로: 두 변중에서 작은 부분 이렇게 생각하시면 놀랍게도 정말 쉽게 풀리는 문제입니다. 그림으로 보실까요? 가로를 두 변중에서 가장 긴 부분으로 설정합니다. (모든 명함을 제일 긴부분으로 눕히는거죠) 세로를 두 변중에서 가장 작은 부분으로 설정합니다. 그후, 가로와 세로의 길이가 모두 들어맞게, Max(가로)와 Max(세로)를 설정하면 정말 쉽게풀립니다. 문제풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..

문제풀이 출력: 동물 타입, 동물의 갯수 테이블: amial_ins 카운트를 세기위한 동물 타입 그룹화 동물타입을 사전순으로 정렬 1 2 3 4 5 -- 코드를 입력하세요 SELECT animal_type,count(*) from animal_ins group by animal_type order by animal_type cs

문제분석 목표:헤비유저가 등록한 공간의 정보를 아이디순으로 조회하기 문제풀이 첫번째 접근 select * from places where host_id=헤비유저 order by id 헤비유저가 등록한 공간의 정보를 아이디순으로 조회하는걸 코드로 번역하면 이렇다. 두번째 접근 헤비유저인 사람들을 구하면된다. select host_id from places groub by host_id having count(host_id)>=2 헤비유저는 host_id를 그룹화해서, host_id의 갯수가 2개이상이면 헤비유저다. 헤비유저는 여러명이니, where host_id in ()으로 바꾼다. 1 2 3 4 5 6 7 8 9 10 select * from places where host_id in ( SELECT ..

문제분석 여러개의 숫자가있는 배열 numbers와 target이 입력으로 주어집니다. 목표: numbers의 숫자를 모두활용하여, + - 만으로 target을 만드는 경우의수를 세기 모든 숫자를 사칙연산중 +,-만을 활용하여 target이 나오는경우를 세주면된다. 사칙연산중 2개의 연산만 고려하면되니, 재귀함수를 활용하면 간단하게 풀수있다. 문제풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { boolean[] visited; int cnt=0; public int solution(int[] numbers, int target) { int answe..

https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 문제분석 문제가 길어서 링크로 대체합니다. 배열의 길이가 같은 enroll 과 referral이 주어집니다. 이 enroll은 판매자를 나타내고, referral은 판매자와의 상속관계를 나타냅니다. 배열의 길이가같은 seller와 amount가 주어집니다. seller는 수익을 낸 판매자를 나타내고, amount는 판매자의 칫솔갯수를 나타냅니다. 목표:모든..

https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 문제분석 문제가 길어서 링크로 대체하겠습니다. 문제설명은 가로,세로 길이가 주어진 2차원배열이 주어집니다. 2차원배열은 1부터 가로X세로까지 +1씩 채워져있습니다. 이 2차원배열을 쿼리[x1,y1,x2,y2] 에 따라 회전시키고, 회전이 종료하고 움직인 숫자들중 가장 낮은숫자를 answer 배열에 추가합니다. 모든 쿼리를 순회했다면, answe..

Heap의 원리를 응용한 PriorityQueue에 대해 알아봅시다. PriorityQueue에서 Queue를 보고 "그 FIFO(First In First Out)의 큐랑 비슷한건가?" 라고 생각하시기 쉬운데 아닙니다. PQ 는 우선순위를 먼저 결정하고 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조입니다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행됩니다. 말로만 설명하니 무슨소리인가 싶으니 그림을 가져오겠습니다. 예시로, PQ로 된, [2,3,5,7,9,10] 이 있다고 가정하고 생성하겠습니다. 보..

문제분석 목표: 모든 음식을 스코빌 지수 K이상으로 만들기 만드는법 : 가장낮은 음식 스코빌 +(두번째로 낮은 음식 스코빌)*2 문제는 정말 쉽다. 공식을 이용하여 모든 음식을 K이상으로만 만들면된다. 하지만, 제한사항을보면 어마어마한 길이의 스코빌이 주어진다. 만약, 별 생각없이 리스트 생성하고 매번 정렬 하면서 최솟값과 2번째 최소값을 구한다면 효율성 오류가난다. 문제를 풀기위해선, 가장 낮은 음식과 두번째로 낮은 음식을 섞은뒤 배열에 넣은뒤, 다시 오름차순 정렬해서 낮은 음식과 두번째 음식을 찾아야한다. 어찌됏건, 매번 반복할때마다 숫자를 넣고 정렬을 해야한다. 그런데 이 정렬을 매우빠르게 해주는 스마트한 녀석이있는데. 바로 자료구조의 Heap(힙)이다. 자바는 Heap을 응용한 PriorityQu..

문제분석 작업진도를 나타내는 progresses 배열 작업 스피드를 나타내는 speeds 배열이 주어진다. 문제를 풀기위해서 필요한 정보는 100%작업완료까지 걸리는 시간이다. 작업완료까지 걸리는 시간은 100-작업진도/작업스피드로(나머지가있으면 +1) 구할수있다. 작업완료까지 걸리는 시간을 모두구했다면, Current_Time을 선언한다. Currrent_Time이 작업까지 걸리는시간보다 적으면 갱신하고, 그렇지 않다면 작업갯수를 1올린다. 문제풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.util.*; class Solution { public int..