주정뱅이 개발자

요격 시스템

1. 문제코딩테스트 연습 - 요격 시스템 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  2. 설명간단하게 각 미사일의 끝 점을 기준으로 정렬을 하고, 미사일의 가장 끝에서 요격을 하면 된다.요격한 지점에 포함되는 미사일들은 요격된 것으로 처리하고, 요격 횟수를 올리지 않는다. 3. 코드public class Roket { public static void main(String[] args) { int[][] test = {{4,5},{4,8},{10,14},{11,13},{5,12}..

괄호 짝 맞추기

1. 문제'(', ')', '{', '}', '[', ']', '' 문자만 포함하는 문자열 s가 주어지면 입력 문자열이 올바른지 확인하여 결과를 출력하라.입력 문자열은 다음과 같은 경우에 유효하다: - 열린 괄호는 동일한 형식의 괄호로 닫아야 한다.- 열린 괄호는 올바른 순서로 닫아야 한다.- 모든 닫힌 괄호에는 동일한 유형의 열린 괄호가 있다. 제약 조건1 ≤ s.length ≤ 10⁴s는 '()[]{}'의 괄호로만 구성된다. 2. 코드public class MatchBracket { public static void main(String[] args){ //String s = "({[[]]})"; //String s = "({[[]]})>"; //String..

석유 시추

1. 문제코딩테스트 연습 - [PCCP 기출문제] 2번 / 석유 시추 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 2. 설명기본은 BFS 알고리즘을 통해 인접한 석유들을 구하면 된다.거기에 열마다 접근할 수 있는 석유의 총량을 저장하는 리스트 하나만 저장하면 된다.  먼저 BFS 알고리즘 적용을 위해서 visited와 queue를 사용했다.BFS의 알고리즘을 잘 모른다면 아래 글을 참조하면 된다. 너비 우선 탐색 (Breadth-First Search) (tisto..

Donut

1. 문제 코딩테스트 연습 - 도넛과 막대 그래프 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 설명 각각의 특성을 파악하는 것이 우선이다. 먼저 그래프의 그림을 보자. 그리고 예제에 해당하는 그래프를 보자. 각각의 특징들을 나열해보자. 생성된 노드 : 들어오는 간선은 없고, 나가는 간선이 2개 이상이다. 막대 모양 그래프 : 나가는 간선 1개 + (들어오는 간선 1개 & 나가는 간선 1개) * N + 들어오는 간선 1개 도넛 모양 그래프 : (들어오는 간선 1개 & 나가는 간선 1개) * N..

동적 계획법 (Dynamic Programming)

1. 동적 계획법이란? 하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 방법이다. 알고리즘이 아닌 하나의 문제 해결 방법으로 볼 수 있다. 예를 들어, 피보나치 수열을 일반적인 재귀로 구하려면, 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 된다. 동적 계획법으로 한번 구한 작은 문제의 결과 값을 저장하고 재사용한다면, 시간복잡도가 대폭 줄어들게 된다. 2. 사용 조건 2가지 조건을 만족해야 한다. Overlapping Subproblems ( 겹치는 부분 문제) DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용하여 전체 문제의 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다. Optimal S..

백트래킹 (Back Tracking)

1. 백트래킹이란? 답을 찾는 도중 답이 아니어서 막히게 되면, 되돌아가서 다시 답을 찾아가는 기법. 최적화 문제와 결정 문제를 푸는 방법이 된다. 2. DFS와 차이점 깊이 우선 탐색의 경우 가능한 모든 경로를 탐색한다. 따라서 불필요한 경로들도 다 탐색하게 되어, 경우의 수를 줄이지 못한다. 결국 N! 가지의 경우의 수를 가진 문제는 깊이 우선 탐색으로 처리가 불가능하다. 백트래킹의 경우 지금의 경로가 답이 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아간다. 반복문의 횟수를 줄일 수 있으므로 효율적이다. 이를 가지치기(Pruning)라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. N! 가지의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로..

깊이 우선 탐색 (Depth-First Search)

1. 깊이 우선 탐색이란? 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘. 깊이 우선 탐색은 재귀함수를 이용하기 때문에, 스택 오버 플로에 조심해야 한다. 후입선출의 특성을 가지므로 Stack이나 재귀함수 사용한다. 시작 노드를 방문 처리하고, 인근 노드 하나를 방문한다. 인근 노드의 인근 노드를 방문한다. 더이상 방문할 노드가 없을때까지 반복한다. 방문할 노드가 없으면 뒷 노드로 가서 방문하지 않은 노드가 있는지 확인한다. 방문하지 않은 노드가 있으면 방문을 하고, 없으면 한번 더 뒷 노드로 간다. 반복한다. 2. 사용처 특정 도시에서 다른 도시로 갈 수 있는지 확인할 경우. 전자 회로에서 특정 단자와 단..

너비 우선 탐색 (Breadth-First Search)

1. 너비 우선 탐색이란? 루트 노드 ( 혹은 다른 임의의 노드 )에서 시작하여 인접한 노드를 먼저 탐색하는 방법. 시작 노드로부터 가장 가까운 노드를 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 순회 방법. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. 깊이 우선 탐색보다 좀 더 복잡하다. 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 검사하지 않으면 무한 루프에 빠질 수 있다. 방문한 노드들을 차례로 정장한 후 꺼낼 수 있는 자료 구조인 Queue를 사용한다. 즉, 선입선출(FIFO) 원칙으로 탐색. 2. 사용처 최단 거리를 구해야하는 경우. 너비 우선 탐색은 현재 노드에서 가까운 곳부터 찾기 때문에, 경로 탐색 시 먼저 찾아지는 해답이 곧 ..

정렬 (Sort)

1. 선택 정렬 ( Selection Sort ) 선택된 값과 나머지 데이터를 비교하여 알맞는 자리를 찾는 알고리즘. 데이터 중 가장 작은 값의 데이터를 선택하여 앞으로 보내는 방법. 안정성 미보장. 시간복잡도는 O(N2)로 버블정렬과 같지만, 실제로 측정해보면 버블정렬에 비해 조금 더 빠르다. public static void selectionSort(int[] arr){ for (int i = 0; i < arr.length; i++){ int minIndex = i; for (int j = i; j < arr.length - 1; j++){ if(arr[j] < arr[minIndex]) minIndex = j; } int tmp = arr[i]; arr[i] = arr[minIndex]; arr[..

이진 탐색 (Binary Search)

1. Binary Search? 이진 탐색이란 정렬됀 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 데이터를 선택하여 찾고자하는 값 A와 비교한다. A가 중간 값보다 작으면 중간 값의 좌측 데이터들을 대상으로, A가 중간 값보다 크면 우측 데이터들을 대상으로 다시 탐색한다. A를 찾을 때까지 이 과정을 반복하면 된다. 2. Code public class BinarySearch { public static void main(String[] args){ int a = 3; int[] arr = {1, 2, 4, 5, 6, 7, 8}; System.out.println(solution(arr, a)); } public static int solution(int[] arr, int a){ i..