본문 바로가기
반응형

Algorithm10

[2019 Kakao Blind] 무지의 먹방 라이브 이 문제는 예전에 파이썬으로 시도했으나 못풀었다... 그래서 그냥 넘어갔었는데 이번에는 도전을 했다. 하지만 역시나 실패... 후 왤케 몬하지!? :) 그래도 이번에는 정확성 테스트는 모두 맞았다. 하지만 효율성 테스트 0점. 내가 짠 소스 코드 내 소스는 아래와 같다. import java.util.Arrays; class Solution { public static void main(String[] args) { int[] foodTimes = {1, 1, 1, 1}; long k = 4; // int[] foodTimes = {4, 2, 3, 6, 7, 1, 5, 8}; // long k = 16; Solution sol = new Solution(); System.out.println(sol.so.. 2021. 4. 3.
[이코테] 만들 수 없는 금액 Python으로 코테 준비를 하다가 Java 실력이 너무나 부족한 것 같아서 그냥 Java로 바꿨다. 꽤나 오랫동안 코딩 테스트 준비를 했는데 발전이 없다. 이것은 분명 방법이 잘못 됐다. 기존에 풀고 풀이를 읽고 넘어가는 방식을 벗어나 블로그에 문제 리뷰를 작성하려고 한다. 하루에 적어도 1시간 30분 이상은 알고리즘에 대해 생각하는 시간을 갖자. 첫 문제는 '이코테 p.314 만들 수 없는 금액'이다. 이 문제는 난이도가 낮음에도 불구하고 풀지 못했다. 알고리즘 자체를 이해 못한 것 같다. 이번에도 풀지 못해서 이렇게 리뷰를 적게 되었다. 소스 코드 import java.util.ArrayList; import java.util.Collections; import java.util.Li.. 2021. 4. 2.
Binary Search 이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때, 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다. 이진 탐색은 위치를 나타내기 위해 시작점, 끝점, 중간점 변수를 사용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다. 1. 이진 탐색 방법 위에 정렬된 데이터 15개에서 76의 데이터를 찾는다고 해보자. step 1. 시작점은 [0], 끝점은 [14], 중간점은 [7]이다. 중간점에 위치한 데이터 47은 찾으려는 데이터 76보다 작으므로 47 이하의 데이터는 볼 필요가 없다. 따라서 시작점을 [8]로 변경한다. step 2. 시작점은 [8], 끝점은 [14], 중간점은 [11]이다. 중간점에 위치한 데이터 77은 찾으려는 데.. 2021. 2. 18.
Sort (Selection, Insertion, Quick, Count) 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열 하는 것을 말한다. 선택 정렬 (Selection Sort) 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정이다. 1. [7] 5 9 (0) 3 1 6 2 4 8 #가장 작은 0을 선택해 맨 앞에 있는 7과 바꾼다. 2. 0 [5] 9 7 3 (1) 6 2 4 8 #정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 1을 선택해서 처리되지 않은 데이터 중 가장 앞에 있는 데이터 5와 바꾼다. 3. 0 1 [9] 7 3 5 6 (2) 4 8 #정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 2을 .. 2021. 1. 28.
Dynamic Programming 다이나믹 프로그래밍은 동적 계획법이라고 표현하기도 한다. 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다. 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있는 방법이다. 1. 재귀 함수 예시 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. n번째 피보나치 수 = (n - 1)번째 피보나치 수 + (n - 2)번째 피보나치 수 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1 피보나치 함수를 구현하기 위해 가장 쉬운 방법으로 재귀 함수를 사용하면 된다. def fibo(x): if x == 1 or x == 2: return 1 return fibo(.. 2021. 1. 18.
Brute Force & Back Tracking 1. brute force란? Brute Force는 완전 탐색 알고리즘이라고 할 수 있다. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만 가지고 온다. 이 알고리즘의 장점은 예외 없이 100%의 확률로 정답만을 출력 할 수 있다. 1-1. 구조에 따른 brute force 종류 일반적인 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색 할 수 있는 방법을 필요로 한다. brute force에 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다. 선형 구조를 모두 탐색하는 방법은 가장 간단한 순차 탐색이 있다. 비선형 구조를 모두 탐색하는 방법은 BFS, DFS가 있다. 1-2. 정리 bru.. 2021. 1. 13.
반응형

티스토리툴바