개발조각

안녕하세요. 개발조각입니다.😊 제가 엘리스AI트랙에 서류통과가 돼서 프리트랙을 준비하면서 파이썬을 배우게 되었습니다. :D 그래서 파이썬 배운김에 알고리즘 공부를 조금씩 해볼까 해요. 어떻게 공부를 할까 고민을 했는데 정말 유명한 개발 유튜버인 동빈나님께서 올린 이코테 2021 강의 몰아보기를 토대로 공부할 생각입니다. 제가 이 강의를 선택한 이유는 동빈나 이분이 유명하시기도 하고 알고리즘 강의 중에서 가장 최근이라 선택하게 되었습니다. 이번에 강의를 들으면서 티스토리에 정리를 해볼까 해요. 사실 티스토리에 정리해둘 필요는 없겠지만 정리를 해야 나중에 제가 찾아보기 편해서 적어보려 합니다.😄 (뭔가 기록을 해야 기억이 남는 것 같기도 하고요.) 강의 구성 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수..

두 정점 간의 최단 경로(shortest path)는 가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로를 의미한다. 모든 정점 간의 최단 경로는 주어진 그래프에서 경로의 길이, 즉 가중치의 합이 음수인 사이클은 없다고 가정한다. 모든 정점 간의 최단 경로를 구하는 대표적인 알고리즘으로 플로이드(Floyd)알고리즘이 있다. 플로이드 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 한꺼번에 구하는 알고리즘으로, 간선의 인접 행렬 표현을 활용하여 경유할 수 있는 정점의 범위가 1인 경로부터 시작해서 1부터 |V|까지 인 경로까지 단계적으로 범위를 늘려 가면서 모든 정점 간의 최단 경로를 구하는 알고리즘이다. 예제 1 다음과 같이 네 개의 정점과 다섯개의 간선으로 ..

편집 거리(edit distance)는 두 문자열 사이의 근접성 또는 유사성을 판단하는 척도로, 철자 검사기에서 잘못된 철자를 만나면 해당 철자와 가장 근접한 다른 단어를 찾아주는 데 활용된다. 일반적으로 편집 거리는 두 문자열 사이에 편집이 필요할수록 커지는 구조이다. 예제 1 x='baa'와 y='aab'가 주어졌을 때 x와 y의 편집 거리를 구하시오. 단, ins=del=1, chg=2 예제 2 x='SNOWY'와 y='SUNNY'가 주어졌을 때 x와 y의 편집 거리를 구하시오. 단, ins=del=1, chg=2 스트링 편집 거리 알고리즘 function solution(x, y, ins, del, chg){ const [row, col] = [x.length, y.length]; let answ..