여러 포스트를 보고 안드로이드와 깃은 연동하려 했으나 안드로이드 스튜디오에서 깃 계정이 등록이 안되는 오류에 부딪히고 말았다. 그런 경우 토큰을 받아 하면 된다는데, 귀찮아서 이것저것 만지다 보니 됐다. 내 포스팅을 보고 다른 사람들도 도움을 받았으면 좋겠다.
새 안드로이드 프로젝트 만들기
일단 프로젝트를 만들자.
1
여기서 Create New Project를 클릭한다.
프로젝트 탬플릿 선택하기
2
어떤 것을 하던 상관은 없지만 일단 빈 액티비티로 만든다.
프로젝트 명 생성하기
3
프로젝트명을 생성해줍니다.
4
이제 프로젝트로 만든 폴더와 같은 위치에 gitignore을 생성한다. 프로젝트 폴더의 상위에서 터미널을 열어 위와 같이 touch .gitignore을 입력한다. 필자의 경우 SayHello위에 AndroidStudioProject가 있으므로 거기서 커맨드를 입력했다.
5
만들어진 파일은 커맨드+쉬프트+.으로 볼 수 있다. 이제 이걸 열고 ignore파일을 작성한다. ignore파일을 아래의 링크에서 만들 수 있다. 필자는 코틀린과 안드로이드 스튜디오를 넣었다.
https://www.toptal.com/developers/gitignore
이제 다시 안드로이드 스튜디오로 돌아간다.
6
프로젝트에서 VCS로 들어가 깃 레파지토리 생성으로 넘어갑니다.
7
Create Git Repository를 선택해 어떤 폴더를 깃과 연동할지 선택합니다. 필자는 AndroidStudioProject로 하였습니다. 만약 이 때 .ignore 파일이 보이지 않는다면 커맨드+쉬프트+.를 입력하면 볼 수 있다. .git이 보이지 않아도 괜찮다. 필자는 이미 연결한 상태라 그렇다. 여기서 Open을 누르면 빨갛게 파일명들이 바뀐것을 볼 수 있다.
8
파일명이 빨갛게 변한 상태에서 우측 상단의 초록 체크마크를 클릭한다.
9
그럼 왼쪽에 어떤 창이 나타나는데 커밋할 파일을 고르는 창이다. 이제보니 .gitignore가 여러개 생성이 되었는데, 앞에 것이 꼭 필요한 걸지 잘 모르겠다. 나중에 좀 더 뜯어봐야겠다.
10
모든 파일을 체크하고 커밋옆의 아래 화살표를 클릭하면 커밋 앤 푸쉬가 나타는데 이걸 클릭한다. 커밋 메시지도 함께 입력하는 것을 잊지말자!
11
뭐라뭐라 경고하는데 그냥 푸쉬한다고 한다.
12
그럼 어떤 창이 뜨는데 define remote를 클릭하면 url을 달라는 창이 이렇게 뜬다. 이때 레파지토리를 생성하여 URL을 입력한다.
//프로그래머스 문제풀이 level2 소수 만들기 publicstaticvoidmain(String[] args){ int[] nums = {1,2,3,4}; int answer = ReturnPrimeCnt(nums, 0, 0, 3); } publicstaticintReturnPrimeCnt(int[] nums, int idx, int sum, int cnt) { if(cnt == 0) { for(int i = 2; i <= Math.sqrt(sum); i++) { if(sum % i == 0) return0; } return1; } else { int res = 0; for(int i = idx; i <= nums.length-cnt; i++) { res += ReturnPrimeCnt(nums, i+1, sum+nums[i], cnt-1); } return res; } } }
숫자 3개를 뽑는 재귀를 이용해 문제를 풀었다. ReturnPrimeCnt는 다음과 같이 동작한다. 1. 만약 cnt가 0이면 3개를 다 뽑았다는 의미이므로 소수인지 판별한다. 필자는 에라토테네스의 체를 활용해 시간을 단축했다. 소수면 1, 아니면 0을 반환한다. 2. 아직 숫자를 더 뽑을 수 있다면 idx부터 nums길이 - cnt까지 숫자를 모두 뽑아본다. 경우의수에서 가지를 쳐나가는 것과 비슷하다고 생각하면 된다. for문의 범위는 중복없이 수를 뽑을 수 있게 한것이므로 앞으로의 코딩에도 참고하면 많은 도움이 될 것이다.
이 함수는 3개만 아니라 4개, 5개로 영역을 뻗어나갈 수 있다. 하지만 속도가 좀 느릴 수 있다. 이 문제에선 오히려 3중 루프가 더 빠르다.
BigInteger n1 = new BigInteger(Integer.toString(arr[0])); BigInteger n2 = new BigInteger(Integer.toString(arr[1])); BigInteger gcd = n1.gcd(n2); n1 = n1.multiply(n2).divide(gcd); for(int i = 2; i < arr.length; i++) { n2 = new BigInteger(Integer.toString(arr[i])); gcd = n1.gcd(n2); n1 = n1.multiply(n2).divide(gcd); } int answer = Integer.parseInt(String.valueOf(n1)); System.out.println(answer); } }
1. 두 수의 곱은 두 수의 최소공배수와 최대공약수의 곱과 같다. 2. 최소공배수는 모두의 배수이다.
이 두 가지만 알면 문제를 풀 수 있다. 2번이 무슨 말이냐고 할 수 있는데, 코드에 나와있는 것을 예시로 들면 2와 6의 최소공배수는 12이고 12와 8의 최소공배수가 24이고, 24와 14의 최소공배수는 168이다. 즉, 최소공배수를 앞에 두개씩 구해나가다보면 그것이 모든 수의 최소공배수가 된다는 것이다. 최소공배수를 구하는 방법은 1번식을 활용하면 된다.
이제 코드를 보자. 배열의 길이가 1인 경우에는 공배수라는 개념이 없으므로 원소 하나를 프린트하면된다. 그렇지 않은 경우 두 수의 촤대공약수를 구해 두 수의 곱에서 나눠주는 과정을 반복하면 된다.
최종 시간복잡도는 arr의 길이를 n이라 할 때 \(O(nlog_{2}n)\)이다. 왜냐하면 n번 동안 gcd를 사용하기 때문인데, 정확한 시간복잡도는 나와있지 않지만, 두 수를 a,b라 할때 한 쪽의 절반보다 크냐 작냐에 따라 연산이 달라지므로 \(log_{2}n\)이라 생각한다.
공백이 하나가 아니라 여러개인 경우 고려할게 좀 더 많아진다. 어쨌든 스페이스 한칸을 기준으로 단어를 쪼갠다. 이때 만약 공백이 여러개이면 아무것도 들어있지 않은 문자열이 생성된다. 이제 잘려진 문자열별로 처리를 해주면된다. 1. 들어온 문자가 아무것도 없는 경우 원래 입력이 공백이므로 공백을 버퍼에 넣은 뒤 넘어간다. 2. 문자열의 맨 앞이 영어가 아닌 경우(아스키 코드로 판단), 영문을 모두 소문자로 만든 뒤 버퍼에 붙여넣는다. 3. 만약 첫문자가 영문인 경우 첫번째만 대문자로 바꾸고 나머지는 소문자로 변환하여 붙인다. 4. 한 문자열 처리를 마칠 때 마다 공백을 붙인다.
이 처리가 끝나면 한가지 예외 케이스가 생긴다 바로 문자열의 맨끝에 공백이 있을 경우와 없을 경우를 잡아내지 못하는 것이다. 따라서 조건을 하나 더 추가하여 원래 문자열보다 작은지 큰지를 비교하여 작다면 공백을 추가하고 크다면 공백을 한 칸 제거한다.
최종 시간복잡도는 문자열 s의 길이를 n이라 할 때 \(O(n)\)이다.
테스트
공백 여러개를 처리하는 과정에서 약간 헤맸었는데, 다른 사람의 풀이를 보니 flag를 이용해서 코드를 더 간결하게 짠 것을 보고 감탄했다. 다음엔 나도 flag를 이용해 문제를 풀어야겠다.
int answer = 0; for(int n : price) { if(answer < n) answer = n; } System.out.println(answer); } publicstaticintReturnPriority(int p_rank, int s_rank, int m_rank, char c) { switch(c){ case'+': return p_rank; case'-': return s_rank; case'*': return m_rank; default: return -1; } } publicstatic Queue<String> ReturnPostfix(int p_rank, int s_rank, int m_rank, String expression) { Stack<Character> stack = new Stack<>(); Queue<String> q = new LinkedList<>(); StringBuilder buff = new StringBuilder(); for(char c : expression.toCharArray()) { if(c >= 48 && c <=57) buff.append(c); else { q.add(buff.toString()); buff.delete(0, buff.length()); if(stack.empty()) stack.push(c); else { int rank = ReturnPriority(p_rank, s_rank, m_rank, c); while(!stack.empty() && ReturnPriority(p_rank, s_rank, m_rank, stack.peek()) <= rank) { q.add(String.valueOf(stack.peek())); stack.pop(); } stack.push(c); } } } q.add(buff.toString()); while(!stack.empty()) { q.add(String.valueOf(stack.peek())); stack.pop(); } return q; } publicstaticintReturnPrice(Queue<String> q) { Stack<Integer> stack = new Stack<>(); while(!q.isEmpty()) { String s = q.poll(); try{ int n = Integer.parseInt(s); stack.push(n); }catch(NumberFormatException e) { int n2 = stack.peek(); stack.pop(); int n1 = stack.peek(); stack.pop(); if(s.equals("+")) stack.push(n1+n2); elseif(s.equals("-")) stack.push(n1-n2); else stack.push(n1*n2); } } return Math.abs(stack.peek()); } }
코드가 좀 긴 편인데 과정을 설명하자면 다음과 같다. 1. 중위표기식(infix)를 후위표기식(postfix)로 고친다. 2. 후위표기식을 계산하고 절대값을 반환한다. 3. 3가지 연산자로 만들 수 있는 모든 우선순위인 6가지에 대해서 1,2과정을 반복하고 가장 큰 값을 반환한다.
main에 있는 것이 3번과정이다. 우리는 1번과 2번에 대한 상세한 내용을 보려고 한다. 일단 중위표기식을 후위표기식으로 변환하는 코드를 살펴보자.
publicstatic Queue<String> ReturnPostfix(int p_rank, int s_rank, int m_rank, String expression) { Stack<Character> stack = new Stack<>(); Queue<String> q = new LinkedList<>(); StringBuilder buff = new StringBuilder(); for(char c : expression.toCharArray()) { if(c >= 48 && c <=57) buff.append(c); else { q.add(buff.toString()); buff.delete(0, buff.length()); if(stack.empty()) stack.push(c); else { int rank = ReturnPriority(p_rank, s_rank, m_rank, c); while(!stack.empty() && ReturnPriority(p_rank, s_rank, m_rank, stack.peek()) <= rank) { q.add(String.valueOf(stack.peek())); stack.pop(); } stack.push(c); } } } q.add(buff.toString()); while(!stack.empty()) { q.add(String.valueOf(stack.peek())); stack.pop(); } return q; }
받은 매개변수에 대해 간단히 살펴보면 p가 더하기 s가 빼기 m을 곱하기로 보면 된다. 이들에 대한 우선순위를 main에서 받아오는 것이며, 숫자가 작을 수록 우선순위가 높은 것으로 가정했다. expression은 중위표기식이다. 이제 중위표기식을 문자단위로 쪼갠다. 이 문자들을 살펴보면서 변환과정을 할 예정이다. for문의 첫번째 if문을 보면 c가 숫자인 경우 버퍼에다 문자를 담아준다. 주어진 식이 한자리 수만 주어진 것이 아니기 때문에 이렇게 한다. 만약 연산자가 주어진 경우 여태까지 버퍼에 담긴것이 한 숫자이므로 이를 스트링으로 바꿔 큐에 삽입한다. 삽입하고 난 뒤 버퍼에 있는 내용은 지운다. 이제 연산자에 대한 처리를 할 차례이다. 만약 스택이 비어있다면 연산자를 그대로 넣어준다. 그렇지 않다면 스택에 있는 연산자들과의 비교가 필요하다. 이들의 우선순위를 비교하여 우선순위가 자신보다 같거나 작다면 스택에서 꺼내서 큐에 넣는다. 이때, 우선순위가 같아도 꺼내는 이유는 같은 연산자일 때, 왼쪽에 있는 연산자가 더 우세하기 때문이다. 꺼내는 과정을 모두 마치면 해당 연산자를 넣는다(ReturnPriority에 대한 코드는 각자가 보길 바란다.). 모든 문자에 대해 이 과정을 마치면 버퍼에는 마지막 피연산자가 있으므로 이를 넣어주고 스택에 남은 모든 연산자를 꺼내어 큐에 넣어준다.
스택에서 푸쉬와 팝이 이루어지지만 전체 중위표기식의 길이를 n이라 할 때, 이것보단 미미한 수이므로 시간복잡도는 \(O(n)\)이다.
publicstaticintReturnPrice(Queue<String> q) { Stack<Integer> stack = new Stack<>(); while(!q.isEmpty()) { String s = q.poll(); try{ int n = Integer.parseInt(s); stack.push(n); }catch(NumberFormatException e) { int n2 = stack.peek(); stack.pop(); int n1 = stack.peek(); stack.pop(); if(s.equals("+")) stack.push(n1+n2); elseif(s.equals("-")) stack.push(n1-n2); else stack.push(n1*n2); } } return Math.abs(stack.peek()); }
연산은 간단하다 큐에서 원소들을 하나씩 빼서 숫자인 경우 스택에 넣는다. 만약 연산자인 경우 스택에서 두 수를 꺼내어 연산을 해준 뒤 다시 스택에 넣어주면 된다. 큐가 비어있으면 스택에 남은 원소 하나가 결과값이다(이 코드를 작성할 때 첫번째로 꺼내는 수가 n1이 아니라 n2라는 것에 주의하자.).
이 부분의 시간복잡도 역시 \(O(n)\)이라 볼 수 있다. 최종 시간복잡도는 \(O(n)\)이다.
테스트
후위표기식으로 변환하는 방법과 연산을 다 까먹어서 다시 공부하는데 애를 먹었다. 대학교 2학년 때 과제만 치중해서 원리를 제대로 공부하지 못한 내 자신이 살짝 원망스럽다. 그래도 이번 기회에 제대로 공부했으니 앞으로는 잊지 말아야겠다.
//프로그래머스 문제풀이 level2 피보나치 수 publicstaticvoidmain(String[] args){ int n = 5; int a = 0, b = 1, c = 0; for(int i = 2; i <= n; i++) { a %= 1234567; b %= 1234567; c = a+b; a = b; b = c; c %= 1234567; } System.out.println(c); } }
숫자가 자칫 커질꺼라 long을 쓸 수도 있는데 나머지 연산은 분배법칙이 통한다는 것을 알면 문제가 쉽게 풀린다. 일반적인 피보나치 수를 구하는 공식에 나머지 연산만 취해주면 된다.
