전체 글
-
[프로그래머스] 그래프 - 순위알고리즘 공부/문제 풀이 2020. 9. 1. 23:11
그래프의 개념보다는 set의 개념을 이용하여 문제를 풀었다.. 블로그 https://velog.io/@ajufresh/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%88%9C%EC%9C%84-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-Java [프로그래머스] 순위 문제풀이 (Java) [프로그래머스] 순위 문제풀이 (Java) velog.io 를 참고하여 코드는 내가 작성한 것이다. package algorithmStudy; import java.util.*; class Player{ Set win=new HashSet();//player한테 이긴사람 Set lose=new HashSet();//player 진사람 } pu..
-
[프로그래머스] 그래프 - 가장 먼 노드알고리즘 공부/문제 풀이 2020. 9. 1. 20:42
풀이 방법 -변수 간선으로 연결된 노드들을 담는 Set list list에 포함된 노드와 연결된 노드들을 저장하는 Set temp 아직 list에 들어가지 않은 노드의 수 left 새롭게 추가될 노드 수 count (=temp.size()) 1. list에 1을 넣는다 2. 1과 연결된 노드들을 temp에 넣는다 바로 list에 넣지 않는 이유는.. 반복문에서 이 친구들을 포함해서 또 노드를 추가하고 추가해서.. 따로 만들어버렸다 그리고 Set인 이유는.. 중복으로 포함될 수 있기 때문이다. 3. 새로 추가된 노드들을 list로 옮겨준다 list.addAll(temp) 메서드를 이용했다 4. temp를 클리어 해준다. 5. 1~4 과정을 반복하되 left==0이면, 즉 모든 간선들이 list 배열에 추가..
-
[알고리즘 개념] 그래프알고리즘 공부/알고리즘 개념 2020. 9. 1. 19:40
그래프 정점(노드)와 간선(엣지)로 이루어진 자료구조 간선의 방향 유무에 따라 단방향 그래프와 무방향 그래프로 나뉜다. 그래프의 표현 인접 행렬 그래프 : 모든 정점에 대해 연결 유무를 표시한다. 직관적이며 쉽게 구현이 가능하지만, 불필요한 정보의 저장이 많으며 메모리 차지가 크다 인접 리스트 그래프 : 간선이 존재하는 곳만 표시한다. 필요한 정보만 저장하기 때문에 메모리 차지는 적지만, 구현이 어렵다. 그래프 탐색 BFS/DFS https://validming99.tistory.com/74 [알고리즘 개념] 깊이 우선 탐색(DFS)와 너비우선 탐색(BFS) 그래프 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종이다. G = (V,E) 세 가지 그림 모두 그래프이다. 트..
-
[프로그래머스] 이분 탐색 - 징검다리알고리즘 공부/문제 풀이 2020. 9. 1. 17:43
이 문제 또한 전과 마찬가지로 블로그를 보고 해결하였다. 문제 해결법은 전과 비슷했지만.. 해결 방법을 생각하는 것이 아직 어려운 것 같다 풀이방법 최소거리를 찾고, 그 최소 거리보다 작은 바위들을 제거한다. 제거된 바위 수가 n보다 크다면 거리를 좁히고, n보다 작다면 거리를 늘리며 최소 거리 중 최대 거리를 찾는다. import java.util.*; class Solution { public int solution(int distance, int[] rocks, int n) { Arrays.sort(rocks); int answer = 1; int start = 1; int end = distance; while (start n) { end = mid - 1; } else { start = mid ..
-
[프로그래머스] 이분탐색 - 입국심사알고리즘 공부/문제 풀이 2020. 9. 1. 17:16
https://syundev.tistory.com/170 참고하여 문제를 해결하였다. 문제를 읽고 왜 이게 이분탐색이지..? 생각했다. 아무리 이분 탐색으로 해결하려고 고민해도.. 각이 안 나와서 결국 서칭.. 나는 문제를 매 시점마다 처리하는 것으로 해결하려는 경향이 있다. 하지만 이러한 풀이법은 비효율적인 계산이 많다.. 역시나 이 문제도 시점마다 처리하는 것이 아닌 입국심사가 가능한 시간 중 가장 효율적인 시간을 찾는 것이었다. 이 때 사용한 개념이 이분 탐색이었다. 입국 심사가 가능한 시간 중 가장 효율적인 시간을 찾는 방법 해당 시간 안에 심사대마다 심사할 수 있는 사람의 수를 더해주어 n과 비교해준다. 이때 입국 심사가 가능한 시간은 가장 적은 시간부터 긴 시간으로 나열되어있기 때문에 이분 탐..
-
[알고리즘 개념] 이분 탐색 (Binary Search)알고리즘 공부/알고리즘 개념 2020. 9. 1. 15:20
이진 탐색 탐색이란 원하는 데이터를 배열 내에서 찾는 것이다. 이진 탐색은 정렬된 배열을 전제로 탐색하는 방법으로 한 번 비교할 때마다 절반의 데이터를 제외시킨다. 이러한 방법으로 엄청난 속도로 탐색을 완료할 수 있다. 예를 들어 70억 개의 데이터에 대해 순차 탐색은 평균적으로 35억 번을 비교하지만, 이진 탐색은 최대 33번의 비교로 데이터를 찾을 수 있다. 찾으려는 데이터와 중간 값을 비교하여 찾으려는 값이 중앙 값보다 작으면 왼쪽 데이터를 선택, 크다면 오른쪽 데이터를 선택하는 과정을 반복하며 데이터를 탐색한다. (중앙값) > (찾는 값) : 중앙 값 기준으로 왼쪽(작은 부분)을 탐색 (중앙값) < (찾는 값) : 중앙 값 기준으로 오른쪽(큰 부분)을 탐색 성능 이진 탐색의 성능을 계산해 보면 아..
-
[프로그래머스] 해시 - 베스트 앨범알고리즘 공부/문제 풀이 2020. 9. 1. 00:45
풀이 방법 1. map : 장르 key로 int[] value에 접근하는 해시맵 이때 int[0]은 조건 1을 비교하기 위한 total 재생 횟수를 담고 int[1],int[2]는 조건 2를 위한 고유번호를 담는다. *장르당 2개까지 노래를 담을 수 있기 때문에 int 배열의 크기는 3 numMap : 고유번호 key로 재생 횟수에 접근하는 해시맵 2. 매 반복문마다 total값과 가장 많이 재생된 고유번호를 갱신하며 map을 초기화 3. map의 value를 이차원 배열로 저장하여 int[0]값으로 내림차순 정렬 4. 장르의 노래가 한 곡일 때와 두 곡일 때를 구분하여 list에 저장 5. ArrayList인 list를 int 배열로 바꾸어 answer로. static int[] solution(Str..
-
[프로그래머스] 해시 - 위장알고리즘 공부/문제 풀이 2020. 8. 31. 18:43
문제를 읽고 예제를 이해하고 예제 풀이법 대로 고민을 한 다음 풀이를 작성했다. 예를 들어, 상의, 하의, 겉옷이 각각 3,2,1 개씩 있다면 3+2+1 + 3*2 + 3*1 + 2*1 + 3*2*1 이런 식으로 모든 수를 계산하려 하였다. static String result=""; static int solution(String[][] clothes) { int answer = 0; // 옷의 종류와 이름이 너무 길어 두개의 해시맵을 이용하여 character와 int로 처리 HashMap typeMap=new HashMap(); HashMap clothMap=new HashMap(); int charnum=97; //초기화 부분 for(int i=0;i