알고리즘31 [알고리즘] 프로그래머스 - 다음 큰 숫자 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. [알고리즘] [2020 카카오 블라인드] 괄호 변환 1. 문제 문제를 딱 보면 엄청나게 많은 조건들이 있다. 사람은 한번에 여러가지를 기억하지 못하기 때문에 조건을 이해하는데 시간이 오래 걸렸다. 2. 나의 풀이 문제를 봤을 때 재귀를 이용하는 문제라는 것을 알았다. 우선 문제의 조건대로 주어진 문자열의 길이가 0일 경우 빈 문자열을 반환하게 하고, 현재 문자열이 올바른 괄호 문자열일 경우 해당 문자열을 그대로 반환했다. 또한 문자열 u는 균형잡힌 괄호 문자열이므로 문자열 w를 u와 v로 나누어주는 getBalanceIndex() 메서드를 만들어 주었다. 여기서 return할 때 1을 더해주어 문자열 u와 v를 구분하는 인덱스를 구한다. 그리고 u가 올바른 괄호 문자열일 경우는 문자열 u에 v를 다시 나누는 재귀함수를 호출해서 더해준다. u가 올바른 괄호.. 2021. 1. 18. [알고리즘] [2020 카카오 블라인드] 문자열 압축 1. 문제 2. 나의 풀이 처음에 리스트에 단어를 넣지 않고 현재 단어와 다음 단어를 구해서 풀려고 했더니 인덱스를 벗어나는 등의 엄청난 시간 낭비가 있었다. 비효율적이지만 푸는게 우선이니 스트링 리스트를 먼저 하나 선언하고 리스트에 단어를 집어 넣는데, 마지막 단어의 경우는 남은 단어를 모두 넣도록 처리했다. 리스트에 넣은 단어가 현재 인덱스의 단어와 뒤의 단어를 비교해서 같을 경우 몇개가 같은지 개수를 세어 주었고, 같지 않은 경우는 count가 1일 경우와 1보다 클 경우로 나누어서 문자열 앞에 숫자를 붙여줄지 안붙여줄지를 정하였다. 그리고 마지막 단어의 경우는 마지막 단어와 그 앞의 단어가 같은 경우와 같지 않은 경우로 구분하여 숫자를 붙여줄지 안붙여줄지를 정하였다. import java.util.. 2021. 1. 18. 이전 1 2 3 4 ··· 6 다음
