IT/Algorithm24 트리 - 트리 순회 순서 변경 트리 - 트리 순회 순서 변경 문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/TRAVERSAL 트리 계층적 구조를 갖는 자료들을 표현하기 위한 자료구조 ex) 대진표, 조직도, 상품 분류 등등 풀이 생각 (삽질) 1. 어떻게 전위랑 중위를 가지고 후위를 찾을까? 1) 전위와 중위를 보고 전체 트리를 만든 후, 후위 탐색을 할까? (트리를 만든 후 후위 탐색) 2) 전위와 중위를 살펴보면서 후위 탐색 (하나씩 살펴보면서 후위 탐색 출력) 2. 왼쪽 오른쪽 어떻게 구분할까? - preorder의 첫번째가 root이고, inorder에서 root가 나오기 전까지 왼쪽인 것을 발견. - inorder에서 왼쪽을 따로 넘겨주고, 오른쪽을 따로 넘겨주고, 계속 반복... 2020. 8. 22. 스택 - 짝이 맞지 않는 괄호 스택 - 짝이 맞지 않는 괄호 문제출저 - 알고스팟 https://algospot.com/judge/problem/read/BRACKETS2 풀이생각 1. 닫힌 괄호일 때 스택검사 => 일치하면 pop, 다르면 바로 return false 2. 열린 괄호일 때 push 3. 함수 마지막에서 스택이 비어있다면 잘 끝난것 (true), 남아있다면 잘못된것 (false) 내 코드 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include #include using n.. 2020. 8. 20. 선형 자료구조 - 조세푸스 문제 선형 자료구조 - 조세푸스 문제 문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/JOSEPHUS 풀이생각 1. 하나의 리스트에서 2명이 남을 때까지 자살한 병사를 삭제 => 특정 위치의 삭제가 용이한 연결리스트를 사용하자 => remove를 사용하려 했으나, 이것은 원소를 탐색하여 제거하는 것. 연결리스트를 선택한 이유가 없어짐 => iterator를 지우는 erase를 사용하자 2. 마지막 원소에서 어떻게 iterator를 처음으로 옮겨줄까? => Linked list 마지막 원소의 다음 iterator에 접근했을 때, Linked list의 begin으로 iterator를 옮겨주기 => 마지막 원소의 다음 주소를 가리키는 end를 사용하자 3. 그럼 어떤.. 2020. 8. 18. 선형 자료 구조 (동적 배열, 연결 리스트) 선형 자료 구조 (동적 배열, 연결 리스트) 1. 동적 배열 ● 배열의 문제점 1. 처음 배열을 선언할 때 크기를 지정해주어야 한다. 2. 그 크기 이상의 자료를 집어넣을 수 없다. => 이 문제를 해결하기 위한 것이 동적배열이다. ● 동적배열의 특징 동적배열의 내부는 배열로 이루어져있기 때문에 배열의 특징을 이어받는다. 배열의 특징 이어받은 것 - 원소들은 메모리의 연속된 위치에 저장 => 캐시의 효율성과 직결되기 때문에 아주 중요하다. - 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있음 동적배열이 가지는 다른 추가 특성 - 배열의 크기를 변경하는 resize() 연산이 가능 => 배열의 크기 N에 비례하는 시간이 걸림 - 배열의 맨 끝에 원소를 추가할 수 있는 append() .. 2020. 8. 17. 탐욕법 - 도시락 데우기 탐욕법 - 도시락 데우기 문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/LUNCHBOX 탐욕법 여러 개의 조각으로 쪼개는 방법. 이는 완전탐색, 동적 계획법이랑 같음. 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 지금 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려하지 않는다. 가장 중요한 건 정당성 증명 (최적 부분 구조) 만약 제일 안 좋은 것이 있다면 그것을 최적해로 가정하자. 그리고 더 좋은 것을 찾으면 그것이 최적해라고 한다. 이렇게 결국 제일 좋은 것을 찾아가 최적해를 찾는다. 귀류법같은 느낌이 난다. 풀이생각 i번째 도시락 데우기 + 먹기. 어느번째 도시락이 오래 걸릴까 체크 i번째 시간 = 데우기시간 + 먹기시작한시간 + 먹기시.. 2020. 8. 17. 분할 정복 - 쿼드 트리 뒤집기 문제 출저 - 알고스팟 https://algospot.com/judge/problem/read/QUADTREE 이것에 중점을 둬보자. - 분할하고, 정복한다. - 재귀 던져준 후에는 생각말자. 절차 - 트리를 입력 받는다. (string) - 입력을 분석 (분할) - 트리를 상하로 뒤집어서 출력 일단 입력을 받고 분할해보자. 아직 분할정복이 감이 안잡혔다. 문제를 보고 분할정복해야지 라는 생각을 못함. 일단 공부하는 부분이 분할정복이라서 어떻게 분할할지 생각해보자. string tree를 입력받는다. w나 b이면 return w, b; -> 기저사례 x이면 4개로 분할 -> 4개의 재귀로 들어감. 분할했으면 정복?병합?해결?도 하자. 순서는 왼쪽위 - 오른쪽위 - 왼쪽아래 - 오른쪽아래 뒤집으면 왼쪽아래.. 2020. 8. 5. 해시 (Hash) - 전화번호 목록 전화번호 목록 문제 출저 - 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/42577 - 제한사항 분석 1. phone_book의 길이는 1 이상 1,000,000 이하입니다. 2. 각 전화번호의 길이는 1 이상 20 이하입니다. => 문제의 크기를 나타냅니다. - 이 문제에서 원하는 것은? phone_book의 각 요소들의 번호에 대한 수를 기록하고 저장하는 구조 !! => 이름(Key), 이름에 대한 수(Value) 로 key value 쌍을 만들어야 하는데, key가 string이고 value는 int입니다. 이렇게 정수 인덱스 말고 문자열 같은 다른 타입으로 찾아갈 수 있는 구조가 바로 해시입니다. (완주하지 못한 선수와 거의 동일합니다) .. 2020. 2. 20. 해시 (Hash) - 완주하지 못한 선수 완주하지 못한 선수 문제 출저 - 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/42576 - 제한사항 분석 1. 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. => 문제의 크기를 나타냅니다. participant의 길이가 100,000이하라는 것도 말해줍니다. 2. completion의 길이는 participant의 길이보다 1 작습니다. => 1명만 완주하지 못한 것을 알려줍니다. 3. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. => 이것 또한 문제의 크기를 나타냅니다. 4. ★★참가자 중에는 동명이인이 있을 수 있습니다. => 이 조건으로 유형이 달라집니다. 동명이인이 있을 수 있기.. 2020. 2. 20. 해시 (Hash) 해시 (Hash) 해시(Hash)란? - hash table이라는 저장공간 내에 key들이 어떤 위치에 있을지를 정해서, hash table 안에 값들을 저장하는 구조를 말합니다. 해시는 key value 쌍으로 이루어져 있으며, 배열과 달리 key value가 int형이 아니어도 됩니다. 만약 key value가 int형이라면 선형배열(linear array)을 이용해도 되지만, int가 아닌 string같은 다른 자료형일 경우 해시를 이용하면 좋습니다. * 사상, 매핑(mapping) - 위의 그림에서 "leo"는 2번째 칸에, "kiki"는 7번째 칸에, "eden"은 3번째 칸에 사상 또는 매핑(mapping) 되었다고 표현합니다. * hash function - hash table 안에 key들.. 2020. 2. 18. 이전 1 2 다음
