일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 이분탐색
- 백준
- 후니의 쉽게 쓴 시스코 네트워킹
- 그리디
- 백트래킹
- JUnit 5
- 구현
- 투 포인터
- 세그먼트 트리
- 프로그래머스
- BFS
- Network
- 알고리즘
- Kotlin
- 위상정렬
- 동적계획법
- mst
- 완전탐색
- CS
- 스택
- Effective Java
- dfs
- 시뮬레이션
- 플로이드-와샬
- 수학
- 유니온 파인드
- 문자열
- java
- swea
- 에라토스테네스의 체
목록투 포인터 (6)
반갑습니다!
14921번: 용액 합성하기 boj.kr 풀이 투 포인터 알고리즘을 사용해서 해결했다. 기존의 방식과 조금 변형해서 사용했는데, 시작 인덱스를 0, 끝 인덱스를 n-1로 두었다. 그리고 두 인덱스가 가리키는 용액을 섞어서 0에 가장 가까운 조합을 찾아주었다. 이 때 0에 가장 가깝다는 것은 절대값이 가장 작다는 의미이므로 절댓값 함수 abs()를 사용했다. 코드 C++
2491번: 수열 www.acmicpc.net 풀이 가장 긴 길이의 연속해서 커지거나 작아지는 수열을 찾는 문제이다. 연속해서 커지는 수열의 길이를 찾을 수 있으면, 입력 받은 숫자 배열을 뒤집어서 연속해서 작아지는 수열의 길이를 찾을 수 있다. 해당 문제에서 실제 연속해서 커지는 수열의 값이 필요한 것이 아니라 길이만 알면 되기 때문에 투 포인터 알고리즘을 사용해 해결했다. 코드 C++ #include #include #include using namespace std; int n; vector num; int two_pointer() { int left = 0; int right = 0; int last_value = 0; // 수열의 마지막 값을 저장할 변수 int ret = 0; // 수열의 최대..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이 문제는 효율성을 테스트하는 문제이다. 그리고 전형적인 투 포인터문제라고 할 수 있다. 보석들의 처음부터 끝까지 탐색하면서 set과 map을 이용해서 보석의 종류의 개수와 보석의 개수를 확인해주면 O(n) 시간만에 해결할 수 있다. 코드 #include #include #include #include using namespace std; vector solution(vector gems) { // 처음에 최대 구간으로 설정 vector answer = { 1, (int)gems.size() }; // ..
1806번: 부분합 www.acmicpc.net 풀이 투 포인터 알고리즘을 사용하여 해결하였다. 이 때 합이 s보다 같거나 큰 경우에는 정답을 찾기 위해 최솟값 비교를 해주어야한다. 코드 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, s; cin >> n >> s; vector num(n); for (int& i : num) cin >> i; int start = 0, end = 0; int sum = 0; int ans = 100001; while (true) { if (sum >= s) { ans = min(ans, end - start); sum -=..
2003번: 수들의 합 2 www.acmicpc.net 풀이 투 포인터 알고리즘을 사용하여 해결하였다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; int s = 0, e = 0; cin >> n >> m; vector num(n); for (int i = 0; i > num[i]; int ans = 0; int sum = 0; while (true) { if (sum >= m) sum -= num[s++]; else if (e == n) break; else sum += num[e++]; if (sum == m) ans++; } c..