찰떡개발자 코딩

이전부터 궁금했던 조합 알고리즘. 조합이란 ...? nCr n개의 숫자중 r개를 뽑아서 만들수있는 조합을 구한다.... 예를 들어 [1, 2, 3] 이란 숫자 배열에서 만들수있는 조합은 [1, 2] [1, 3] [2, 3] [1,2,3] 이된다. 순열을 뽑았을 때 나오는 [2, 1] [3, 1] [3, 2] 등은 중복이라서 제거된다. 일단 기본적으로 알고리즘을 먼저 보자... public class combination { public static void main(String[] args) { //ABCD 4개를 받아서 조합을 만든다. String[] arr = {"A", "B", "C", "D"}; //자리수별 체크 1개뽑을때부터 n개 다 뽑을때까지 //n개중에 i개 뽑기 //2개부터 뽑자 boole..

그리디 알고리즘 문제 2번째 - 백준 개미 문제 : https://www.acmicpc.net/problem/4307 4307번: 개미 개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된 www.acmicpc.net 풀이 : 괜히 복잡하게 생각했다가 낭패봤던 문제.... 간단하게 풀이를 설명하자면. 개미가 만나서 반대로 돌고 하는 부분을 생략하고 생각하면된다. 함정....! 결국 최소 시간= 개미들이 다떨어지는 시간 = 끝에서 가장 멀리있는 개미의 위치 = 1개미 마다 양끝에서의 거리를 재서 가장 짧은 거리를 기준으로 temp를 만든다. => 그 temp..

최적해를 구하는 데에 사용되는 근사적인 방법, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식이다. 하지만 선택들을 계속 수집해서 최종적인 해답을 얻었을 경우 이 해답이 최적의 답이라는 보장은 없다. 적용이 잘되는 경우 1. Greedy Choice Property (탐욕 선택 조건) 앞의 선택이 이후 선택에 영향을 주지 않는 경우. 즉, 각 사건들이 서로 독립적일 때 잘 맞는다. 2. Optimal Substructure (최적 부분 구조 조건) 문제에 대한 최적해가 부분 문제에 대해서도 최적인 경우 이문제는 쉬운 문제다 그리디가 뭐지? 하는 나도 풀었던 문제 정리.. 문제 : https://www.acmicpc.net/problem/5585 5585번: ..

아 엄청 헤맨 문제.... 결국 풀이를 보고말았다... 다른분들은 아주 심플하게 푼것같다. 내 나름대로 정리를 해놓으려고 한다. 1). 우선 Class를 따로 빼서 관리할수 있도록 만든다. 무게와 진입시점을 담고있는 아이를 Queue에 넣어서 진행 시킬것! class Truck { int weight; int entry; Truck(int weight, int entry){ this.weight = weight; this.entry = entry; } } 2). 여기서 중요한 부분은 기다리는 Truck Queue와 다리를 지나는 Truck Queue로 구분짓는다. 다리에 진입하는 시점의 시간을 트럭Class객체에 담아 queue에 넣어준다. 트럭의속도는 1임으로 시간이 지날때 지나가는 Queue에 있는 ..

BFS 정의 BFS는 현재 위치에 인접한 모든 위치의 노드를 방문하고, 그 이웃 노드들의 또 다른 이웃 노드들을 방문하는 것은 그 다음에 진행하는 것을 의미. 큐를 이용해서 순환적 형태로 구현하는 것으로 공부해보려고 한다. BFS 넓이 우선 탐색 (Breadth Fisrt Search) "근처부터 확인하자"와 같이 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 알고리즘이다. 시작 정점을 지나고 나면 깊이가 1인 모든 정점을 방문하고, 그다음에는 깊이가 2인 모든 정점을 방문한다. 2..3..4... 이런식으로 나중에는 더 이상 방문할 곳이 없을 때 탐색을 종료 * 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 * 사용하는 경우:..

이번에는 코딩테스트에 자주 출몰한다고하는..? DFS 알고리즘을 공부해 보려고한다. 비전공자로 시작한 만큼 하나하나 꾸준하게 나만의 공부를 하는것이 중요하다...! 시간날때마다 어떤것이든 하나씩 공부를 하는 습관을 길들이며... DFS 깊이 우선 탐색 (Depth Fisrt Search) "더 나아갈 길이 보이지 않을 때까지 깊이 들어간다"를 원칙으로 그래프 내의 정점을 방문하는 알고리즘 분기가 여러개가 있을때, 분기별로 끝까지 탐색해보고 이어진 다음 노드가 없을경우 다음분기로 넘어가는 방법이다. 완전 탐색 알고리즘에서 사용한다고 하는데, 자세하게 언제 어떻게 사용하는지는 알고리즘을 공부하고 난뒤 알아보도록 하자! 구현 방법 2가지 1). 순환 호출 이용(재귀) 2). 명시적인 스택 사용 - 인접한 정점..

알고리즘에 대해서 너무 모르는것 같아 하나씩 시간 날때마다 공부해 보려고 한다. 이진탐색 알고리즘이란 정렬되어 있는 자료들의 집합에서 특정 자료를 찾고자 할 때 많이 사용 이진 탐색은 '퀵정렬'과 유사하게 '분할 후 정복(divide and conquer)'의 전략을 사용 실행시간은 log 특히 문제의 크기를 정확히 양분하는 경우에는 최악의 경우 logN의 성능을 보장한다. 이진 탐색의 탐색 시간은 'T = K * logN'으로 O(logN)이다. 선형 탐색의 시간보다 상당히 빠르지만 이진 탐색은 반드시 정렬이 되어있어야 한다. 정렬하는 비용이 든다는 단점이 있다. 다음과 같은 상황에서 이진 탐색은 효율적인 성능을 제공한다. 1) 새로운 자료가 추가되었어도 모든 자료가 재정렬이 일어나지 않는 경우 -> ..

여러가지 정렬 알고리즘 중 선택정렬, 버블정렬, 삽입정렬에 대해 정리를 해보려고 한다. 1). 삽입정렬 (Insortion Sorting) : 삽입정렬은 기준이 되는 인덱스의 앞쪽을 검사하여 기준이 되는 인덱스가 들어갈 자리를 찾아서 삽입하는 정렬이다. class Sort { public List sortNum(int[] arrs) { List list = new LinkedList(); loop:for (Integer num : arrs) { for (int i = 0; i num) { list.add(i,num); continue loop; } } list.add(num); } return list; } } public class TE..

1). 문제 : www.hackerrank.com/challenges/minimum-absolute-difference-in-an-array Minimum Absolute Difference in an Array | HackerRank Given a list of integers, calculate their differences and find the difference with the smallest absolute value. www.hackerrank.com 2). 풀이 : 2중 For문으로 처음에 풀었다가, Timeout으로 TestCase 몇개가 걸렸다. 아래 풀이의 KeyPoint는 인접한 값의 차이 = 최소값 이라는 점이다. import java.io.*; import java.math.*..

1). 문제 : www.hackerrank.com/challenges/sherlock-and-valid-string Sherlock and the Valid String | HackerRank Remove some characters from the string such that the new string's characters have the same frequency. www.hackerrank.com 2). 풀이 : import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*; p..