알고리즘 검색 결과
37 개의 검색 결과가 있습니다.
# 공부 자료들/알고리즘

[알고리즘] 다익스트라 알고리즘

코테 준비를 하다보면 흔하게 등장해서 항상 공부해야지 하면서도 그러지 못했던 알고리즘들이 많이 생깁니다. 다익스트라 알고리즘도 그 중 하나인데요! 그래서 이번 기회에 확실하게 알고 넘어가야겠다 생각해서 공부했습니다 :) 목차 0. 다익스트라 알고리즘이란? 음의 가중치가 없는 경우에 특정 출발지에서 모든 정점까지의 최단거리를 구하는 알고리즘입니다. 대부분의 알고리즘은 최적의 해를 찾기 위해 등장하는데, 특정 상황에서 최적의 상황을 찾는 다익스트라 알고리즘은 현실 세계와도 굉장히 밀접하게 연관이 되어있기 때문에 정말 많이 쓴다고 볼 수 있습니다! (그래서 그런지 코테를 보면 심심치 않게 등장합니다!) 다익스트라의 동작 방식은 시작점을 잡고 최단거리를 갱신한 후에 가장 가까운 곳으로 이동해서 다시 그 곳에서 ..

2022. 3. 7. 01:25
# 주저리주저리/가끔 하고 싶은 뻘소리

알고리즘.. 알고리즘!!

매번 최대한 만들어놨던 양식에 맞춰서 글을 쓰려고 하고 있는데, 여기에서만큼은 가끔씩 목차를 달지 않고 의식의 흐름대로 한번 글을 써볼까 합니다. (근데 버릇처럼 쓰게되네요.. 무서워라) 원래는 학습스프린트 4주차가 끝나고 중간점검으로 글을 쓸까 했는데, 왜 이렇게 글이 안올라오냐고 하시는 분들이 많기도 하고 무엇보다 오늘 코테보고 현타와서... ㅋㅋㅋㅋㅋㅋㅋ (코테는 완전 망했습니다 ㅠ) 그동안 소홀했던 나를 반성하며 다시금 열정의 불씨를 조금이라도 살려보고자 이렇게 글을 작성중입니다. 목차 0. 알고리즘 시작 처음 개발자를 목표로 하겠다고 했던 것이 작년 말~ 올해 초였는데, 그 당시 어떻게 공부를 시작해야 할까 잘 알지 못해서 프로그래머스 알고리즘 문제를 풀기 시작했던 기억이 납니다. 그 당시에는 ..

2021. 9. 12. 02:18
# 알고리즘 문제풀이 (PS)/프로그래머스

[프로그래머스 Level 3] [그래프] 순위 (C++)

안녕하세요! 쏘코입니다. 정말 오랜만에 알고리즘 문제를 손에 잡게 되었습니다. 한동안 기술 스택을 쌓는다고 알고리즘에 조금 소홀했는데, 학기가 끝나서 여유가 생긴 만큼 다시 코테 통과를 위한 알고리즘 공부를 열심히 해야겠죠? 하필이면 제가 제일 두려워 하는 그래프 문제가 기다리고 있다는 것이 참 무서웠습니다. 바로 설명으로 들어가시죠! 출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 목차 0. 문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까..

2021. 7. 3. 05:19
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 7.5. 계산복잡도 : 검색 2 (完)

안녕하세요! 코딩하는 경제학도 쏘코입니다. 드디어 이번 포스팅이 알고리즘분석의 마지막 포스팅이 될 것 같습니다. 참 길었습니다 ㅠㅠ 이번 포스팅에서는 해시와 문자열 매칭으로 검색을 구현하는 방법에 대해 알아보도록 하겠습니다. 목차 0. 해싱 만약 키가 주민등록번호라면 해당 번호의 저장소 를 모두 만들기는 굉장히 어렵습니다. 13자리의 숫자를 담아야 하기 때문입니다. 그렇다면 어떻게 효율적으로 인덱스를 관리할 수 있을까요? 이럴 때 사용할 수 있는 방법이 바로 해싱입니다. 0부터 99의 인덱스를 가진 크기가 100인 배열을 만든 후에, 키를 0~99 사이의 값을 가지도록 해시(hash)합니다. 여기서 해시함수는 키를 배열 인덱스값으로 변환하는 함수입니다. 예를 들면 h(key) = key % 100 으로 ..

2021. 6. 16. 09:21
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 7. 계산복잡도 : 검색

알고리즘분석 카테고리의 마지막은 검색의 계산복잡도에 대한 내용이 되겠습니다. 이번 포스팅에서는 검색 방법들의 계산복잡도를 알아보도록 하겠습니다. 목차 0. 검색의 하한 먼저 검색 문제의 정의부터 알아보도록 합시다. 검색 문제는 n개의 키를 가진 배열 S와 어떤 키 x가 주어졌을 때, x = S[i]가 되는 첨자 i를 찾는 것입니다. 만약 x가 배열 S에 없다면 오류로 처리해야하죠. 이전 포스팅에서 배웠던 정렬을 이용해서 배열을 정렬한 후에 이진(이분) 검색 알고리즘을 사용하면 시간복잡도가 W(n) = floor(lg n) + 1이 되어서 매우 효율적인 알고리즘을 만들 수 있습니다. (floor는 내림, ceil은 올림입니다!) 그렇다면 이진 검색보다 더 좋은 알고리즘을 만들 수 있을까요? 정답은 아니다입..

2021. 6. 15. 22:16
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 6.5. 계산복잡도 : 정렬 2

깔끔하게 정렬되어있는 저 펜들도 처음에는 막 흐뜨러져 있었을 수 있습니다. 저 친구들을 올바른 자리에 똑바로 정렬시키는 것도 하나의 알고리즘이라고 할 수 있겠죠? 이전 포스팅에서 O(n^2)의 시간복잡도를 가진 친구들에 대해서 알아봤다면, 이번 포스팅에서는 보다 나은 효율(O(n lg n))을 가진 알고리즘들에 대해서 공부할 예정입니다. 바로 내용으로 넘어가시죠! 목차 0. 합병정렬 합병정렬은 분할정복의 대표적인 예시입니다. 분할정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 뒤 결과를 모아서 원래의 문제를 해결하는 방법을 사용합니다. 합병정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 만..

2021. 6. 14. 21:49