Mhwan
-
[알고리즘/투 포인터] 2020 카카오 인턴십 - 보석 쇼핑Mhwan's Study/Algorithms 2021. 1. 6. 21:39
본래 알고리즘 문제 같은 경우 따로 올리지 않으려 했지만, 꼭 알고 넘어가고 싶은 의미에서 올려봅니다. https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 이 문제도 투 포인터 기법을 활용한 방법으로 이 방법을 활용해야 효율성을 통과할 수 있습니다. 투 포인터 기법이란 아래 글에서 확인하시기 바랍니다 mhwan.tistory.com/57 [알고리즘/투포인터] 투포인터 알고리즘 투 포인터 알고리즘 또는 슬라이딩 윈도우 기법 또는 지렁이 알고리즘 등 이름이 참 많은..
-
[알고리즘/투포인터] 투포인터 알고리즘Mhwan's Study/Algorithms 2021. 1. 6. 20:00
투 포인터 알고리즘 또는 슬라이딩 윈도우 기법 또는 지렁이 알고리즘 등 이름이 참 많은 알고리즘입니다. 개인적으로 이 알고리즘과 인연이 깊습니다. 알고리즘을 공부하며 처음 소름돋았던 알고리즘이기도 하며 대충 공부했었는데, 운이 좋게도 얼마 지나지 않아 응시했던 Kakao 공채 1차 코테에서 이걸 활용해 풀었습니다. 이 문제 덕분에 제 첫 코테를 통과라는 기쁨을 누렸고, 그 이후 여러 코테에서 비슷한 유형으로 마주쳤던 기억이 납니다. 솔직히 매번 쓸때마다 헷갈렸는데, 이번 기회에 제대로 학습해 올립니다. www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[..
-
[알고리즘/Stack/Queue] Stack으로 Queue 구현, Queue로 Stack 구현Mhwan's Study/Algorithms 2021. 1. 6. 02:08
스택 2개로 큐를 만들 수 있고, 큐 2개로 스택을 만들 수 있다. 개인적으로 이 알고리즘을 처음 알았을 때 참신함에 소름이 돋았던 기억이 난다. 스택은 LIFO형태이고, 큐는 FIFO형태 이므로 들어오고 나갈때 저장된 순서를 뒤집을 수 있다면 스택으로 큐를 구현할 수 있고, 큐로 스택을 구현할 수 있다. 그래서 2개가 필요한것이다. # Stack으로 Queue 구현 (뺄때 다른 스택으로 옮겨서 빼자!) 두개의 스택인 A, B 스택이 있다. - enQueue : A스택에 push - deQueue : B 스택에 남은게 있다면 B에 있는 것을 pop하고, 남은게 없다면 A스택에 있는 것을 모두 pop해서 B로 push하고 B에 있는 것을 pop한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 1..
-
[알고리즘/Stack] 유효한 괄호가 있는지 판별Mhwan's Study/Algorithms 2021. 1. 6. 01:32
이것도 스택을 이용한 대표적인 알고리즘 중 하나이다. 유효한 괄호는 [(()){}] 와 같이 여는 괄호와 닫는 괄호의 갯수가 같고, 각 여는 괄호와 닫는 괄호의 짝이 맞아야한다. # 대략적인 과정 1. 여는 괄호가 나올 경우 Stack에 push 2. 닫는 괄호가 나올 경우 스택에 pop해서 비교한다. (닫는괄호와 여는 괄호가 서로 짝이 다르거나, 스택이 비어있다면 괄호의 개수가 맞지 않아 모두 유효하지 않은 괄호식인 것이다.) 아, 그리고 이 과정을 모두 반복했는데 스택에 남아있는 괄호가 있어도 짝이 맞지 않은 것이고, 스택이 비어있어야 유효한 괄호인 것이다. # 소스코드 12345678910111213141516171819public boolean checkParentheses(String str) ..
-
[알고리즘/Stack] 후위표기식으로 변환 및 계산Mhwan's Study/Algorithms 2021. 1. 6. 01:26
3+2*4-9/3의 연산 결과는 8이 나와야한다. 이는 중위표기식으로 표현한 식인데, 컴퓨터를 통해 각 연산자의 우선순위대로 계산을 하려면 후위표기식으로 변환해서 계산해야한다. 3+2*4-9/3 --> 324*+93/-으로 변환되고 이를 계산하면 8이 된다. 실제로 이 알고리즘은 어느 회사 면접에서 라이브 코딩으로 물어봤던 내용이다. 예전부터 공부했지만, 매번 까먹는 내용이다보니 확실히 기억하기 위해 상세히 적어본다.. # 후위 표기식으로 변환 1. 숫자는 바로 변환하는 후위식에 넣어준다. 2. 연산자일 경우 스택에 넣는다. (단, 스택에 현재 연산자보다 우선순위가 낮은게 있을때까지 빼서 후위식에 넣어준다. 그 다음 스택에 넣기) (이는 즉, 스택에 현재 연산자보다 우선순위가 높거나 같은건 다 나와야 한..
-
[자료구조] Queue(큐)Mhwan's Study/Data Structure 2021. 1. 6. 00:42
# Queue (큐) First In First Out (FIFO)형태의 자료구조로, BFS탐색이나 버퍼 등에 사용된다. 기본적으로 rear와 front라는 포인터로 삽입할 곳과 뺄 곳을 가리키고 있음 (rear : enQueue (삽입)할 위치, front : deQueue(데이터 빼기)할 위치) 1. 기본적인 구현 front와 rear은 모두 초기에 -1로 시작한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public Queue { int[] queue; int rear = -1; int front = -1; public Queue(){ queue = new int[50]; } public void enQueue(in..
-
[자료구조] Stack (스택)Mhwan's Study/Data Structure 2021. 1. 5. 22:46
평소 블로그를 포트폴리오용으로 사용했으나, 오늘부터 개인적인 공부할 내용을 정리해두는 용도로 사용합니다. 일단 알고리즘 문제보단 CS관련으로 올리려 합니다. 알고리즘도 이와 연관된 것들만.. 첫번째는 스택으로 시작하려합니다. # Stack 스택은 Last In First Out (LIFO) 방식의 자료구조로, 주로 함수의 호출 콜스택 등에 사용됩니다. 1. 배열을 통한 구현 top이라는 변수를 통해 push할 곳과, pop할 곳을 가르켜야한다. (top의 초기 위치는 -1) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 public Stack { int MAX_SIZE; int[] stack; int top = -1; pu..
-
Mhwan's Career Log (현재까지의 기록)About Mhwan 2020. 7. 30. 03:04
- Develop Career 2021 'NAVER ETECH SmartEditor' Android 파트 인턴 2020 'PICA' 안드로이드 App (대학교 졸업작품, https://mhwan.tistory.com/65) 2020 '마스크 파인더' 안드로이드 App (플레이스토어 출시 중단, https://mhwan.tistory.com/48?category=725190) 2019 '강남대학교 시간표 new' 안드로이드 App (플레이스토어 출시중, https://mhwan.tistory.com/40?category=725190) 2016 'CheckMoney' 안드로이드 App Prototype (중도 개발 중단, https://mhwan.tistory.com/39?category=725190) 20..