chhggg
article thumbnail
[백준 C++] 20922 겹치는 건 싫어
PS/BOJ 2023. 1. 28. 04:56

https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 투포인터 글쓸때 한번 시도해봤다가 코드가 꼬여서 덮어뒀던 문제이다... 문제에서 요구하는 것이 "최장 연속 부분 수열의 길이"이므로 투포인터 알고리즘으로 해결 가능할 것이다. 투포인터 알고리즘의 개념은 아래 링크에 있다. https://chhggg.tistory.com/15 투포인터 알고리즘 (Two pointers Algorithm) 투포인터 알고리즘은 슬라이딩 윈도우 알고리즘이라고도 하며..

article thumbnail
다익스트라 알고리즘 (Dijkstra Algorithm)
PS/Algorithm 2023. 1. 27. 00:53

다익스트라 알고리즘은 최단 경로 문제를 해결할 수 있는 알고리즘이다. 최단 경로 알고리즘에는 BFS, 다익스트라, 플로이드와샬, 벨만-포드가 있다. BFS는 간선의 가중치가 모두 같을 때, 다익스트라와 벨만-포드는 각 간선의 가중치가 다를 때 한 정점에서 다른 정점까지의 최단 경로를 구할 때(벨만-포드는 음의 가중치가 있을 때), 플로이드와샬은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구할 때 사용한다고 함. 알고리즘은 다음과 같은 순서를 통해 수행된다. 1. 시작 노드 설정 2. 최단 거리 테이블 초기화 (연결 되지 않은 노드는 INF) 3. 연결되었지만 방문하지 않은 노드 중 최단 거리를 가지는 노드 선택 & 방문 4. 해당 노드를 거쳐 다른 노드로 갈 때의 비용을 계산하여 최단 거리 테이블을..

투포인터 알고리즘 (Two pointers Algorithm)
PS/Algorithm 2023. 1. 9. 19:44

투포인터 알고리즘은 슬라이딩 윈도우 알고리즘이라고도 하며, 1차원 배열에서 두 개의 포인터를 조작해서 원하는 결과를 얻는 알고리즘이라고 한다. 보통 완전탐색으로 풀어서 시간초과가 날때의 해결책이 될 수 있다고 한다. 아래 문제가 전형적인 투포인터 알고리즘 문제이다. https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 주어진 1차원 배열 중에 합이 M이 되는 부분의 수를 구하는 문제이다. 1) 포인터를 sta..

article thumbnail
배낭 문제 (knapsack problem)
PS/Algorithm 2022. 12. 23. 03:51

배낭 문제란.. 나무위키 왈 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제라고 함. 즉 쉽게 말해서 도둑이 가방에 담을 수 있는 양이 정해져 있는데 얼마나 효율적으로 비싼 물건을 담아 최고의 이득을 볼 수 있는지.. 이런 문제이다. 배낭문제는 크게 fractional knapsack problem, 0-1 knapsack problem 로 나눌 수 있다! 1. fractional knapsack problem (분할 가능한 배낭문제) 이 유형은 좀 단순하다고 생각된다. 별 다른 제약 없이 짐이 분할이 가능한 것이다. 무슨말이냐면, 위 사진과 같이 짐이 있을떄,..

보호되어 있는 글입니다. 내용을 보시려면 비밀번호를 입력해주세요.
보호되어 있는 글입니다. 내용을 보시려면 비밀번호를 입력해주세요.

검색 태그