JJ_blog

약간의 백트래킹 방법에서 살짝만 바뀐 방법으로 문제를 해결할 수 있다. 일반적으로라면 count를 증가시켜 확인 후 return; 하지만 해당 문제는 모음 개수와 자음 개수를 따로 계산하여 가져가야한다. 나머지는 백트래킹 하듯이 하면 해결할 수 있다. #include using namespace std; int L1759, C1759; vector input1759; vector result1759; vector check1759(16,false); char vowelList1759[] = {'a','e','i','o','u'}; void backback1759(int pos, int vowelCount, int conCount){ if(vowelCount + conCount == L1759 and vo..

주어진 오름차순 수열을 가지고 6개의 숫자를 뽑아 출력하는 문제이다. 백트래킹을 활용하면 문제를 쉽게 해결할 수 있다. #include using namespace std; vector input6603; vector check6603(14,false); vector result6603; int K6603; void backback6603(int count, int pos){ if(count == 6){ for(auto& i: result6603){ cout

문제를 해결하는 아이디어는 가장 넓은 안전 영역을 구하는 것이므로 벽을 설치한 후 바이러스를 퍼트려보고 완료된 그래프를 탐색하여 안전영역의 개수를 출력하면 되는 문제이다. 바이러스를 퍼트리고 안전영역을 찾는건 정말 쉬운 문제인데.. 이놈의 벽..! 해당 문제를 처음 딱 읽고 이해는 갔지만 이 벽이 문제였다. 벽 3개를 어떻게 배치를 할 것인가.. 처음에 반복문을 이용하여 배치를 해보았지만 내 구현 능력이 부족한지 계속해서 실패하였다. ㅜㅜ 결국.. 인터넷의 힘을 빌릴 수 밖에..ㅠ 재귀를 이용하여 벽을 세우는데 약간 신기했다. (새로운 패턴 익히는 중) □ 소스코드 #include using namespace std; vector inputOrginal14502(9,vector(9,0)); vector ..

솔직히 처음 문제를 읽었을 때 N이 비가 내리는 양을 포함하는 줄 알고 풀었다. 신기하게 문제에서 제공해 주는 예제들이 모두 통과가 되었다 ㅋㅋㅋ 그리고 제출했더니.; 틀렸습니다 (눈물..) 문제를 조금 꼼꼼하게 읽어보니 안전영역이 덩어리 지는 최대의 개수를 구하는 것이었다...!! 바로 수정.. 어렵지 않고 쉬운 문제였다. □ 소스코드 #include using namespace std; vector input2468(101,vector(101,0)); vector check2468(101,vector(101,false)); int count2468 = 0; int rain2468 = 0; queue q2468; void bfs2468(int N,int x, int y){ int dx[] = {0,0,..

대각선이 포함하여 덩어리 개수를 세면 되는 문제이다. 상하좌우 덩어리를 세는 문제에서 활동 범위를 대각선으로만 늘리면 해결 할 수 있다. □ bfs 버전 #include using namespace std; vector input4963(51,vector(51,0)); vector check4963(51,vector(51,false)); queue q4963; void bfsIsland4963(int N, int M, int x, int y){ int dx[] = {0,0,1,-1,1,-1,1,-1}; int dy[] = {1,-1,0,0,1,1,-1,-1}; while (!q4963.empty()) { int frontX = q4963.front().first; int frontY = q4963.fro..

약간 새로운 패턴의 문제였다. 그냥 약간의 노가다(?) 문제 일반인의 덩어리를 세는 부분은 R,G,B를 모두 나누어 개수를 세면 되지만 적록색약의 덩어리를 세는 부분은 (R,G), B를 나누어 개수를 세면 끝이다 쉽죠? □ 소스코드 #include using namespace std; vector input10026(101,vector(101,0)); vector check10026(101,vector(101,false)); vector checkNotRG10026(101,vector(101,false)); bool dfsBlue10026(int N, int x, int y){ if(xN) return false; if(input10026[x][y] == 'B' && !check10026[x][y] ){..

해당 문제는 1차원 배열을 이용하여 해결할 수 있는 문제이다. dfs로 구현하였고, 헷갈리지만 않는다면 쉽게 풀 수 있다. □ 소스코드 #include using namespace std; vector input11724[1001]; vector check11724(1001,false); void dfs11724(int x){ check11724[x] = true; for(int i=0;i>N>>M; for(int i=0;i>a>>b; input11724[a].push_back(b); input11724[b].push_back(a); } int result = 0; for(int i=1;i

투포인터를 이용하여 연속한 숫자의 합이 입력 값 N과 같아지는 경우의 수를 찾는 문제이다. first, second 두 변수를 이용하여 sum N 경우 first를 증가시켰다. #include using namespace std; void num2018(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin>>N; int count = 0; int first = 1; int second = 1; int sum = 0; while(1){ if(sum == N) count++; if(first == N ) break; if(sum N){ sum -= first; first++; } } if(N==1) cout

종이의 개수 문제는 이전에 블로그에 올렸던 색종이 만들기 문제와 완전 똑같다. #include #define MAXARANGE 2200 using namespace std; vector input1780(MAXARANGE,vector(MAXARANGE,0)); int minusOneCount = 0; int oneCount = 0; int zeroCount = 0; void recursive1780(int N, int x, int y){ if(N==1){ if(input1780[x][y] == 1) oneCount++; else if(input1780[x][y] == 0) zeroCount++; else if(input1780[x][y] == -1) minusOneCount++; return; } boo..

이전에 블로그에 올렸던 문제 색종이 만들기 문제와 매우 유사한 문제지만 출력방식이 다르다. 처음에 문제를 봤을 때 이해가 정말 안됐었다.. 색종이 만들기 문제는 파란색, 하얀색 종이의 개수를 구하는 문제라면 해당 문제는 1과 0이 정사각형 모양으로 반복되는 구간이 있다면 1로 압축하는 문제이다. 예를들어 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 이와 같이 주어진 경우 (10(1100)1)로 출력할 수 있다. 4등분을 먼저 하면 아래와 같이 볼 수 있다. 1번 2번 3번 4번 1번의 경우 모두 같은 숫자 1로 구성되어 있으므로 1로 압축을 할 수 있다. 2번의 경우에도 0으로 모두 구성되어 있으므로 0으로 압축할 수 있다. 3번의 경우 1과 0이 섞여 있으므로 다시 한번 재귀를 통해 4등분..