Algorithm10 [Programmers] 등산코스 정하기(118669) - 자바(Java) https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🥕 문제 핵심 intensity : 휴식 없이 이동해야하는 시간 중 가장 긴 시간 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 출입구로 돌아오는 등산코스 위의 규칙을 지키면서, intensity가 최소가 되도록 등산코스를 정한다. intensity가 최소가 되는 등산코스가 여러 개라면 그 중 산봉우리의 번호가 가장 낮은 등산코스 선택 🥕 접근 방법 최단 경로라서 다익스트라.. 2022. 9. 20. [Programmers] 합승 택시 요금(72413) - 자바(Java) https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🥕 문제 핵심 두 사람(A, B)이 s에서 출발해서 각각의 도착 지점 까지 택시를 탄다고 가정할 때, 최저 예상 택시 요금 계산 합승하지 않고 각자 이동하는 경우의 택시요금이 낮다면 합승하지 않아도 된다! 🥕 접근 방법 A, B, s 지점에 대해서 모두 다익스트라를 한 후 최소 값을 구했다/ 🥕 문제 후기 다익스트라 문제인 건 알았는데 어떻게 사용해서 풀어야할지 조금 어려웠다. 🥕 코드 HTML .. 2022. 9. 20. [Programmers] 주차 요금 계산(92341) - 자바(Java) https://school.programmers.co.kr/learn/courses/30/lessons/92341 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🌱 문제 핵심 어떤 차량이 입차된 후에 출차된 내역이 없다면, 23:59에 출차된 것으로 간주 00:00부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 정산 누적 주차 시간 기본 시간 → 초과 시간에 대해 단위 시간 마다 단위 요금 청구 (올림) 🌱 접근 방법 차량 번호과 들어온 시간을 저장하는 HashMap과 차량 번호와 누적 주차 시간을 계산하는 .. 2022. 9. 20. [Programmers] 전력망을 둘로 나누기 (86971) - 자바(Java) https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🥕 문제 핵심 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있다. 이 전선들 중 하나를 끊어서 현재 전력망 네트워크를 2개로 분할 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞춰야 한다. 🥕 접근 방법 가장 연결된 것이 많은 것을 기준으로 끊는다. ➡️ 실패(몇개는 맞고 몇개는 틀림) 하나씩 다 끊어보기(완전탐색) 🥕 문제 후기 간단한 문제인데 오랜만에 알고리즘을 .. 2022. 8. 31. [Programmers] 추석 트래픽(17676) - 자바(Java) https://school.programmers.co.kr/learn/courses/30/lessons/17676 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🥕 문제 핵심 초당 최대 처리량은 요청의 응답 완료 여부에 관계 없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수 입력 로그 배열의 길이 N (1 2022. 8. 30. [Programmers] 피로도(87946) - 자바(Java) https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🥕문제 핵심 각 던전마다 탐험을 시작하기 위해 필요한 [최소 필요 피로도, 소모 피로도]가 있다 최소 필요 피로도 : 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도 소모 피로도 : 던전 탐험 후 소모되는 피로도 최소 필요 피로도 >= 소모 피로도 현재 피로도 k (1 2022. 8. 30. [알고리즘 이론] 최소 신장 트리(MST) - 크루스칼(Kruskal), 프림(Prim) 1. 최소 신장 트리(Minimum Spanning Tree) → 그리디(Greedy) 🌲 신장 트리 - n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 🎄 최소 신장 트리 - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 📍 그래프에서 최소 비용 문제 풀 때 사용 - 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 - 두 정점 사이의 최소 비용의 경로 찾기 2. 크루스칼(Kruskal) - 간선 중심[간선 리스트 사용] - 간선을 하나씩 선택해서 MST를 찾는 알고리즘 (1) 모든 간선을 가중치에 따라 오름차순으로 정렬 (2) 가중치가 가장 낮은 간선부터 선택, 트리 증가(if 사이클이 존재, 해당 간선 사용.. 2022. 2. 23. [알고리즘 이론] 서로소 집합(Disjoint Set) 1. 정의 - 서로 중복 포함된 원소가 없는 집합이다. - 즉, 교집합이 없다. - 하나의 특정 멤버(대표자)를 통해 집합을 구분한다. 2. 표현 방법 📕 연결리스트 - 같은 집합의 원소를 하나의 연결리스트로 관리 - 맨 앞의 원소를 집합의 대표 원소로 결정 - 대표자를 찾기 위한 검색을할 때 시간이 오래걸리기 때문에 각 노드에 대표자 노드를 가리키는 링크를 만들어준다. 📗 트리 - 같은 집합 원소를 하나의 트리로 관리 - 루트 노드를 집합의 대표 원소로 결정 3. 집합 연산 - MakeSet() : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산 - FindSet(x) : x를 포함하는 집합의 대표자를 찾는 연산 - Union(x, y) : x와 y를 포함하는 두 집합을 합치는 연산(합집합) 🪄.. 2022. 2. 23. [SWEA] 창용 마을 무리의 개수(2259) - 자바(Java) 1. 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 접근 방법 - 마을에는 N명의 사람이 살고있다. - 두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면, 이러한 사람들을 모두 다 묶어서 하나의 무리라고 한다. 📌 위의 내용을 봤을 때 서로소 집합 문제인 것을 알 수 있다. - 서로소 집합구현을 위해서 makeSet , findSet, Union 메소드를 구현한다. - 처음 group을 N으로 초기화해서 Unio.. 2022. 2. 22. 이전 1 2 다음
