반응형 Programming27 [Algorithm][Python]최장 증가 부분 수열(LIS) 알고리즘 + 코드 이번에 알아 볼 알고리즘은 최장 증가 부분 수열, 통칭 LIS(Longest Increasing Subsequence)입니다. 어떤 수열이 입력으로 주어질 때 해당 수열에서 증가하는 부분 수열의 최대 길이를 구하는 문제에서 볼 수 있습니다. 약간 변형을 해서 사용하면 LCS 알고리즘과도 비슷합니다. 사실 구현만 한다고 했을 때는 굳이 따로 포스팅을 해야할 만큼 거창한 풀이 방법이 있는 것은 아닙니다. 동적 계획법이 익숙하신 분들에게는 그냥 우리가 머리로 생각하듯이 처음부터 원소를 하나씩 순차적으로 탐색하면서 부분 수열의 길이를 세면 되는 거라 코드 작성도 쉬운 편이라고 생각하지만, 제 개인적인 경험으로는 그냥 이런 걸 처음봐서 증가 부분 수열이 무슨 소린지 이해하는 것이 시간이 더 걸렸던 것 같습니다. .. 2023. 10. 5. [Algorithm][Python]깊이/너비 우선 탐색 알고리즘(DFS/BFS) + 코드 너무 중요한 알고리즘이죠. 대표적인 그래프 탐색 알고리즘인 깊이 우선 탐색, 너비 우선 탐색에 대해서 알아봅시다. 이 그래프를 기본으로 해서 알아보겠습니다. 깊이 우선 탐색(Depth First Search) 먼저 알아볼 것은 깊이 우선 탐색, DFS 입니다. 이번 포스팅에서는 기본 그래프를 트리로 사용하고 있지만 트리에만 사용할 수 있는 것은 아닙니다. DFS는 이름 그대로 그래프를 탐색함에 있어서 깊이를 우선적으로 탐색하는 방법을 말합니다. DFS의 탐색 순서입니다. 1 → 2 → 4 → 5 → 3 → 6 → 7 의 순서로 탐색을 진행하는 모습을 확인할 수 있는데요. 저는 DFS를 보면서 호기심이 많은 사람이다 라고 생각했던 기억이 있습니다. 각 노드를 하나의 방이라고 보고 간선이 문이라고 한다면 깊.. 2023. 8. 12. [Algorithm][Python]유니온-파인드(Union-Find) 알고리즘 + 코드 이번에는 유니온 파인드 알고리즘에 대해서 한 번 알아봅시다. 아직 학부생이던 시절에 저보다 먼저 알고리즘 공부를 하던 친구가 유니온 파인드 한 번 써보라고, 진짜 너무 편하다고 했던 기억이 나는데요. 그 때 저는 DFS/BFS도 모르던 시절이라 그런게 있구나 생각만 하고 넘겼습니다. 사실상 그런 일이 있었다는 것도 거의 잊고 지내다가 평소처럼 알고리즘 문제를 풀었는데 별로 런타임이 빠르지 않았고, 해당 문제가 어떤 태그가 있나 살펴보다가 분리 집합이라는 알고리즘으로 분류가 되어있어서 이걸 사용하면 좀 빨라지려나 싶어서 찾아봤던게 유니온 파인드와의 첫 만남이었네요. 사실 이게 유니온 파인드구나를 알았을 때는 약간의 당황과 겁이 났습니다. 저한테 유니온 파인드는 상당히 먼 얘기일거라고 생각하고 있었거든요. .. 2023. 8. 3. [Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드 저를 가장 오랫동안 괴롭혔던 알고리즘 중에 하나인 데이크스트라 알고리즘에 대해서 정리를 해볼까합니다. 그 때의 헤매던 저와 비슷한 분들께 도움이 되면 좋겠네요. 데이크스트라(Dijkstra) 최단 경로 알고리즘 최단 경로라는 말에서 짐작할 수 있듯이 데이크스트라 알고리즘은 출발점에서 도착점까지 가장 빠르게 갈 수 있는 경로를 탐색하는 알고리즘입니다. 최단 경로를 구하는 알고리즘에는 대표적으로 데이크스트라, 플로이드-워셜, 벨만-포드, A*(에이 스타) 이렇게 네가지가 있으며 이번 포스팅에서는 데이크스트라 알고리즘에 대해서만 정리를 해보겠습니다. 알고리즘의 이름인 데이크스트라는 알고리즘의 고안자인 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라(Edsger Dijkstra)의 이름을 따서 부르고 있습니다. 한.. 2023. 8. 1. [Algorithm][Python] 계수 정렬(Counting Sort) 알고리즘 + 코드 이번에는 제가 가장 좋아하는 정렬 알고리즘인 계수 정렬(Counting Sort)에 대해 작성해보겠습니다. 문제 풀이를 하면서 상당히 많이 계수 정렬을 이용한 풀이를 포스팅했습니다. 계수 정렬을 굳이 사용했던 이유는 너무 많지만 계수 정렬을 알게 된 이유는 백준 문제 때문이었네요. counting sort 정도로 빠른 정렬 알고리즘을 사용하지 않으면 풀 수 없는 문제가 있었던 것으로 기억합니다(비고에도 counting sort를 알아보라는 말이 적혀있었구요). 그게 계기가 되어서 계수 정렬을 공부했고 처음엔 이게 무슨 말인가 싶었는데 익숙해지니까 속도도 빠르고 직관적이라 자주 쓰게 되었네요. 계수 정렬 그렇다면 계수 정렬(Counting Sort)은 무엇일까요? 위키피디아에 따르면 양의 정수를 키로 하여.. 2022. 12. 23. [CSS]티스토리 글 쓰기 배경색 변경하기 이번 글도 제목이 뭐 이래 싶은 글입니다. 좀 더 좋은 제목이 떠오르면 좋겠는데요. 티스토리는 글 작성하는 화면이 흰색으로 고정입니다. 운동 일지 같은 걸 작성할 때는 시간도 얼마 안걸리기 때문에 크게 불편하지는 않지만 정보 전달을 위한 글을 작성할 때는 저한테 상당히 부담스러운데요. 거기다 티스토리는 글 작성 화면은 스킨 적용도 안됩니다. 열심히 티스토리 스킨을 다크모드로 바꿔도 사실상 가장 긴 시간을 들여서 보는 화면에는 적용을 못한채 흰 화면만 계속 봐야한다는 것이죠. 그래서 이 포스팅에서는 제가 사용하는 간단한 방법을 알려드리겠습니다. 이 방법은 영구적인 해결 방법이 아니라 해당 페이지에서 글을 작성하는 동안만 적용되고 새로고침이나 다른 페이지에서는 적용이 안됨을 미리 알려드립니다. 방법 자체는 .. 2022. 6. 7. [Capstone Design]마치며 이번 포스팅은 캡스톤 디자인 마지막 포스팅이 될 예정입니다. 마지막에 와서는 거의 하루에 1.5~2개의 포스팅을 작성해서 금방 끝난 것 같은데요. 뭔가 급하게 끝내는 느낌도 들구요. 원래는 프로젝트의 전반적인 진행상황을 기록하려고 시작했던 포스팅이 차일피일 미루다 보니 결국 끝나고도 많은 시간이 지나서 글을 쓰게 되었는데요. 뭔가 시원섭섭하네요. 원래는 프로젝트에 관해서 모든 내용을 포스팅하려고 했습니다. 제가 맡지 않았던 부분들도 말이죠. 처음에는 그게 맞다고 생각했습니다. 다음에 제가 했던 것과 비슷한 프로젝트를 진행하면서 혹시 찾아올지도 모를 분들을 위해서도 더 자세히 써야한다고 생각을 했었습니다. 하지만 그렇게 하는 것은 포기하고 제가 진행했던 부분만 작성을 했는데요. 해당 이유는 다음과 같습니다.. 2022. 4. 19. [Capstone Design]5. 웹캠을 이용한 실시간 차선인식 이번 시간에는 웹캠을 한 번 써봅시다. 원래 같으면 차선 인식 마지막에 넣었어야 했는데 어쩌다 보니 뒤로 밀렸네요. 이때까지 해왔던 것에서 입력해주는 이미지가 웹캠에서 찍는 이미지로 바뀌는 것뿐입니다. 빠르게 관련 코드부터 먼저 보겠습니다. capture = cv2.VideoCapture(0) capture.set(cv2.CAP_PROP_FRAME_WIDTH, 640) capture.set(cv2.CAP_PROP_FRAME_HEIGHT, 480) _, frame = capture.read() capture.release() 이번에는 한 군데에 있는게 아니라 조금 퍼져있어서 필요 코드만 가져와봤습니다. 평소처럼 제일 마지막에 전체 코드를 남겨두겠습니다. ○ capture = cv2.VideoCapture(.. 2022. 4. 18. [Capstone Design]4. 시리얼 통신(Serial Communication) - 2 오늘은 말씀드렸던 대로 조향 파라미터를 아두이노로 보내서 처리하는 것을 진행해보겠습니다. 사실 오늘 포스팅은 반쪽짜리 포스팅이라고 할 수 밖에 없는게, 벌써 해당 프로젝트를 끝을 내고 이미 다 분해해서 처리를 했기 때문에 제가 가지고 있는 것도 카메라와 아두이노 뿐이고 일체 모터나 전선은 가지고 있지 않기 때문에 에코백 정도 까지만 구현을 하고 넘어가게 될 것 같습니다. 그래도 최대한 자세히 적어보도록 노력하겠습니다. 일단 지난 포스팅에서 시리얼 통신에 대해, 파이썬과 아두이노로 시리얼 통신을 하는 법에 대해서 간략하게 알아봤었죠. 하지만 뭐 아무 데이터나 보낸다고 우리가 원하는 동작을 해주지는 않겠죠. 그래서 우리가 이렇게 말하면 이렇게 해주고 저렇게 말하면 저렇게 해줘 라고 하는 약속을 해야합니다. .. 2022. 4. 17. [Capstone Design]4. 시리얼 통신(Serial Communication) - 1 이번 시간에는 시리얼 통신과 파이썬에서 시리얼 통신을 하는 방법에 대해서 알아보겠습니다. 시리얼 통신(Serial Communication)이란 정기적인, 일련의, 연속된 같은 뜻을 가지고 있는 serial과 통신, 대화, 소통 등의 뜻을 갖는 communication의 합성어입니다. 한글로는 직렬 통신이라고 부릅니다만 근래에 들어서는 다들 시리얼 통신이라고 부르는 게 더 익숙한 듯합니다. 이런 시리얼 통신은 통신 방법 중에 하나이고 직렬이 있으니 병렬 통신(Parallel Communication)도 존재합니다. 시리얼 통신의 특징은 데이터를 주고 받을 때 직렬로 즉, 한 선만을 이용해서 통신을 한다는 점입니다. 예를 들어서 Serial 이라는 데이터를 보낼 때 S 보내고, e 보내고, r 보내고..... 2022. 4. 17. 이전 1 2 3 다음 반응형
