자료구조론47 [백준][C++] 2263번: 트리의 순회 <191> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구해야 하는 문제이다. 다음 이진트리를 우선 살펴보자. 중위 순회 : 8 4 9 2 5 1 6 3 7 후위 순회 : 8 9 4 5 2 6 7 3 1 우리는 후위 순회를 통해 root 번호를 알수가 있다. 후위 순회의 마지먹 번호인 1이 root에 해당.. Algorithm/백준 2022. 2. 24. [백준][C++] 1629번: 곱셈 <187> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 입력으로 받을 A, B, C 모두 int형으로 담을수 있는 값이다. 하지만 A^B를 한다 했을때, 이를 직접 계산하려면 1) 변수 크기도 엄청 커지게 된다. 2) 자료의 크기 1억당 => 1초 정도 걸리기 때문에, 2^2,147,483,647 만 계산하려 해도 21초나 걸린다. 따라서 이를 분할정복으로 해결해야 한다. 예를들어 2^8을 구해야 핸다.. Algorithm/백준 2022. 2. 17. [백준][C++] 14601번: 샤워실 바닥 깔기 (Large) <185> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 14601번: 샤워실 바닥 깔기 (Large) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 7) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 문제를 해결하기에 앞서, 출력하는 부분부터 매우 거슬리는 문제이다. 보통 시작점을 왼쪽 상단으로 두는데, 이번 문제는 시작지점이 왼쪽 하단이다. 이점 또한 주의해야 한다. 우선 이번 문제를 해결하기 위해 L-트로미노에 .. Algorithm/백준 2022. 2. 13. [백준][C++] 1939번: 중량제한 <183> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 BFS + 이분탐색(파라메트릭 서치) 가 포함된 문제이다. 이분탐색은 가능한 범위 내에서 탐색을 해야 한다. 답으로 가능한 가장 작은 중량제한은 0 부터 ~ 가장 무거운 중량제한은 입력으로 받은 다리의 중량 최대.. Algorithm/백준 2022. 2. 7. [백준][C++] 12919번: A와 B 2 <180> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이 문제는 문자 S => T를 직접 만들려하면 해결할수가 없는 문제이다. 매번 2가지 선택 사항이 있는데, 문자열의 총 길이가 49까지 가능하니, 2^49가 되므로, 시간초과가 발생할것이다. 따라서 역으로 T => S로 조건에 맞게 변경이 가능한지를 확인해야 한다. 조건 1) 주어진 S의 문자열 맨 끝이 'A'라면 맨 뒤 문자 하나를 제거해 준다. 조건 2) 주어진 문자열 S의 맨앞 문자가 'B'라면, 문자열 전체를 뒤집은 후 맨뒤로온 'B'를 제거해 준다. 여기서 주의할점이 1번과 2번 조건을 else if 로 묶으면 안된.. Algorithm/백준 2022. 1. 31. [자료구조] Priority Queue, Dijkstra 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번시간에는 우선순위 큐 (priority queue)에 대하여 배웠다. 일반적인 queue는 후입 선출의 과정, 즉 먼저 들어간 원소가 먼저 나오는 방식이지만 우선순위 큐는 각 원소마다 우선순위가 정해져서, 우선순위가 높은 원소부터 먼저 나오는 방시이다. Priority Queue " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 Queue 이긴 한데, 원소들이 우선순위를 갖고있다. 우선순위가 높은 원소가 먼저 나온다. 가능한 배열 구현 종류 - Sorted by priority : 빠른 삭제연산, 하지만 삽입이 느리다. - Unsorted .. CS/Data Structure (2021-1) 2022. 1. 25. [자료구조] 2-3-4 Tree, Red-Black Tree 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 시간에는 2-3 Tree의 확장 버전인 2-3-4 Tree에 대하여 배웠으며, 이를 Red-Black Tree로 표현하여 보았다. 2-3 Tree가 궁금하다면 이전 글을 먼저 확인해보길 권장한다. [자료구조] AVL Tree, 2-3 Tree 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 시간에는 AVL-Tree에 대하여 배웠다. AVL-Tree 는 BS blogshine.tistory.com 2-3-4 Tree " data-ke-type="html"> HTML 삽입 미리보기할 .. CS/Data Structure (2021-1) 2022. 1. 25. [자료구조] AVL Tree, 2-3 Tree 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 시간에는 AVL-Tree에 대하여 배웠다. AVL-Tree 는 BST가 최악의 경우 linked-list 처럼 이어저 O(n)의 시간복잡도의 성능을 보여준다는 단점을 보완하는 tree이다. AVL-Tree의 직관적 이해 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 다음 그림을 통해 AVL-Tree가 어떻게 보정 작업을 하는지 살펴보자. 왼쪽의 경우 root 노드인 6을 기준으로 왼쪽으로 node들이 치우쳐 있는 모습을 볼 수 있다. 이 tree의 H(높이)는 4에 해당한다. 이를 AVL-Tree의 정의에 부합하도록 보정 작업을 해주면.. CS/Data Structure (2021-1) 2022. 1. 25. [자료구조] Binary Search Tree 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 시간에는 이진탐색트리 에 대하여 배우는 시간이였다. 이진탐색의 방식으로 만들어진 트리라고 생각하면 쉽다. 크게 Search, Insert, Delete 3가지 기능이 필요한데 Delete의 경우 삭제할 Node의 자식이 몇명인지에 따라 case가 나뉜다. 우선 Skip List에 대하여 간단하게 살펴보자. Skip List " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 Skip LIst란 여러 node를 건너뛸 수 있는 Linked List를 말한다. 이를 활용하여 중간 지점으로 건너 뛸 수 있다면, 이진탐색의 방식을 Linked Li.. CS/Data Structure (2021-1) 2022. 1. 25. [자료구조] Linked List 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 시간에는 연결리스트(Linked List)에 대하여 배웠다. 사실 연결리스트만 해도 내가 직접 구현해본 경험이 이미 여러번 있고 쉬운내용이라 이해하는데 어렵지 않았다. 윤성우 열혈, C++로쉽게풀어쓴 자료구조, 알고리즘책 등등 이미 많은 책에서 자주 접했던 내용이다. 구현부분은 조금 대충한 느낌이 있는데... 예전 글에서 더 정성스럽게 구현한 경험이 있으니... 이 글에서는 돌아갈정도만 구현하는걸로.... Linked List " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 연결리스트 란 노드를 data 와 다음 노드를 가리킬 포인터로 .. CS/Data Structure (2021-1) 2022. 1. 25. [자료구조] Equivalence Relation 출처: https://privatedevelopnote.tistory.com/81 [개인노트] 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 시간에는 Equivalence Relation(동치관계) 에 대하여 배웠다. 이산수학에 나오는 내용으로 그레프 이론과 연계되는 것 같다. 우선 relation에 대하여 알아본 후, Equivalence Relation에 대하여 알아보자. Relation " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 relation이란 다음과 같다. 이를 좀더 해석해보면 Relation이란 한 집합 위에서 정의되는 관계를 말한다. 처음들어서는 명확하지 않.. CS/Data Structure (2021-1) 2022. 1. 24. [서평] 쉽게 배우는 알고리즘 저의 돈으로 직접사서 직접 완독해본후 써보는 후기입니다. 따라서 장점은 장점대로 칭찬할것이며, 단점은 단점대로 언급할 것 입니다. 쉽게 배우는 알고리즘 저자 : 문병로 출판 : 한빛아카데미 발매 : 2018.01.20 2021/03/25 ~ 2021/05/12 1) 책의 표지 2) 단원별 구성 3) 읽은소감 우선 저의 글의 앞부분만 보는 분들을 위해 먼저 간단히 3가지에 대해 답해보겠습니다. Q 이 책을 읽기 전에 필요한 수준/ 지식은? => 이책은 알고리즘을 깊게 설명해주는 책 이다. 기본적인 자료구조에 대한 충분한 이해가 필요하다. 더 나아가 이미 알고리즘을 어느정도 접해본 분이라면 더욱 배워갈점이 많은 책 이다. Q 이 책을 읽어야 할 필요성, 어디에 도움이 될까? => 단순 코딩테스.. Life/Book Record 2022. 1. 24. 이전 1 2 3 4 다음
