반갑습니다!

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..

개념 잘 모르고 있다가 투포인터라는 알고리즘에 대해 듣게되어 공부할겸 포스팅을 작성한다. 일반적으로 연속된 수들의 합을 구할 때 자주 사용된다고 한다. 기본 원리는 두 개의 인덱스를 이용하여 두 인덱스의 범위를 조절하여 정답을 찾는 방식이다. 예시를 보며 이해해보자. 크기가 10인 자연수 배열이 있고, 연속된 숫자들의 합이 5가 되는 경우의 개수를 찾아야한다고 가정하자. 투포인터 알고리즘에서는 인덱스를 2개로 지정한다. s와 e라고 하자. 그리고 두개의 인덱스를 통한 범위는 [s, e)라고 가정할 것이다. 초기에는 s = 0, e = 0이고, [s, e) 범위 내의 숫자의 합은 0이므로 M보다 작다. 따라서 e의 값을 1 증가시킨다. 위 그림의 경우 [s, e) 범위 내 숫자의 합은 1이 되었지만 아직도..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 그리디로 접근하여 해결할 수 있다. A와 B를 내림차순으로 정렬한 뒤, 순차적으로 비교하면서 B가 A보다 큰 경우에는 B의 인덱스를 증가시키면서 개수를 세면 된다. 코드 #include #include #include using namespace std; int solution(vector A, vector B) { int answer = 0; sort(A.rbegin(), A.rend()); sort(B.rbegin(), B.rend()); int idx1 = 0, idx2 = 0; for (int i..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 숫자 사이의 관계를 생각해보면 쉽게 해결할 수 있다. n이 8, a는 3, b는 7인 경우를 생각해보자. 1번과 2번 중에서 승리하는 참가자는 1이 된다. 3번과 4번 중에서 승리하는 참가자는 2가 된다. 5번과 6번 중에서 승리하는 참가자는 3이 된다. 7번과 8번 중에서 승리하는 참가자는 4가 된다. 두 명 중 한명만 살아남기 때문에 라운드가 지나갈수록 참가자의 수는 절반으로 줄어들게 된다. 다음에 부여받는 숫자의 규칙을 찾아보면 i번째 참가자는 다음 라운드에서 i/2 + i%2번을 부여받음을 알 수..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 블록이 제거되는 것과 블록이 제거되어 위에 쌓인 블록이 내려오는 부분을 잘 구현하면 쉽게 구현할 수 있다. 코드 #include #include #define REMOVE 3 using namespace std; int N, M; bool finish = false; int chk[31][31]; // 2x2 사각형을 검사하는 함수 void checkBlock(vector& board, int x, int y) { char c = board[y][x]; if (c == ' ') return; // 2x2..