Algorithm44 [알고리즘] 프로그래머스 - 다음 큰 숫자 1. 문제 2. 나의 풀이 처음에는 직접 binaryNumber를 구하는 메소드와 binary로 변환했을 때 1의 갯수를 구하는 메소드를 짰는데 효율성 테스트에서 실패하였다. 찾아보니까 Integer를 binaryString으로 바꿔주는 메소드와 Integer에서 2진수로 변환했을 때 1의 개수를 반환해주는 메소드가 있었다. 해당 메소드를 사용하니 효율성 테스트를 통과할 수 있었다. binaryString으로 바꾸는 부분의 경우 구현을 살펴보니 비트 단위로 조작하는 부분이 있었다. 이 부분은 좀 더 찾아봐야할꺼 같다. Integer.toBinaryString(n); Integer.bitCount(n); class Solution { public int solution(int n) { int answer .. 2021. 11. 20. [Algorithm] 공간 복잡도(Space Complexity) 1. 공간 복잡도란? 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻한다. 총 필요 저장 공간 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수 가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간 S(P) = c + Sp(n) c: 고정 공간 𝑆𝑝(𝑛)Sp(n): 가변 공간 고정 공간은 상수이므로 공간 복잡도는 가변 공간예 좌우된다. 2. 공간 복잡도 계산 공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 빅 오 표기법으로 표현한다. 2.1 O(n) 공간 복잡도 예시 n! 팩토리얼 구하기 재귀 함수를 통해서 구현하므로 변수 n에 따라서 변수 n이 n개가 만들어지게 됨 factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스.. 2021. 11. 15. [Algorithm] 시간 복잡도(Time Complexity) 1. 시간 복잡도란? 알고리즘의 로직을 코드로 구현할 때 시간 복잡도를 고려한다는 것은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?" 이다. 효율적으로 알고리즘을 구현했다는 것은 즉, 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화했다는 것이다. 시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다. 2. 시간 복잡도 표기법 Big-O(빅-오) ⇒ 상한 점근 Big-Ω(빅-오메가) ⇒ 하한 점근 Big-θ(빅-세타) ⇒ 그 둘의 평균 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다. 위 세가지중에서 보통 빅오 표기법을 통해서 알고리즘 수행 시간을 나타낸다. 최악의 경우도 고려하는 것이 바람직하기 때문이다. .. 2021. 11. 15. [알고리즘] 프로그래머스 - 올바른 괄호 (Stack) 1. 문제 2. 나의 풀이 전형적인 Stack 문제로 반복문을 통해서 문자열을 순회한다. 문자가 '(' 일 경우에는 Stack에 넣어주고 ')'일 경우에는 Stack에서 제거한다. 만약 더이상 제거할게 없는데 ')' 문자가 오면 올바른 괄호가 아니다. 또한 문자열을 모두 순회하고나서 Stack에 '('가 남아있다면 괄호가 제대로 닫히지 않고 끝났기 때문에 올바른 괄호가 아니다. import java.util.*; class Solution { boolean solution(String s) { boolean answer = true; Stack stack = new Stack(); int len = s.length(); for(int i=0;i 2021. 11. 15. [알고리즘] 프로그래머스 - 스킬트리 1. 문제 2. 나의 풀이 배울 스킬트리(skill_trees)와 선행 스킬 문자열(skill)이 주어졌을 때 해당 스킬 트리를 몇 개를 배울 수 있는지 반환하는 문제다. 코드를 보면 크게 어렵지 않다는 것을 알 수 있다. class Solution { private boolean[] visit; public int solution(String skill, String[] skill_trees) { int answer = 0; for(int i=0;i 2021. 3. 31. [알고리즘] 2018 카카오 블라인드 - 캐시 1. 문제 2. 나의 풀이 LRU 알고리즘을 이해하고 있으면 쉽게 풀 수 있는 문제이다. 캐시에 있으면 answer에 1을 더해주고, cache에 없으면 cache에 넣으면서 5를 더해준다. 여기서 주의해야할 점은 캐시에 있을 경우 해당 city를 cache Deque 맨앞으로 옮겨줘야한다는 것이다. 왜냐하면 가장 최근에 사용했기 때문이다. import java.util.*; class Solution { public int solution(int cacheSize, String[] cities) { Deque cache = new ArrayDeque(); int answer = 0; int len = cities.length; for(int i=0;i 2021. 3. 26. 이전 1 2 3 4 ··· 8 다음
