본문 바로가기

전체 글

 (121)
[JAVA] 백준 1916 - 최소비용 구하기 🤔 문제 접근 다익스트라 알고리즘의 대표 문제인 최단 경로 문제와 매우 똑같은 문제이다. https://daneng4-codingstory.tistory.com/66 [JAVA] 백준 13549 - 최단 경로 다익스트라 알고리즘을 공부하며 대표 문제인 최단 경로 문제를 풀어보았다. BFS와 비슷한 느낌이 들었지만 각 노드의 가중치의 최소를 계속해서 갱신해주는 것이 새로웠다. 🤔 문제 접근 각 노 daneng4-codingstory.tistory.com 위 문제와 로직은 똑같고 도착 정류장의 최소 비용만 구해주면 된다. 다익스트라 알고리즘 문제를 풀 땐 항상 1. 갈 수 있고 방문하지 않은 노드 중 가중치(비용)가 최소인 노드부터 탐색한다 2. 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. 이 두..
[JAVA] 백준 2108 - 통계학 🤔 문제 접근 구현 문제인 통계학 문제이다. 어려운 문제는 아니었지만 산술 평균쪽과 최빈값 계산에 있어서 살짝 헤맸다. 산술 평균을 구할 때 데이터 형식을 int로 하여 계산할 경우 예를 들어 전체 합 / N 의 값이 -1.8일 때 -1로 나올 수 있다. 따라서 double 형으로 계산하고 Math.round 메소드를 통해 소수 첫째자리에서 반올림 한 뒤 int 형으로 변환하여 값을 반환해주자. 또한 최빈값을 구하는 과정은 각 숫자들을 map에 집어넣고 가장 많이 나온 횟수인 maxCount를 구한 뒤, key의 value가 maxCount와 같은 key들을 찾아내도록 했다. 이때 key의 개수가 2개 이상이라면 두번째로 작은 값을 반환해주었다. key들을 구하고 다시 key들을 순회하며 2번째로 작은 ..
에라토스테네스의 체 - seive of eratosthenes 📗 에라토스테네스의 체 알고리즘 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 구하는 방법으로 프로그래밍 알고리즘에서 소수를 구할 때도 적용하여 사용한다. ✔️ 에라토스테네스의 체 알고리즘의 원리 에라토스테네스의 체 알고리즘의 원리는 "소수의 배수인 수들을 전부 제외하면 소수만 남는다" 이다. 다시 말하면 소수의 배수들은 전부 소수가 아니기 때문에 소수의 배수들만 전부 제외하면 소수만을 구할 수 있는 것이다. 🚨CODE // 에라토스테네스의 체 boolean[] prime = new boolean[n]; public static void SeiveOfEratosthenes(){ // true = 소수x , false = 소수 prime[0] = prime[1] = true; for(int i = 2; i
[JAVA] 백준 13549 - 최단 경로 다익스트라 알고리즘을 공부하며 대표 문제인 최단 경로 문제를 풀어보았다. BFS와 비슷한 느낌이 들었지만 각 노드의 가중치의 최소를 계속해서 갱신해주는 것이 새로웠다. 🤔 문제 접근 각 노드들의 가중치 정보는 Node 클래스를 하나 생성하여 저장하도록 했다. 뭔가 문제를 풀면서 느끼는 건데 주어지는 데이터 형식이 복잡해 어떤 자료구조를 사용해야 할지 애매하다면 클래스를 생성해서 데이터를 저장하는 형식이 좋은 것 같다. 그리고 다익스트라 알고리즘 매커니즘 상, 갈 수 있는 노드 중 아직 방문하지 않았고 최소 가중치인 노드들을 먼저 탐색해야 하므로 add할 때 마다 정렬 해주는 우선순위 큐를 이용했다. 이때 가중치가 정렬의 기준이 되므로 Node 클래스에서 Comparable를 상속 받고 정렬 조건을 가중치..
다익스트라 알고리즘 - Dijkstra 📗 다익스트라 알고리즘 DP를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. ✔ 왜 DP 문제? 다익스트라 알고리즘이 DP 문제인 이유는 "최단 거리는 여러 최단 거리로 이루어져있기 때문이다" 따라서 작은 문제가 큰 문제의 부분집합에 속해 있다고 볼 수 있다. 기본적으로 다익스트라는 "하나의 최단거리를 구할 때 그 이전까지 구했던 최단거리 정보를 그대로 사용한다"는 특징이 있다. 현재까지 알고있던 최단 경로를 계속해서 갱신해나간다. 📗 다익스트라 매커니즘 기본적으로 DP와 그리디 기법을 사용한다. 아래 두 단계를 반복해 임의의 노드에서 각 모든 노드까지 최단거리를 구한다. 1. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. (..
[SQL] 프로그래머스 - 평균 일일 대여 요금 구하기 🤔 배운 것 COLUMN 명을 임의의 이름으로 출력하는 방법, 소수점 반올림 방법 // DAILY_FEE를 가공한 데이터를 Alias 를 통해 임의의 COLUMN 명을 정의한다. // ROUND("COLUMN") 는 소수점 1번째 자리에서 반올림 한다. // ROUND의 2번째 파라미터는 생략 가능하며 DEFAULT VALUE = 0 (소수점 첫째자리) 이다. // 소수점 둘째자리부터 반올림을 하고 싶다면 ROUND("COLUMN", 1)로 작성하면 된다. SELECT ROUND(AVG(DAILY_FEE), 0) AS AVERAGE_FEE // CAR_RENTAL_COMPANY_CAR 테이블에서 데이터 조회 FROM CAR_RENTAL_COMPANY_CAR // CAR_TYPE 이 SUV인 차량 조회 W..
[SQL] 프로그래머스 - 재구매가 일어난 상품과 회원 리스트 구하기 🤔 배운 것 COLUMN 들을 그룹화 하기 : GROUP BY 그룹의 조회 조건을 세우기 : HAVING COUNT, AVG, SUM, MAX, MIN등으로 조회한 데이터의 양, 평균, 합, 최대, 최소를 구할 수 있다. // USER_ID 와 PRODUCT_ID를 COLUMN으로 하는 테이블을 만들 것이므로 SELECT USER_ID, PRODUCT_ID // ONLINE_SALE 테이블에서 조회할 것이므로 FROM ONLINE_SALE // 어떤 USER가 재구매한 내역을 조회할 것이기 때문에 GROUP BY 1,2 -> USER_ID, PRODUCT_ID 와 동일 // 재구매 한 물품이면 해당 USER가 구매한 PRODUCT_ID가 2개 이상일 것이므로 // 그룹화 한 것의 PRODUCT_ID > ..
[SQL] 프로그래머스 - 3월에 태어난 여성 회원 목록 출력하기 🤔 배운 것 SQL 문에서 DATA FORMAT을 설정하는 것, COLUMN 값이 NULL인 경우 출력 대상에서 제외하는 것 // 전체 COLUMN 에서 4가지 COLUMN만 조회한다 SELECT MEMBER_ID, MEMBER_NAME, GENDER, DATE_OF_BIRTH FROM MEMBER_PROFILE; // 이때 DATE_OF_BIRTH의 DATA_FROMAT을 년-월-일로 맞춰줘야한다. // 풀면서 알게된 것인데 %대문자 인 것과 %소문자 인 것이 다르다 // 예) %M 이 3월이면 'march', %m이면 03 이라고 결과가 출력된다 SELECT MEMBER_ID, MEMBER_NAME, GENDER, DATE_FORMAT(DATE_OF_BIRTH, '%Y-%m-%d') FROM MEMB..
반응형

티스토리툴바