분류 전체보기

https://www.acmicpc.net/problem/4963 문제 설명각 테스트 케이스마다 w와 h가 주어진다. w * h 크기의 배열이 주어지는데, 1은 땅을, 0은 바다를 의미한다.땅은 가로, 세로, 대각선으로 움직일 수 있다. 각 테스트 케이스별로 연결된 땅의 개수를 구하는 문제이다.마지막 테스트 케이스이라면 w와 h값으로 0이 주어진다  주요 로직1. 그래프 탐색 문제이다각 테스트 케이스마다 visited배열을 0으로 초기화하고 깊이 우선 탐색으로 배열을 탐색한다 정답 코드#include using namespace std;int w,h, arr[55][55], visited[55][55];int dy[8] = {-1,-1,0,1,1,1,0,-1}, dx[8] = {0,1,1,1,0,-1,-..

https://www.acmicpc.net/problem/2230 문제 설명n개의 정수로 이루어진 수열이 주어진다.이 수열 중 두 수를 골랐을 때 그 차이가 M이상이면서 제일 작은 경우를 구하는 문제이다.  주요 로직1. 투 포인터수열을 정렬한 다음에 i와 j를 선언해 탐색하면서 최적의 값을 찾아 낸다 2. 최솟값 설정 - 1,000,000,000  정답 코드#include using namespace std;int n,m,x;vector v;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for(int i=0; i> x; v.push_back(x); } sort(v.begin(), v..

https://www.acmicpc.net/problem/2661 문제 설명좋은 수열이란 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 없는 수열을 뜻한다.예를 들어 33, 32121323 은 나쁜 수열이고 32, 32123은 좋은 수열이다.길이가 n인 좋은 수열들을 찾아 그 중 가장 작은 수를 출력한다 주요 로직1. 백트래킹1,2,3 중 숫자 하나씩을 추가하면서 현 상황에서 좋은 수열인지 확인을 하고 아니라면 stop, 맞다면 계속 탐색한다. 2. n의 범위처음에 go(int num, int size)로 num을 string이 아닌 int로 설정했었다. n의 범위가 80이하이기 때문에 80자리의 수까지 탐색할 수 있어야 하는 데 int는 약 20억 범위이기에 10자리까지만 탐색할 수 있다. 그..

https://www.acmicpc.net/problem/11660 문제 설명2차원 배열이 주어졌을 때, (y1,x1)부터 (y2,x2)까지의 합을 구하는 문제이다. 주요 로직1. 누적합을 사용하는 것이다.n의 범위가 1024까지이기에 이중 for문을 사용해서 문제를 풀면 시간 초과가 발생한다 i행 j열의 누적합 구하기pfix[i][j]는 1행부터 i행까지, 1열부터 j열까지의 모든 수의 합을 구한 값이다.pfix[i][j] = pfix[i-1][j] + pfix[i][j-1] - pfix[i-1][j-1] + arr[i][j]; (y1,x1)부터 (y2,x2)까지의 합 구하기pfix[y2][x2] - pfix[y1-1][x2] - pfix[y2][x1-1] + pfix[y1-1][x1-1] 정답 코드#..

https://www.acmicpc.net/problem/14889  문제 설명n x n 배열이 주어졌을 때, 두 팀으로 나누어서 두 팀간의 능력치 차가 최소가 되는 경우를 출력하는 문제이다.i번째와 j번째가 같은 팀이 되었을 때 능력치는 S(i,j) + S(j,i)이다. 주요 로직1. 비트 마스킹이다.-> 두 팀을 나누는 모든 경우의 수를 따져야 하므로 비트마스킹으로 경우마다 두 팀의 인원이 같은지 확인하고 능력치를 구하면 된다. 정답 코드#include using namespace std;int n,ret=987654321,arr[24][24];int check(vector v){ int sum = 0; for(int i=0; i> n; for(int i=0; i> arr[i][j]; } } fo..

https://www.acmicpc.net/problem/3273 문제 설명n개의 숫자가 주어질 때 이 중 두개의 숫자를 뽑아 합이 x가 되도록 하는 경우가 총 몇 개인지를 출력하는 문제이다. 주요 로직1. 투포인터 문제이다-> n개의 숫자를 받아 정렬한 후, 두 개의 포인터로 탐색한다. 정답 코드#include using namespace std;int n,x,ret;vector v;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for(int i=0; i> x; v.push_back(x); } cin >> x; sort(v.begin(), v.end()); int low=0, high=n..

https://www.acmicpc.net/problem/1644 문제 설명n이 주어질 때, 연속된 소수의 합으로 n이 만들어지는 경우의 수를 찾는 문제이다. 주요 로직1. 소수 찾는 로직-> 에라토스테네스의 체를 통해 소수를 찾는다. 2. 투 포인터로 경우의 수 찾는 로직-> 두개의 포인터인 i,j를 통해 합이 n이 되는 경우의 수를 찾는다. 정답 코드#include using namespace std;int n,ret;bool che[4000004];vector era(int n){ vector v; for(int i=2; i> n; vector v = era(n); int i=0,j=0; while(i

https://www.acmicpc.net/problem/1931 문제 설명n개의 회의 시작 시간과 회의 끝나는 시간이 주어질 때, 최대로 사용할 수 있는 회의의 최대 개수를 출력하는 문제이다. 주요 로직1. 정렬이다.-> 회의가 끝나는 시간 기준으로 정렬을 해야한다. 정답 코드#include using namespace std;int n, s, e;vector> v;bool cmp(pair a, pair b){ if(a.second == b.second) return a.first > n; for(int i=0; i> s >> e; v.push_back({s,e}); } sort(v.begin(), v.end(), cmp); int cnt = 0; int time = 0; for(auto it ..

https://www.acmicpc.net/problem/1781  문제 설명데드라인과 컵라면의 수가 주어졌을 때, 데드라인 내에 문제를 풀면 해당 컵라면을 받을 수 있다받을 수 있는 최대 컵라면의 수를 구하는 문제이다. 주요 로직1. 그리디 문제이기에 우선순위 큐를 통해 풀어야 한다.-> 오름차순의 우선순위 큐를 선언하여 하나씩 넣고 데드라인을 넘어서면 pop()한다. 정답 코드#include using namespace std;int n, d, c;vector> v;priority_queue, greater> pq;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for(int i=0; i> d..

https://www.acmicpc.net/problem/9935  문제 설명tmp1과 tmp2라는 문자열이 주어진다. 이 때, tmp1에 tmp2라는 문자열이 있으면 tmp1에서 사라진다. tmp1에 tmp2라는 문자열을 없앤 남아 있는 문자열을 출력하는 문제이다. 존재하지 않는 경우엔 "FRULA"라는 문자열을 출력한다. 주요 로직1. 문자열의 substr() 과 erase() 함수를 사용한다.-> tmp1의 i번째 문자가 tmp2의 마지막 문자와 동일한 경우에 substr() 함수로 확인해 tmp2 문자열이 있는 경우 삭제하도록 구현했다.  정답 코드#include using namespace std;char c;string tmp1, tmp2, str;int main(){ ios_base::syn..