알고리즘 공부/문제 풀이
-
[프로그래머스] 깊이 우선 탐색 - 타겟 넘버알고리즘 공부/문제 풀이 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..
-
[프로그래머스] 동적계획법 - 등굣길알고리즘 공부/문제 풀이 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 ..
-
[프로그래머스] 탐욕 알고리즘 - 단속카메라알고리즘 공부/문제 풀이 2020. 8. 18. 23:40
public static int solution(int[][] routes) { int answer = 0; // routes[0] 오름차순 정렬 Arrays.sort(routes,new Comparator() { public int compare(int[] o1,int[] o2) { return o1[0]-o2[0]; } }); int point=routes[0][0]; int pre_count=0;// 전에 센 값 while(point Integer.compare(a[1], b[1])); int camera=-30001; for(int[] route:routes) { if(camera
-
[프로그래머스] 탐욕 알고리즘 - 섬 연결하기알고리즘 공부/문제 풀이 2020. 8. 18. 17:01
문제를 읽고 최소 스패닝 트리를 만드는 문제라는 것을 알았고 크루스칼 알고리즘을 이용하였다. static int solution(int n, int[][] costs) { int answer = 0; ArrayList in=new ArrayList(); int[][] adj = new int[n][n];//인접한 섬들을 알려주는 배열, 0으로 초기화 상태 for(int i = 0; i < costs.length; i++) { //선은 양방향 adj[costs[i][0]][costs[i][1]] = adj[costs[i][1]][costs[i][0]] = costs[i][2]; } in.add(0); while(in.size()
-
[프로그래머스] 탐욕 알고리즘 - 조이스틱알고리즘 공부/문제 풀이 2020. 8. 18. 15:02
public static int solution(String name) { int answer = 0; char[] arr = name.toCharArray(); char[] temp=new char[arr.length]; int left = 0, down = 0, up = 0, right = 0; char check; // 진행방향 나타내는 변수 //temp 초기화 for(int i=0;i 0; i--) { if(arr[i] !='A') { right=i; break; } } //더 적은 수로 check 초기화 check = right