일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- DP
- SW Expert Academy
- 스택
- 데이터베이스
- 그리디 알고리즘
- 다익스트라
- 백트래킹
- 너비우선탐색
- 오라클
- 브루트포스 알고리즘
- 파이썬
- DFS
- 자바스크립트
- SWEA
- 완전탐색
- oracle
- BFS
- 백준알고리즘
- 깊이우선탐색
- 그래프 탐색
- 백준 알고리즘
- Python
- 문자열
- javascript
- 다이나믹 프로그래밍
- 그래프 이론
- 너비 우선 탐색
- 브루트포스
- 구현
- 프로그래머스
- Today
- Total
목록알고리즘 (8)
민규의 흔적
2024년 11월 26일위상 정렬 위상 정렬이란, 순환하지 않는 유향 그래프(DAG, Directed Acyclic Graph)를 방향성에 거스르지 않도록 순서대로 배열하는 방법이다. 이게 무슨 의미인가. 다음 예시를 통해 쉽게 이해해보자. 나는 어떤 RPG 게임을 시작하려고 한다.해당 RPG 게임에서는 첫 레이드인 A 보스 레이드에 참여하기 위해서 50레벨을 달성하고 모든 장비 강화를 10단계 이상 달성해야 한다.그리고 다음 레이드인 B 보스 레이드에 참여하기 위해서, A 보스 레이드를 클리어한 상태에서 모든 장비 강화를 15단계 이상 달성해야 한다.그리고 장비를 업그레이드 하기 위해서는 B 보스 레이드를 클리어한 상태에서 기존 장비를 상위 장비로 계승해야 한다. 어떤 RPG 게임에서 내가 이룩하고 싶..
오탈자나 오류를 범한 내용이 있다면 댓글 남겨주세요!! 언제든 환영합니다!!!!!2024년 10월 10일 패턴 매칭 당장 ctrl + F를 누르면 현재 페이지에서 찾고자 하는 키워드를 손쉽게 찾을 수 있는 기능이 존재한다.이와 같이 전체 문자열에서 특정 키워드(패턴)을 찾는 것을 패턴 매칭이라고 부른다. 패턴 매칭 알고리즘 문자열 패턴 매칭 알고리즘은 워드패드, 논문, 웹 페이지 등에서 원하는 키워드를 검색할 때 빠른 속도로 찾게 해주는 중요한 역할을 한다.문서 전체의 길이가 길수록, 그리고 검색하려는 키워드(패턴)의 길이가 길수록 효율적인 패턴 매칭 알고리즘을 필요로 하게 된다. 패턴 매칭 알고리즘에는 여러 가지가 존재하지만, 이 글에선 브루트포스( brute force ) 방식과 KMP 알고리즘 방식..
2024년 5월 22일다익스트라( 데이크스트라, Dijkstra ) 다익스트라 알고리즘은 그래프의 한 정점에서 모든 정점까지의 최단 경로를 각각 구하는 알고리즘으로, 에츠허르 다익스트라가 고안한 알고리즘이다. 다이나믹 프로그래밍을 활용해 중복 연산을 방지하며 최단 경로를 구한다는 특징을 지니고 있다. 플로이드-워셜 알고리즘과는 다르게, 다익스트라 알고리즘은 그래프 내에 음의 가중치를 가진 간선이 존재한다면 사용할 수 없다. 추가로 둘의 차이점이라면 다익스트라 알고리즘은 하나의 노드로부터 최단 경로(one - to - all)를 구하는 알고리즘인 반면, 플로이드-워셜 알고리즘은 가능한 모든 노드쌍들에 대한 최단 경로(all - to - all)를 구하는 알고리즘이라는 점이다. (플로이드-워셜 알고리즘에 대..
2024년 5월 16일 0-1 냅색 문제를 풀어보며 해당 이론에 대해 알아보도록 하겠다. 문제 링크 : SWEA 3282번 - 0/1 Knapsack SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 접근 제목에서 친절하게 0-1 냅색 문제임을 알려주었다. Knapsack 문제는 배낭 문제라고도 하며, 0-1 Knapsack 문제와 Fractional(분할 가능한) Knapsack 문제가 존재한다. 둘의 차이점은 다음의 예시를 보며 설명하겠다. 민규는 고향으로 내려가기 전, 배낭에 선물을 담아 가져갈 것이다.선물을 무한정 담으면 좋겠지만, 배낭의 한계 무게 W를 초과하면 배낭이 찢어진다.민규는 각각의 선물..
2024년 4월 16일 LIS (최장 증가 부분 수열) 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)이란, 주어진 배열 내에 존재하는 여러 부분 수열 중 오름차순을 준수하며 가장 길게 나열되어 있는 부분 수열을 의미한다. 예를 들어, { 2, 3, 8, 6, 4, 5, 9, 1 } 라는 배열의 LIS는 { 2, 3, 4, 5, 9 } 이며 길이는 5 이다. 오름차순을 준수하는 부분 수열은 { 2, 3 }, { 2, 3, 5 }, { 2, 3, 6, 9 } 등 많지만, 가장 긴 부분 수열은 { 2, 3, 4, 5, 9 } 이다. LIS의 길이를 알아내는 방법은 대표적으로 완전 탐색법과 DP(다이나믹 프로그래밍), 이분 탐색이 존재한다. 이 중, 완전 탐색을 통해 모..
2023년 10월 27일 플로이드-워셜(Floyd-Warshall) 플로이드-워셜 알고리즘이란, 모든 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이라면, 플로이드-워셜 알고리즘은 한 번의 실행으로 모든 정점 간의 최단 거리를 구할 수 있다는 차이로 구분할 수 있다. 또한 음수 가중치가 존재하는 가중치 그래프에서는 적용할 수 없는 다익스트라 알고리즘과는 다르게, 플로이드-워셜 알고리즘은 음수 가중치가 존재하는 가중치 그래프에서도 활용할 수 있다. 접근 방법 사전 준비 플로이드-워셜 알고리즘을 적용하기 위해선, 가중치 그래프가 존재해야 한다. 임의의 가중치 그래프를 예시로 들어보겠다. 정점은 1~5번까지 총 5개의 정점이 존재하고,..
2023년 9월 19일 그래프 탐색 (해당 포스팅은 무향 그래프를 인접 리스트 형태로 다루며 설명을 진행합니다.) 그래프 탐색은 연결되어 있는 그래프의 모든 정점을 지나며 탐색하는 것을 의미한다. ( 그래프 순회라고도 말한다. ) 그래프를 탐색하는 방법으로는 깊이 우선 탐색인 DFS, 너비 우선 탐색인 BFS가 사용된다. DFS ( Depth First Search ) DFS는 출발점에서 시작해, 막다른 지점에 도착할 때까지 최대한 깊게 탐색한다. 만약 탐색을 진행하다 막다른 지점에 도착하면 다시 이전 정점으로 돌아가 다른 길이 있는지 확인하고, 있다면 해당 경로를 최대한 깊게 탐색하다 또 다시 막다른 지점에 도착하면 다시 이전 정점로 돌아가는 과정을 밟는다. 이와 같은 과정을 통해 그래프를 탐색하는 방..
2023년 5월 13일문제 링크 : 11400번 - 단절선문제 그래프가 주어졌을 때, 단절선을 모두 구해 출력하는 프로그램을 작성하시오.단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다.입력첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는..