알고리즘 공부
-
[알고리즘 개념] 해시 알고리즘알고리즘 공부 2020. 8. 28. 21:27
해시 함수 어떤 길이의 데이터를 입력해도 정해진 길이의 결과를 주는 함수 여기서 정해진 길이는 256 bits로 input의 길이에 관계없이 output의 길이는 일정하다. 해시 함수의 특징 - 데이터의 입력의 길이에 제한이 없다 - 결과는 정해진 256bits의 길이를 가진다 - 결과값이 중복될 가능성이 거의 없다 - 결과값을 가지고 입력값을 유추할 수 없다 해시 알고리즘 크기가 U인 테이블 T를 생성하고 key k를 slot h(k)에 저장하는 방식이다. 이때 key의 중복은 없어야 한다. key k가 slot h(k)로 해쉬 되었다고 하며 h(k)를 key k의 해쉬 값이라고 부르고, h()가 해쉬 함수이다. slot의 크기는 무한하지 않기 때문에 h(k)의 값이 중복되어 나타날 수 있다. 이 경우..
-
[프로그래머스] DFS/BFS - 단어 변환알고리즘 공부/문제 풀이 2020. 8. 25. 23:11
단어를 만들 수 있는 가장 적은 변환 횟수를 리턴하는 문제라 너비 우선 탐색을 이용하겠다고 생각하였다. 탐색 구현까지는 어쩨 저쩨 했는데 최소 횟수를 어떻게 구하나 막막하던 쯤 Node를 만들기로 하였고 Node 클래스를 만들어 문제를 해결하였다. package algorithmStudy; import java.util.*; class Node{ String val; int level; public Node(String v,int l) { val=v; level=l; } } public class dfsbfs { static boolean check(String a,String b) { int num=0; for(int i=0;i
-
[프로그래머스] 깊이 우선 탐색 - 타겟 넘버알고리즘 공부/문제 풀이 2020. 8. 25. 13:23
numbers의 배열을 가지고 target을 만드는데 필요한 연산은 +-이다. 따라서 연산의 순서는 결과 값에 영양을 끼치지 않는다. 가능한 모든 경우를 그래프로 표현하면 이진트리가 만들어진다. 마지막 레벨에서 target과 값이 같으면 +1이고 값이 다르면 다른 것을 탐색하면 된다. 나는 깊이 우선 탐색과 이진 트리를 이용하여 문제를 해결해야 겠다는 생각을 하고 무식하게.. 이진트리를 코드로 만들었다.. 그랬더니 스택오버플로우 에러... 아직 재귀 함수 호출하는 코드를 짜는 것이 어렵게 느껴진다. package algorithmStudy; public class dfsbfs1 { static int current=0; static int[] arr; static boolean[] check; stati..
-
[알고리즘 개념] 깊이 우선 탐색(DFS)와 너비우선 탐색(BFS)알고리즘 공부/알고리즘 개념 2020. 8. 25. 12:03
그래프 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종이다. G = (V,E) 세 가지 그림 모두 그래프이다. 트리 또한 그래프 중 하나이며 정점과 간선의 관계에 따라 세부적으로 구분할 수 있다. 그래프 탐색 그래프를 탐색한다는 것은 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 깊이 우선 탐색과 너비 우선 탐색은 그래프를 탐색하는 방법 중 하나이다. 깊이 우선 탐색 : DFS (Depth-First Search) 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동. 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 모든 노드를 방문하고자 하는 경우 깊이 우선 탐색이 적합하다..
-
[프로그래머스] 동적계획법 - 등굣길알고리즘 공부/문제 풀이 2020. 8. 24. 13:35
풀이방법 1. 중학교 때인가 배웠던 것처럼 숫자를 합하는 방식으로 진행한다. 1 1 1 1 2 3 4 1 3 6 10 2. 갈 수 없는 곳은 -1, [m][0],[0][n] 에는 1로 초기화한다. (나머지는 자동 0 초기화) 1 1 1 1 -1 0 0 1 0 0 0 3. 만약 [m][0],[0][n]에서 -1값이 있다면 그 다음 칸들은 절대 갈 수 없다 ((0,2)가 -1인 경우 (0,3)도 -1이 될 수밖에 없음) 1 -1 -1 1 -1 0 0 1 0 0 0 4. 0인 칸들을 계산한다 map[i][j]=map[i-1][j]+map[i][j-1] 5. -1인 칸은 0으로 바꿔준뒤 다음 칸으로 넘어간다. static int solution(int m, int n, int[][] puddles) { int[..
-
[프로그래머스] 동적 계획법 - 정수 삼각형알고리즘 공부/문제 풀이 2020. 8. 23. 23:33
이 문제는 지난 컴퓨터 알고리즘 수업시간에 설명을 들은 적이 있다.. 그거와는 별개로 기억나지 않는 풀이법.. 그래서 동적계획법을 이용하여 어떻게 해결할까를 고민하니 거꾸로 올라가자라는 생각이 떠올랐고 맨 아래줄을 제외한 아랫줄에서 부터 새로운 정수 삼각형을 만들어 그 삼각형에서 만들 수 있는 가장 큰 수를 저장하게 하였다. static int solution(int[][] triangle) { int answer = 0; for(int i=triangle.length-2;i>=0;i--) {// 맨 아랫줄의 바로 윗줄서부터 for(int j=0;j
-
[프로그래머스] 동적 계획법 - N으로 표현알고리즘 공부/문제 풀이 2020. 8. 23. 13:59
... 처음에는 각각의 수에 대해 몇개의 N으로 표현가능한가 점화식도 세워보고.. 규칙성도 찾으려 했으나.. 너무 어려워서 포기 그래서 결국 풀이를 서칭해봤다. 핵심은 i개의 N으로 표현 가능한 수들을 찾고 number가 그 안에 포함되어있는 지를 체크하는 거였다. 참고 : https://dheldh77.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-N%EC%9C%BC%EB%A1%9C-%ED%91%9C%ED%98%84 [프로그래머스] N으로 표현 문제설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 ..