Algorithm115 [알고리즘] 불확실한 상황을 현명하게 사용하는 코드 이번글은 학교 알고리즘 수업 시간에 Randomized algorithm을 배우면서 느낀 점을 남기는 글입니다. 어떤 알고리즘을 설명한다기보다는, 제가 느낀 점을 남겨보는 글입니다. 1. 불확실한 상황을 이용해 볼 수 없을까? 우리가 코드를 작성할 때 모든 상황이 확실하게 결정된 상황에서만 진행하는 경우는 거의 없다, 어쩌면 이는 코드뿐만 아니라 대부분의 사람들이 하루를 살아가는 자연스러운 방법(?) 중 하나일지도 모른다. 물론 우리는 계획이라는 것을 만든다. 해당 계획을 통하여 시간이 얼마나 걸릴지 예측할 수도 있고, 얼마나 많은 리소스가 필요한지 또한 측정할 수 있다. 하지만 이는 어느 정도의 사전 정보가 있다는 가정 하에 가능할 것이며, 당장 첫 시도를 해야 하거나, 상황 자체가 너무나 불확실하다면.. Algorithm/PS 알고리즘 정리 2023. 12. 14. [알고리즘] 최소 공통 조상 LCA(Lowest Common Ancestor) 1. LCA란? LCA(Lowest Common Ancestor)는 주어진 두 노드 a와 b의 최소 공통 조상을 찾는 알고리즘입니다. 예를 들어 다음 그림과 같은 트리가 있다고 했을 때, 12번과 15번 노드의 최소 공통 조상 LCA는 5번 노드가 됩니다. 우선 두 노드의 LCA를 찾는 가장 간단한 O(N)이 걸리 방법으로 2가지 정도가 있다. 2가지에 대하여 간단하게 알아본 후, 이글의 Main 목표인 O(LogN) 안에 해결하는 알고리즘에 대하여 알아보자. 2. O(N) 알고리즘 2-1) 두 Node의 Level을 통일시키는 방식 A와 B의 깊이가 다를 경우 더 깊은 정점의 부모를 따라 하나씩 올라가면서 A와 B의 깊이를 맞춘다. 위의 결과 A와 B가 같다면 A(or B)가 최소 공통조상이다. A !.. Algorithm/PS 알고리즘 정리 2023. 12. 8. [알고리즘] HeapSort보다 QuickSort가 더 빠른 이유 1. 왜 HeapSort보다 QuickSort가 현실적으로 더 빠를까? HeapSort와 QuickSort는 대표적으로 O(NlogN)안에 동작하는 정렬알고리즘이다. 하지면 현실성면에서 QuickSort가 더 빠르다는것은 익히 들어 알고있을 것 이다. 왜 그런것 일까? 이에 대하여 알아보자 1-1) 알고리즘의 성능 요인 크게 정렬 알고리즘에서 성능을 미치는 원인은 크게 3가지로 볼 수 있다. 비교 및 스왑을 수행하기 위한 반복자(loop) = 반복자가 어떻게 구현되어있는가의 문제 유효 접근 시간 (지역성) 메모리 소비량 1번의 경우 대부분 시간복잡도를 측정할때 고려하는 요소라, O(NlogN)이라는 표기안에 포함되어있는 개념이다. 따라서 HeapSort와 QuickSort의 차이는 2번인 유효 접근 시간.. Algorithm/PS 알고리즘 정리 2023. 10. 13. [프로그래머스][Java] 택배 배달과 수거하기 (268) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이문제를 보고 생각한 방식은 다음과 같았다. 1) 일단 10진수를 2진수로 변환한다 2) 변환된 2진수를 재귀적으로 (왼쪽, 중심, 오른쪽) 으로 나누어서 탐색하면서 판단하면 되겠다! 였다! 하지만 생각하지 못했던 부분이 있었는데, 10진수를 2진수로 변환한다고 끝나는 것 이 아니다... 변환된 2진수가 만약 포화 이진트리가 아니.. Algorithm/프로그래머스 2023. 5. 5. [프로그래머스][Java] 택배 배달과 수거하기 (267) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 생각이고 나발이고 문제 진짜 어렵다 생각 드는데, 이거 나처럼 greedy라고 생각 못한 사람은 끝까지 이 문제 못 건들이다가 끝났을것 같다. 일단 N제한이 100,000 이라 O(N^2), 즉 완전 탐색은 절대 안된다 생각했다. 여기서 문제다. 그럼 O(logN) = 5, O(NlogN) = 500,000, O(N) = 1000.. Algorithm/프로그래머스 2023. 4. 27. [백준][C++] 16120번: PPAP (266) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 입력이 1,000,000까지라 O(NlogN), O(N) 안에 해결해야겠다는 생각부터 들었다. 그런데 경험상 이런 문자열 처리는 대부분 O(N)에 처리하는 문제였기에, 문자열을 처음부터 끝까지 한 번만 탐색해서 처리하는 방식을 생각하게 되었다. 문제는 이해만 하면.. Algorithm/백준 2023. 3. 21. [백준][Python] 10282번: 해킹 (265) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 다익스트라를 알면 금방 해결할 수 있는 문제이다. 문제는 다익스트라인 것을 어떤 부분에서 눈치챌 수 있을까? 사실 문제만 읽으면 최단경로를 구해야 한다는 점이 명확하게 보이지 않을 수 있다(적어도 나는 그랬다.. Algorithm/백준 2023. 2. 14. [백준][C++] 18808번: 스티커 붙이기 (264) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이게 생각보다 쉬운것 같으면서 약간 구현이 빡신 문제이다. 애당초 생각을 많이 하기보다는, 문제 그대로 구현만 계속 하면 되는 문제이다. 배열의 크기도 최대 40*40 이라 brute force 방식으로 해결하면 된다 .. Algorithm/백준 2023. 2. 13. [백준][C++] 6987번: 월드컵 (263) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/6987 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 사실 보자마자 떠오른 방식은, 모든 팀은 게임을 할때마다 3가지 경우(승리, 비김, 패배)중 하나의 경우가 나온다 생각하였다. 또한 6개팀이 승부하는 경우의 수는 15가지 이다. A: {B, C, D, E, F} B.. Algorithm/백준 2023. 2. 9. [LeetCode][C++/Python] 238번: Product of Array Except Self (262) 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 사실 문제를 보자마자 든 생각은 전체 수를 다 곱한다음, 해당 자리의 수로 나누는 방식이다. 아마 나같은 일반인이라면 당연히 나누는 방식을 생각했을 것 이다... 하지만 문제 제약 조거을 보면.... "나누기 금지".... 따라서 좀더 생각을 하게 되었다. 일단 문제는 O(N)안에 해결 가능해야 한다는 점이다. 일단 투포인터 비슷한 방식으로 해야 하지 않을까? 란 생각이 먼저 들었다. O(N)안에 가능해야 하니 말이다! 어떤 수 하나를 생각해보면, 그 수의 index의 양옆 => (0 ~ index - 1), (index + 1 ~ N)의 수를 전부 곱해야 한다. 그럼 우선 배열을 순회하면서 왼쪽의 곱들만 구하고.. Algorithm/LeetCode 2023. 1. 18. [LeetCode][C++/Python] 42번: Trapping Rain Water (261) 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 1. Stack을 활용한 풀이 처음 떠오른 방식은 Stack을 사용하는 방식이었다. (뭔가 예전에 풀어본건가? 그냥 보자마자 Stack부터 떠올랐다) Stack에 게속 index를 추가하면서, 현재를 기점으로 이전보다 높이가 더 높은 경우에 해당 volume을 계산하여 결과변수에 더해준다. 글만 보면 이해가 안갈 수 있다, 다음 그림을 살펴보자. 우선 맨처음 1번 블록을 보면, 인덱스 2에서 3으로 넘어갈때 이전보다 높이가 높아지는 곳 이다. (0에서 2로) 따라서 다음 while문의 height[i] > height[stack.top()]을 만족시키게 된다. while (!height_stack.empty() .. Algorithm/LeetCode 2023. 1. 5. [LeetCode][C++/Python] 5번: Longest Palindromic Substring (260) 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 2가지 접근 방법이 있다. 사실 문제를 보면 바로 떠오르는 내용은 일반적으로 DP와 LCS(Longest Common Substring)이다. 따라서 나는 1) DP로 문제를 해결하려 노력하였다. 문제를 풀고 나니 보고 있는 책 에서는 2) 투포인터를 활용한 슬라이딩 윈도우 방식을 사용하였다. 이 방식 또한 정리해볼까 한다. 1) DP방식 접근 우선 DP로 푸는 경우 DP[i][j]의 의미를 i번째 부터 j까지가 palindrome인 경우 True를 대입하도록 하였다. 따라서 재귀적으로 DP[i][j]이 palindrome이려면 DP[i+1][j-1]이 palindrome 이여야 하고, 또한 str[.. Algorithm/LeetCode 2022. 12. 29. 이전 1 2 3 4 ··· 10 다음
