728x90 개발자7 [SW사관학교 정글] WEEK05 주말의 단상 [SW사관학교 정글] WEEK05 주말의 단상 주말이 되어따.. 주말은 일단 행복하다. 평일도 행복하지만 고통-행복-고통-행복의 무한 반복이라면, 주말은 defualt가 일단 행복이다. 똑같이 공부하고 똑같이 강의실에 앉아 있음에도 마음이 여유로워 지는건 신기하면서도 기분 좋은 일이다. 어제도 4시에 잠들어서 아침 늦게 일어났음에도 불구하고 머리가 아픈 관계로 중간 감상문을 적어볼까 한다. 아마 단상이자 잡상이 되지 않을까 싶다. 4주간의 알고리즘 공부가 끝나고 C언어와 OS 공부주차에 들어갔다. 이번주 공부했던 것은 공부하는 내내 레드-벨벳 케이크가 생각나는 레드-블랙 트리여따. 투썸에 먹으러 가야게따.. 5주차 - 레드-블랙 트리 가아아아아아장 복잡한 구조를 자랑하는 자료구조를 배우면 앞으로 어떤 자.. 2021. 9. 12. [C언어] 이진 탐색 트리(Binary Search Tree, BST) [C언어] 이진 탐색 트리(Binary Search Tree, BST) 이진 탐색 트리란 이진 탐색(Binary Search)과 연결리스트(Linked List)를 결합한 자료구조의 일종이다. 이진 탐색의 효율적인 탐색 능력(O(log n)은 유지하면서 자료 입력과 삭제가 효율적으로(O(1)) 가능하다. 이진 탐색 트리 특징 각 노드에 값이 있다. 값들은 전순서가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다. 이진 탐색 트리 기능 검색, 추가, 삭제, 최솟값 찾기 코드 #include #include typedef i.. 2021. 9. 7. [WEEK04] 알고리즘_그리디(Greedy) 알고리즘 [WEEK04] 알고리즘_그리디(Greedy) 알고리즘 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 난이도가 매우 낮은 알고리즘 중 하나이다. 항상 최적의 결과를 도출하는 것은 아니지만 어느정도 빠르게 구할 수 있으며 특정한 상황에서는 그리디 알고리즘이 최적의 해를 구할 수 있게 해준다. 예를 들면 거스름 돈 문제이다. 무조건 더 큰 화폐 단위부터 거슬러 주는 것이 최적의 해를 제공한다. 즉, 무조건 큰 경우, 작은 경우, 긴 경우, 짧은 경우 등 극단적으로 문제에 접근한다는 점에서 정렬(Sort) 기법이 함께 사용되는 경우가 많다. 사실 뭔가 특별한 테크닉이 아니라 그냥 특정 경우에 평소 풀던대로 풀면 되는 듯 하다.. 유튜브 - 동빈나 그리디(Greedy) 알고리즘 [ 실전 알고리즘 강좌(Al.. 2021. 8. 30. [백준_9252] 다이나믹 프로그래밍(DP), LCS 최장 공통 부분 문자열 [백준_9252] 다이나믹 프로그래밍(DP), LCS 최장 공통 부분 문자열 다이나믹 프로그래밍 대표 문제인 LCS 문제를 풀어봤다. LCS(Longest Common Subsequence)는 최장 공통 부분 문자열로 다이나믹 프로그래밍의 대표적인 문제이다. 문자열 출력까지 포함하는 9252번 문제를 풀어보았다. https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 풀이 생각 포인트 다이나믹 프로.. 2021. 8. 27. [WEEK04] 알고리즘_다이나믹 프로그래밍(DP) [WEEK04] 알고리즘_다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 특징 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 메모이제이션(Memoization, 이미 계산한 결과는 배열에 저장함. Memorization이 아님)을 통해 동일 계산시 저장된 값을 단순히 반환하여 시간을 줄임 -> 메모리를 적절히 사용하여 수행 시간을 굉장히 단축시킨다. 일반적으로 탑다운(하향식, 재귀함수 이용), 바텀업(상향식) 두가지 방식으로 구현한다. 보통 바텀업이 전형적인 형태이다. 다이나믹 프로그래밍 사용 조건 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 통해 큰 문제를 해결 가능한 구조 중복 부분 문제(Overlapping Subproblem.. 2021. 8. 27. [SW사관학교 정글] 8/21(토) 장병규 의장님과의 대화 보호되어 있는 글 입니다. 2021. 8. 21. 이전 1 2 다음 728x90
