감자는 아직 꿈을 꾼다.

알고리즘 : 벨만 포드 알고리즘다익스트라 알고리즘과 달리 음의 가중치인 경우에 최단경로 구하기가 가능하다.하지만 다익스트라 알고리즘에 비해서 모든 간선을 다 확인하므로 O(V * E)로 시간복잡도가 느리다.또한 음의 순환의 확인이 가능하다.음의 순환이 존재하면 최단경로는 구할 수 없다.문제https://www.acmicpc.net/problem/11657내 풀이기본적인 벨만포드 알고리즘으로 풀었다.풀다보면 38프로에서 출력초과가 뜨는 경우가 있는데이 조건에서 n= 500,m = 6000인 경우 모든 간선이 -10000 일 경우 최단경로 값이 -30억이 나올 수 있기에 Int오버플로우가 발생하는 경우 일 것이다. 이는 dist 배열을 Long 타입으로 선언하여 해결 할 수있다.package com.exam..

알고리즘 설명 : 다익스트라 알고리즘최단 경로 알고리즘을 사용한다.다익스트라 알고리즘은 한 정점에서 다른 모든 정점에 대한 최단 경로를 정하는 알고리즘이다.여기서 최단 경로란 상황에 따라서 달라진다.가중치가 있을 경우 가중치의 합이 가장 작은 길이 최단 경로이고,가중치가 없을 경우 간선의 갯수가 가장 작은 길이 최단 경로다.문제 설명https://www.acmicpc.net/problem/1753시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율1 초 256 MB 224898 69029 35315 25.902%문제방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.입력첫째 줄에 정점의 개수 V와 간선..

Comparable 와 Comparator클래스의 데이터 멤버를 사용해서 객체를 정렬하기 위한 인터페이스간단한게 표현하면 이렇다.자바의 기본 자료형들로 Collection이나 Array가 이루어져 있을 경우 기본적인 sort함수 호출로도 정렬이 가능하다.하지만 우리가 생성한 객체에 대해선 불가능하다.그 이유는 자바가 비교 기준을 모르기 때문이다.우리가 만든 클래스에 대해 비교 기준을 알지 못하므로 우리는 비교 기준을 정의해야된다.Comparable과 Comparator는 비교 기준을 정의한 것Comparator객체 정렬기준을 외부에서 지정한 것주로 하나의 객체를 여러가지 기준으로 정렬할 때 사용된다.util패키지에 존재하므로 Import해줘야된다.Comparable객체 자기 자신이 정렬 기준을 가진 것자..

알고리즘 : 트리 구조 떠올리기별다른 알고리즘 보단 간단한 아이디어 문제 같다.문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr    내 풀이가장 단순한 풀이가 아닐까 생각한다.우선 처음에는 부모와 자식노드들의 리스트로 클래스를 구성하여 구현할 생각이였으나,결국 판매액을 구한 다음, 자신의 추천인(부모)에게 수수료를 제공하는 방식으로 진행됨 생각해단순하게 부모 만 저장하는 HashMap을 만들어서 활용했다.결국 루트인 민수한테 가는 것까지 고려서 10프로만 먹는 구조이기에while문으..

JAVA 언어를 사용합니다.순열과 조합은 항상 간단한 것 같으면서 나를 헷갈리게 하였고, 이 참에 정리를 하려고 한다.백트래킹순열서로다른 수에서 뽑아서 정렬하는 경우의 수정렬이기에 순서가 존재한다.조합서로다른 수에서 뽑을수 있는 조합의 수순서가 중요하지않고 중복이 없다,아래의 코드는 순열,중복순열,조합,중복조합의 기본 형태를 나타내었다.중요한 것은 이러한 기본코드를 이해해야지 조합이나 순열을 활용해서 문제에 맞게 풀어 낼 수있다는 것이다.조합을 활용한 풀이는 아래 링크에 있다. 확인해보는 것을 추천한다.https://dreaming-potato.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv2-%EB%A9%94%EB%..

알고리즘 : 해시 + 조합처음엔 비효율적으로 각 String을 character 변환시켜 set에 저장하여 수행했다.이후엔 조합으로 풀이를 진행했다.문제 설명레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메..

알고리즘 : 간단한 정렬?? + Hash사실상 정렬 문제로 도 무방할 정도인 것같다.별다른 알고리즘이 들어가진 않는 거 같다.그리고 다른 사람 풀이를 보면서 댓글을 봤는데 사람들이 이 문제를 지저분한 문제라고 생각하는 것 처럼 보였다.하지만 삼성코테를 준비해보면서 느낀건데 이정도면 귀여운 수준인거 같다.LV3 난이도의 문제는 아닌거 같다.문제 설명스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.속한 노래가 많이 재생된 장르를 먼저 수록합니다.장르 내에서 많이 재생된 노래를 먼저 수록합니다.장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.노래의 장..

알고리즘 : 배열 활용별다른 알고리즘이 존재 하진 않는다. https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 설명프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작..

알고리즘 : 큐 or 연결리스트https://www.acmicpc.net/problem/1158     문제 설명문제요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.두 가지의 풀이 방법이 있다.1. 큐큐를 사용해서 푸는 것이 제일 연상하기 쉬운 풀이 방법이다.하지만 메모..

알고리즘 : 스택 + 배열로 구현한 리스트문제 설명링크 참조 https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  기존 풀이처음 문제를 보자마자 나는 change라는 삭제되었는지 안되었는지를 표시하는 배열을 선언하고인덱스만 이리저리 움직이면서 stack을 활용해서 풀 수 있을줄 알았다.하지만 최종 코드를 작성하고 답을 제출하니 정확성 테스트 통과 및 일부 효율성 테스트 통과 했다.시간초과도 발생하였고, 잘못된 알고리즘으로 코드를 작성했음을 깨달았다.배열은 삽입과 삭제시 원하는 위치까지 탐색을 진..