🐸 Problem Solving

🔗 문제 링크 : https://www.acmicpc.net/problem/15652  문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.     입출력 예시입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)  출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.  ..

🔗 문제 링크 : https://www.acmicpc.net/problem/15651  문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.     입출력 예시입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)  출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.        풀이 앞 문제들보다 간단해진(?) 백트래킹 문제이다.n번째 수를 선택하는 함수 Sol()을 호출하고 이후 n+1를 인자로 넘기..

🔗 문제 링크 : https://www.acmicpc.net/problem/15650  문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다.     입출력 예시입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)  출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.       풀이 백트래킹으로 해결 가능한 문제이다. 백준 15649번: N과 M (1) 문제와 유사하나, 고른 수열은 오름차순이어야..

🔗 문제 링크 : https://www.acmicpc.net/problem/15649  문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열     입출력 예시입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)  출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.        풀이 백트래킹 기초에 도움이 되는 문제이다. 몇 번째 수까지 사용했는지를 n에 담아서 재귀 호출을 한다. (다음 재귀 호출은 n + 1) 1~N 까지..

🔗 문제 링크 : https://www.acmicpc.net/problem/10026  문제적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에RRRBBGGBBBBBBRRBBRRRRRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강..

🔗 문제 링크 : https://www.acmicpc.net/problem/7576  문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익..

🔗 문제 링크 : https://www.acmicpc.net/problem/2003  문제N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.     입출력 예시입력첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.  출력첫째 줄에 경우의 수를 출력한다.       풀이 #include #include using namespace std;int mai..

🔗 문제 링크 : https://www.acmicpc.net/problem/13144  ☁ 어떻게 해야 투포인터를 더 효율적으로 움직일 수 있을지.. 수많은 고민을 하며 풀었던 문제 아직 투포인터 구현이 미숙했기에 첫 접근 방식부터가 잘못됐었다.투포인터를 구현하면서 중복 확인 부분을 unordered_set을 이용하는 방법을 택했는데, 갈수록 복잡해지는 코드에 잘못된 길(?)을 걷고 있음을 깨달았다. 투포인터조차 제 기능을 못 하는 상황까지.. 🥊  결과적으로, 배열을 이용하여 현재 숫자의 빈도를 카운트를 하고, 중복이 발생하면 투포인터의 움직임으로 구간의 중복을 제거하며, 중복이 없는 구간에서 가능한 경우의 수를 누적해 나가도록 구현한 코드가 최종 정답이 되었다.   역시 다양한 유형의 문제를 풀..

🔗 문제 링크 : https://www.acmicpc.net/problem/3273  문제n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i     입출력 예시입력첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)  출력문제의 조건을 만족하는 쌍의 개수를 출력한다.       풀이 수열은 서로 다른 양의 정수로 이루어졌다. -> 중복되는 수가 없다.(1 ≤ i 예를 들어, 1 3 7 5 인 수열에서 합이 10이 되..

🔗 문제 링크 : https://www.acmicpc.net/problem/1406  문제한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다. 이 편집기가 지원하는 명령어는 다음과 같다. L : 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)D : 커서를 오른쪽으로 한 칸 옮김 (커서가..