본문 바로가기

Algorithm

 (117)
[SWEA] JAVA - 5432.쇠막대기 자르기 처음에 문제를 어떻게 풀것인지에 대해 '오늘 수업에서 스택을 배워서 스택 자료구조를 사용할껏같습니다'라고 생각했다가 반성한 문제입니다. 처음 아이디어가 떠오르지 않아 수업을 듣고나서 이해했습니다. 또한 스택을 사용해서 풀어도 되지 않은 문제이고 레이저가 나올때 누적한 쇠막대기값과 나와있는 쇠막대기 개수를 더해나가면 되는 문제였습니다. 만약 () 이런 형식의 레이저가 아니고 ')' 만 나왔을때는 쇠막대기가 끝나는 지점이므로 나와있는 쇠막대기 개수인 cnt값을 -1 감소시키고 누적 쇠막대기 값도 +1만 더해주면된다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util..
[백준] Python - 1316.그룹단어체커 생각 중복하는 단어들이 연속해서 들어오는지에 대한 체크를 해주기 위해 스택을 사용하자고 생각했다. 우선 각 문자가 존재하지 않는다면 스택에 넣어준다. 만약 스택에 현재 abcd 이렇게 들어있고 그 다음으로 d 가 들어온다고 생각했을때는 스택에 추가해주지 않는다. 그 다음으로 계속 진행하다가 현재 스택에는 유니크한 문자들만 존재하는데 만약 abcde에서 d가 또 들어오려고할때 새로운 값과 스택의 마지막 원소가 같지 않을때가 바로 그룹 단어가 아닌 단어이다. Python Code def groupChecker(s): stack = [] for i,c in enumerate(s): if c not in stack: stack.append(c) else: if (i!=0) and (s[i] != s[i-1]):..
[정렬 알고리즘] - Heap Sort 먼저 우선순위 큐를 알아야한다. 우선순위 큐는 사실 가장 일반적인 큐이다. 왜냐하면 스택이나 큐도 우선순위 큐를 사용하여 구현할 수 있기 때문이다. 적절한 우선순위만 부여하면 우선순위 큐는 스택이나 큐로 동작할 것이다. 우선순위 큐는 네트워크 트래픽 제어, OS에서 작업 스케쥴링 등에 사용된다. 이러한 우선순위 큐를 구현하기 위해 사용되는 자료구조가 배열, 연결 리스트 등으로 구현이 가능한데, 가장 효율적인 구조는 Heap 을 사용한 방식이다. 이제 Heap에 대해 알아보자! heap 이란 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 완전 이진 트리로 최대값, 최소값을 찾아내는데 유용하다. 이러한 힙 정렬을 사용할때 가장 좋은 경우는 전체 자료를 모두 정렬하는 것이 아니라 가장 큰 값 몇개만 ..
[정렬 알고리즘] - Quick Sort merge sort와 비슷하게 분할 정복 방법으로 정렬하는 방식이다. merge sort와는 다르게 퀵 정렬에서는 부분 리스트를 분할할때 비균등하게 분할한다. 분할시 리스트 안에 있는 한 요소를 pivot으로 선택한뒤 pivot보다 작은 원소들은 왼쪽으로 큰 원소들은 오른쪽으로 분할한다. 이 상태에서 pivot을 제외한 왼쪽 리스트와 오른쪽 리스트들을 계속해서 분할 정복 방법으로 정렬해나간다. QuickSort Animation 구현 (업로드 예정) def partition(arr, low, high): i = (low-1) #작은 원소들의 끝 pivot = arr[high] for j in range(low,high): if arr[j]
[SWEA] JAVA - 1208.Flatten 전에 이와 비슷한 문제를 풀어서 정렬을 사용해 금방 풀수있었다. 평탄화의 핵심 아이디어는 가장 큰값과 가장 작은 값의 차이를 계속 상쇄시키는것인데 이때 가장 큰값의 값을 하나씩 빼서 가장 작은값에게 하나씩 더해주면 된다. 나는 주어진 배열을 내림차순으로 정렬시켜줬다.(오름차순도 상관없다 주어진 문제 상황을 그대로 재현하려고해서 내림차순으로 정렬시켜줬다.) 그 다음으로 dump 횟수 만큼 가장 큰 값을 가진 첫번째 원소에서 1을 빼준 다음 가장 작은 원소인 마지막원소에 1을 더해줬다. (Arrays.sort의 시간복잡도는 O(nlogn) 이고 주어진 테스트케이스가 10개로 고정되있기 때문에 Arrays.sort 메소드를 사용하여 풀었다) public static void solve2() throws IOE..
[정렬 알고리즘] - Merge Sort Merge sort 하나의 리스트를 두개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 병합하여 전체가 정렬된 리스트가 되게 하는 정렬 방법이다. 합병 정렬은 분할 정복(Devide and conquer) 방법에 바탕을 두고 있다. 분할(Devide) : 정렬하려는 리스트를 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작을때까지 재귀 호출을 이용하여 1단계-2단계를 반복한다. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열로 합병한다. 이해를 돕기 위한 애니메이션 영상!! 구현 (업로드 예정입니다!!) def merge(leftList, rightList): i = 0 j = ..
[백준] JAVA - 1244.스위치 켜고 끄기 남자인 경우와 여자인 경우 비트를 처리하는 로직이 다르다. 남자인 경우는 주어진 번호의 배수마다 모두 비트를 반전시킨다. 여자인 경우 주어진 번호 기준 좌우대칭 값이 같을때 최대한 넓은 영역의 비트를 반전시킨다. 이때 여자의 번호는 무조건 반전된다. 처음 제출했을때 틀렸는데 그 이유는 스위치의 상태를 한줄에 20개까지 출력한다음 개행을 놓쳤었다. 그 다음으로 제출했을때도 틀렸는데 while문의 조건에서 left와 right의 범위를 left >= 0 && right < n 으로 설정하여 틀렸다. 스위치 번호값이 1부터 시작하기 때문에 처음에 배열 크기를 +1 늘려주고 index를 1부터 시작하도록 했는데 while문 내부의 범위 조건에서 이를 놓쳤다. 오늘의 배움 = '배열의 범위를 잘 체크하자!!' p..
[백준] JAVA - 1535.안녕 1월 5주차 알고리즘 스터디에서 진행한 DP 문제이다. 문제에서 구하려는것은 주어진 체력안에서 얻을수있는 최대 기쁨값이다. DP로 풀수있는 문제들은 처음 주어진 문제들을 더 작은 문제들로 나눌 수 있다는것이 특징이다. 즉 이렇게 작게 나누어진 부분문제들로 이들의 답을 통해 원래 문제에 대한 답을 구할수있는것이 핵심이다. DP 에서는 부분문제들이 여러번 재사용될수있기 때문에 이들의 값을 따로 저장하는 기법(Cache, Memoization)을 잘 사용하면 효율적으로 풀수있다. 보통 DP 문제들을 보면 점화식을 세우고 이를 재귀적으로 풀이하는 코드가 많지만 나는 이 문제를 보고 재귀적으로 구현하는게 부족해서 손으로 직접 써가면서 문제를 풀었다. 마음은 재귀로 풀고싶었지만 그렇게 풀지 못해서 다른 스터디원이 ..

티스토리툴바