# 투포인터
[알고리즘] 프로그래머스 - 구명보트
프로그래머스 - 구명보트처음에는 대충 생각하고 역순으로 정렬한 다음, 하나씩 꺼내서 비교하는데 무게가 초과하면 새 보트를 꺼내는 식으로 구현했다. 하지만 그렇게하면, 낭비되는 공간이 있고, 그 낭비되는 공간에 몸무게가 작은 사람들을 넣을 수 있다. 따라서 투포인터로 큰
2470번 두 용액
문제 출처 : https://www.acmicpc.net/problem/2470투포인터 관련 문제란 걸 몰랐다면 못 풀었을라나... 조금은 시간이 소요됐을 듯Brute force로 하면 O(n^2)이 나오는데 이건 아닐 거 아니야. 결국 합해서 0에 가깝게 되
[알고리즘] 부분 문자열이 포함된 최소 윈도우
부분 문자열이 포함된 최소 윈도우코드만 봐서는 직관적으로 이해가 가지 않는다. A에서 시작해서 필요한 ABC가 다 생기면 A를 제외하고 B부터 시작해서 다음 A가 있는 곳까지 찾고.. 반복이다. missing이 0이되면, 즉 필요하누 문자의 개수가 0이 된다면 이제 왼
2003번 수들의 합2
문제 출처 : https://www.acmicpc.net/problem/2003 사고과정 선형적인 list에서 연속적인 값들을 요소로 하여 주어진 값과 비교. O(n)으로 풀 수 있을 듯! 주어진 값과 비교할 요소값들을 모은 list를 s라고 하자. s+new가
[알고리즘] 소수판별, 투포인터, 구간합
소수1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수약수의 성질모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룸따라서 소수를 판별할 때, 가운데 약수까지만 확인하면 됨(Math.sqrt(x)다수의 자연수에 대하여
[백준] 1644 소수의 연속합
하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.3 : 3 (한 가지)41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)53 : 5+7+11+13+17 = 53 (두 가지)하지만
백준 2003번 : 수들의 합 2
링크 : https://www.acmicpc.net/problem/2003 아 진짜 마음에 안든다. 계속 쉽게 생각하려고 하니까 for문을 많이 쓰게 되고, 자연스럽게 연산 시간은 늘어나고, 시간이 늘어나니 틀리고, 이게 계속되니까 답답하다. 이 알고리즘은 망했다.
백준 7453번 - 합이 0인 네 정수(★★★ / X▲ / 2) : Python
풀이 시간 : 30분시간 제한 : 12초메모리 제한 : 1024MB기출 : 백준 7453번 문제링크 : https://www.acmicpc.net/problem/7453정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.Aa, Bb, Cc, Dd의 합
투 포인터 (Two Pointer)
정렬된 리스트를 두 개의 포인터를 이용해 순차적으로 접근하면서 두 포인터 구간의 값이 타겟 값과 같을 때 까지 포인터를 조작하는 기법을 말한다. 두 개의 포인터를 함께 활용할 때 얻을 수 있는 이점은 무엇일까? 투 포인터를 활용한 대표적인 예로 아래와 같은 문제가 있다
[BOJ 1981] 배열에서 이동 (Java)
BOJ 1981 배열에서 이동투포인터 + BFS 문제다. 투포인터는 두 변수가 변화하면서 상관관계를 만들어낼 때 사용하면 되는 것 같다? 또 모든 문제가 그렇듯이 주어진 문제를 단순화해야한다. 단순화의 가장 쉬운 방법이 변수를 고정하는 것이다.완전탐색으로 풀기에는 너무
[BOJ 2842] 집배원 한상덕 (Java)
BOJ 2842 집배원 한상덕이 문제는 투포인터 + 그래프 탐색 문제다. 방문한 칸 중 가장 높은 곳과 가장 낮은 곳의 차이가 피로도라고 한다. 이 때 가장 높은 곳과 가장 낮은 곳을 정하고 탐색 가능 여부에 따라서 가장 높은 곳과 가장 낮은 곳을 조정해나가면 된다.투
[BOJ 2143] 두 배열의 합 (Java)
BOJ 2143 두 배열의 합 문제풀이 주어진 A, B 배열에서 각각 합하여 나올 수 있는 모든 경우의 합을 리스트에 담는다. 첫 번째 리스트를 돌며 T - list[i] 가 두 번째 리스트에 있는지 확인한다. 어려운 문제였다... 모든 합의 경우를 가지고 있는 리
[BOJ 1208] 부분수열의 합2 (Java)
BOJ 1208 부분수열의 합2 문제풀이 일단 부분수열의 정의를 잘못알고 있어서 시간이 좀 걸렸다. 부분수열은 원래 수열의 일부 항을 원래 순서대로 나열한 것이다. 따라서 순서만 지킨다면 원래 수열에서 연속적으로 가져오지 않아도 된다.(나는 연속된 항만 가져와야한다고 생각했다...) BOJ 1182 부분수열의 합1 문제의 경우에 시간이 충분했다. 재귀함...
[BOJ 2003] 수들의 합2 (Java)
BOJ 2003 수들의 합2 문제풀이 짧은 시간 제한과 M의 엄청난 범위에 겁을 먹어서 고민을 많이 했지만 2중 반복문의 형태로 단순히 풀었더니 통과해버렸다. 하지만 이 문제는 알아보니 투 포인터를 사용하는 문제였다. 두 개의 포인터가 각자의 조건에 따라 움직이는 형태다. start는 합계가 M과 같거나 커질때 까지 계속 증가한다. end는 합계가 M과...