알고리즘46 [알고리즘] 불확실한 상황을 현명하게 사용하는 코드 이번글은 학교 알고리즘 수업 시간에 Randomized algorithm을 배우면서 느낀 점을 남기는 글입니다. 어떤 알고리즘을 설명한다기보다는, 제가 느낀 점을 남겨보는 글입니다. 1. 불확실한 상황을 이용해 볼 수 없을까? 우리가 코드를 작성할 때 모든 상황이 확실하게 결정된 상황에서만 진행하는 경우는 거의 없다, 어쩌면 이는 코드뿐만 아니라 대부분의 사람들이 하루를 살아가는 자연스러운 방법(?) 중 하나일지도 모른다. 물론 우리는 계획이라는 것을 만든다. 해당 계획을 통하여 시간이 얼마나 걸릴지 예측할 수도 있고, 얼마나 많은 리소스가 필요한지 또한 측정할 수 있다. 하지만 이는 어느 정도의 사전 정보가 있다는 가정 하에 가능할 것이며, 당장 첫 시도를 해야 하거나, 상황 자체가 너무나 불확실하다면.. Algorithm/PS 알고리즘 정리 2023. 12. 14. [알고리즘] 빅오(Big-O)표기법 수학적 이해 1. Big-O를 수학으로 이해하기 이번 코드스쿼드 멘토를 진행하면서, Big-O 표현식에 대한 과제가 있었다. 물론 이에 대한 직관적인 이해까지는 대부분 하게 된다. 하지만, 성장을 원하는 개발자라면 한 번쯤 수학의 관점에서 이해할 수 있어야 된다 생각한다! 그만큼 Bio-O는 중요한 내용이다! 따라서 학생들에게 이를 설명하기 위한 12분 정도의 영상을 하나 만들었는데, 좀 부족하지만... 나름 잘? 설명했다 생각하여 유튜브 영상으로 남겨두었다! https://youtu.be/OF-BsdcFJ8U (3:49, 5:59, 7:52초 에 N제곱 이라 말한 부분 N제로 입니다 ㅎㅎ) Algorithm/PS 알고리즘 정리 2022. 11. 10. [백준][C++] 12100번: 2048 (Easy) <215> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 원래 맨 처음 생각한 풀이는 DFS를 진행하면서 우선 방향에 대한 중복순열을 구한 후, 구해논 중복 순열대로 돌려가면서 닶을 구하려 했다. 문제는 4방위에 맞도록 비슷한 함수를 4번이나 작성해야 한다는 점 이였다.... 이러한 문제를 해결하기 위해 2차원 .. Algorithm/백준 2022. 4. 27. [백준][C++] 10942번: 팰린드롬? <212> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 생각보다 간단한 DP 문제이다. 1) 길이가 1인 경우 모두 팰린드롬 수가 된다. 2) 길이가 2인 경우 바로 다음 칸의 수와 비교해서 같은지 확인하면 된다. 3) 길이가 3 이상인 경우 우리의 배열 input이 다음과 같다 해보자. 1 2 1 3 1 2 1 이중 가장 중간에 있는 P : [1, 2, 1] 은 팰린드롬 수 .. Algorithm/백준 2022. 4. 7. [백준][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++] 16719번: ZOAC <186> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 와 이번문제 나는 어려웠다. 단순하게 A부터 찾아서 추가하는 식으로 해결하기도 어렵다. 왜냐하면 문자는 중복이 가능하기 때문이다. A가 2개 이상이라면 어디부터 시작해야 할까? 이또한 문제이다... 따라서 나는 다음과 같은 알고리즘으로 문제를 해결해 나갔다. (다른분의 풀이를.. Algorithm/백준 2022. 2. 14. [백준][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. [알고리즘] L-트로미노 1. 트로미노란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 트로미노는 크기가 같은 정사각형 3개를 변끼리 붙여 만든 다각형 이다. 따라서 다음과 같은 모양이 가능하다. 2. 트로미노로 구성된 불완전 보드 증명 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 트로미노중에서 L 모양의 트로미노를 한 변의 길이가 2^n인 정사각형에 배치하는 것이 목표이다. 결론부터 말하자면, L-트로미노는 1x1 한 칸을 제외하고, 한 변의 길이가 2^n인 정사각형을 항상 채울 수 있다. 위 가정의 증명은 다음과 같이 수학적 귀납법으로 가능하다. 1) Base 단계 (n = 1일때) 만약 n = 1 이면 2x2의 불완전 보드는 트로미노 자신이며, 하나의 .. Algorithm/PS 알고리즘 정리 2022. 2. 10. [백준][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. [자료구조] 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. 이전 1 2 3 4 다음
