본문 바로가기

분류 전체보기

 (164)
[백준] 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 = ..
IT 용어 정리 작년에 NCS 공부하면서 정리한 IT 용어 정리 노트다. 단어만 보고 답을 생각하기 위해 내용을 숨겨놨는데 티스토리로 옮기려니깐 숨기기 기능이 지원되지 않는다ㅜㅜ 계속 업데이트 될 예정!! www.notion.so/4ad334f426834848be26f3258fed32fd
[백준] JAVA - 1244.스위치 켜고 끄기 남자인 경우와 여자인 경우 비트를 처리하는 로직이 다르다. 남자인 경우는 주어진 번호의 배수마다 모두 비트를 반전시킨다. 여자인 경우 주어진 번호 기준 좌우대칭 값이 같을때 최대한 넓은 영역의 비트를 반전시킨다. 이때 여자의 번호는 무조건 반전된다. 처음 제출했을때 틀렸는데 그 이유는 스위치의 상태를 한줄에 20개까지 출력한다음 개행을 놓쳤었다. 그 다음으로 제출했을때도 틀렸는데 while문의 조건에서 left와 right의 범위를 left >= 0 && right < n 으로 설정하여 틀렸다. 스위치 번호값이 1부터 시작하기 때문에 처음에 배열 크기를 +1 늘려주고 index를 1부터 시작하도록 했는데 while문 내부의 범위 조건에서 이를 놓쳤다. 오늘의 배움 = '배열의 범위를 잘 체크하자!!' p..
Collection 중복체크 - equals(), hashCode() Collections Collection 인터페이스는 모든 클래스들의 Object를 element로 저장하는 객체의 최상위 Interface 이다. 예를 들어, Collection에서 객체를 삭제하는 경우 Object Class의 equals()는 주소값을 비교하기 때문에 동일한 정보를 가진 객체를 서로 다른 객체로 판단하여 False를 반환한다. 하지만, 객체의 주소값을 비교하는것이 아닌 객체의 실제 값들을 비교하고 싶을때 equals()를 재정의하여 사용해야한다. /* 객체 p3와 p4를 동일하게 생성하고 p4를 삭제해보면 삭제가 되지 않는다*/ // 새로운 환자 등록 Patient p3 = new Patient("환자3", 33, "010-3333-3333", "고열", "001", false); ..

티스토리툴바