DevBoi

투 포인터의 대표 적인 예제는 아래와 같다. 리스트 A가 있고, 타겟값 S가 있다. 이 리스트에서 두수의 합이 타겟값 S가 되는 걸 찾는다고 가정하면? 리스트 1개씩 비교해 가면서 체크를 할수있겠지만. 리스트의 크기에 따라, 시간 복잡도는 정비례하게된다. 그러면 이럴 경우에는 ? 리스트를 정렬하고 투포인터 알고리즘을 사용하면 된다. 사용 방법은 아래 순서와 같다. 1. 리스트를 오름차순으로 정렬한다. 2. 포인터 left는 리스트의 시작점을 포인터 right는 리스트의 끝점을 가리킨다. 3. left 와 right가 만날때까지 다음을 반복한다. 3-1. left + right 의 합이 타겟 값과 같으면 출력, 3-2. left + right 가 타겟 값보다 작으면 left 1증가 3-3 left + ri..

최단 경로에 대한 알고리즘을 정리해보자. 엇 최단 경로면 BFS 아닌가? 응 아니야~ 그러면 시작해보자 특정 시작노드에서부터 가중치를 더해가면서 계산하는 다익스트라 알고리즘이라는 것을 써야한다. 다익스트라 알고리즘이란? BFS랑 유사하지만 조금 다른 개념이다. BFS는 단순 가장가까운 노드부터 계산해서 큐에 넣고 빼서 체크를 했다면 다익스트라는 가까운 노드만 업데이트를 하는것이다. 그래서, 우선순위 큐는 minHeap방식을 활용해서 가장 짧은 거리를 가진 노드 정보만 꺼내고 업데이트한다. 좀더 자세히 알아보자 * 최단 경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,..

이진탐색에 대한 공부를 시작한다. 이진탐색을 왜쓸까? 일단 이것부터 파악을 해야한다. 사실 순차 탐색 = 이진탐색 값을 구하는 건 동일하다. 결국 둘다 탐색을 해서 답을 도출해내는 건 동일하게 성공적으로 실행된다. 근데, 탐색해야되는 량이 엄청 많다면? 그때는 이진탐색을 실행한다. 우선 이진탐색에 대한 기초적인 구현을 시작한다. 아주 간단하게, 5개의 숫자를 입력받고, 그중에 target인 15를 찾는것이다. mid를 시작과 끝점을 합한 /2 를 하고, 만약의 mid index가 타겟보다 크면, 최고를 mid -1 로 이동 반대라면 low를 mid +1로하게된다. 물론 이 것은 입력값이 순차적은 정렬 형태를 띈다는 가정이다. 이렇게 되면 순차 탐색 보다 훨씩 빠른 탐색을 할수있다. 탐색 대상이 많은 경우..

DFS 깊이 우선 탐색이다. 어떤 노드나 행렬이 주어지면, 해당 노으나 행렬에 대한 값을 최대로 깊이 탐색하고, 그다음 노드로가는방법이다. 나는 그림으로 이해하는게 편해서 그림으로 남겨놓으려고한다. 그림이 좀 웃기지만 뭔가 이렇게 이해하는게 편하다 코드를 짤때 생각해야하는 구조로 다시 그려보자 우선 각 노드별로, ArrayList로 각 노드들이 가지는 인접한 것들을 구한다. 역시나 개떡같지만 ㅋ 이 걸 가지고 생각해보는 그림은 처음에 1부터 시작을 하면, 2로가고 2가 3으로가고 3에서 2로가려고하지만, 기존에 2에서 check를 해놨기 때문에 1로, 1도 체크해놨기 떄문에 4로 4는 모든걸 다 check가 되어있기 때문에 out이된다라고 생각하면 된다. 자 공부는 여기까지하고 예제 부터 풀어보자 htt..

우선 개념에 대해서 숙지 및 관련 유형 문제를 풀이한다. (문제는 , 백준 기준 - https://www.acmicpc.net/step 기준) 1. 브루트포스 완전 탐색 알고리즘, 가능한 모든 경우를 탐색 , 조건에 맞는 결과만 가져온다. 무식하게 탐색하는 방법, 100% 정답을 찾는다. * 블랙잭 문제 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 전형적인, 완전 탐색문제이다. 배열을 3중 for문을 사용해서..

브루트 포스 DFS BFS 시뮬레이션/ 구현 DP 그리디 이분탐색 투포인터 최단경로 다이나믹 프로그래밍 백트랙킹 Trie KMP 위상정렬 최소신장 트리 폴로이드 와샬 다익스트라 이정도 한번 달려보자!

1. 배열 선언 int[] a = new int[8] int[] a = {1,2,3,4,5} 2. 배열 -> 문자열 Arrays.toString(); Arrays.sort(배열) -> 오름차순 Arrays.sort(배열,Colections.reversOrder()) -> 내림차순 배열의 특정 범위만 빼기, Arrays.copyOfRange(배열,2,4) 3. char 배열 -> 문자열 : String.valueof 4.문자열 비교 str.startWith("a"); str.endWith("a"); str.indexOf("a"); str.subString(0,2); str.toLowerCase str.toUpperCase str.trim() str.charAt(i) -> i번째 문자 출력 StringBui..

쉽게말해서, 2진수로 변환하고, 해당 1간의 간격의 최대값을 구하는게 키포인트이다. 이진수로 변환하는건 라이브러리가있기 때문에 변환해서, 값 index를 배열에 넣고, 빼주고 -1 을 더 뺴준다. index가 3,2 일경우 11 이기때문에 gap은 0이기때문에

위장 문제 문제의 키포인트는 각각의 옷에 대한 카테고리는 같지만 이름은 다 다르다는것이다. key 로만 구분해서, 해당 값들을 카운트한 값들을 넣어주고, 각각 경우의수를 곱해준다. 상의3개 하의2개인 경우 3 * 2 6가지의 옷을 입을수 있고, 해당 케이스처럼 * 해준뒤에 다 벗을수있는경우가 포함되어있는 경우 1은 빼준다. 그리고 상의가 2개여도, 안입을수도있기 떄문에 (하의 1개만 입을수 있음) 해당 경우를 생각해서 가지수 +1 해서 곱해준다.

그리드 함수를 쓰는 체육복 문제이다. 난이도는 1이며, 푸는건 10분 정도 걸렸다. 우선 전체 탐색은 기본이고, 한번빌려줬으면, 해당 사람은 못빌려주니까, 다음 검색 조건에서 -음수대로 만들어야 한다. 그리고, 본인이 잊어버리고 여분이 있을수있으니, 우선 이 케이스는 먼저 음수처리를 하고, 전체 탐색을 진행 한다 일케하면, 빌려줌을 못받는 애들만 lost에서양수인채로 남아져있고, 나머지는 -99가 된다. 혹시 0의 인덱스에 걸려있을수도있으니 -1은 위험하다고 생각해서 -99로했다. 무튼 이렇게 되면 통과