티스토리

JJ_blog

검색하기

블로그 홈

JJ_blog

hj39-develop.tistory.com/m

도전!

구독자: 1

방명록 방문하기

주요 글 목록

[백준] 2573 빙산 빙산의 덩어리 개수를 파악하기 위해서 자신 있게 dfs를 이용하여 문제를 풀었지만 결과는 시간초과 ㅜㅜ (dfs 안써..) □ 망한 코드.. ㅎ (잘못 나올 수 도 있어요!) vector input2573(301,vector(301,0)); vector modSea2573(301,vector(301,0)); vector check2573(301,vector(301,false)); int N2573, M2573; bool dfs2573(int x, int y, bool check){ if(x M2573) return false; if(check){ if(modSea2573[x][y] == 0 && input2573[x][y] != 0 && !check2573[x][y]){ int countSea = 0; .. 공감수 0 댓글수 0 2023. 5. 19.
[백준] 16974 레벨 햄버거 3 번째 예제를 보지 못하고 신나는 마음에 문제를 재귀로 쉽게 풀어내서 이게 실버문제라고..?라는 의문이 드는 순간 무려 4천조나 되는 숫자가 나와서 매우 당황..;; 처음에 신나는 마음에 푼 코드.. 는 정말 단순하게 있는 그대로 구현한 것 같다. 끙끙 헤매다가 결국 인터넷의 힘을 빌릴 수밖에..ㅜ 숫자가 매우 커서 재귀를 무작정 돌리는 경우 시간초과가 나는 것은 무조건이다. 따라서 DP를 이용하여 풀어야 하는데 솔직히 막막하다. 햄버거 재료 개수랑 패티 개수를 저장할 배열을 생성한 후 미리 개수를 저장해 놓는다. 그리고 우리가 구하고 싶은 것은 패티! 의 개수가 중요하니까 모든 코드는 패티의 개수에 맞춰서 짠다. 우선 전체 코드 공개! #include #define fast ios::sync_with.. 공감수 0 댓글수 0 2023. 5. 19.
[백준] 10974 모든 순열 이 문제는 N과 M 시리즈 문제를 풀었다면 정말 눈감고(?)도 풀 수 있다. #include using namespace std; vector arr10974; vector check10974(9,0); void backback10974(int N, int count){ if(N == count){ for(int i=0;i 공감수 0 댓글수 1 2023. 5. 17.
[백준] 10819 차이를 최대로 문제를 읽고 예제를 봤을 때 왜 62가 나오는지 몰랐다.(하핳) 그래서 문제에서 알려준 식을 가지고 코드로 변환하여 작성했더니 정말 62가 나와서 놀랬다.ㅎ #include using namespace std; int N10819; int maxNum = -INT_MAX; vector input10819; vector check10819(9,false); vector tmp10819; void backback10819(int count){ if(count == N10819){ int sum = 0; for(int i=0; iN10819; for(int i=0;i>a; input10819.push_back(a); } backback10819(0); cout 공감수 0 댓글수 0 2023. 5. 17.
[백준] 2580 스도쿠 이 문제가 왜 골드 4인지 잘 모르겠다..ㅋ 빈칸에 전부 다 대입을 한 후 반복문을 돌리면서 확인하는 경우의 수는 너무 많이 나오고 시간초과가 발생할 확률이 매우 높다. 따라서 빈칸에 적당한 값을 넣기 전에 같은 행, 열, 블록을 검사한 후 같은 숫자가 없는 경우 대입하는 방법으로 문제를 해결해야 한다. #include using namespace std; vector input2580(10,vector(10,0)); vector zeroPos2580; bool complete2580 = false; bool checkValidSudo(int x, int y){ // 세로 가로줄 검사 for(int i=1; i 공감수 0 댓글수 0 2023. 5. 16.
[백준] 1987 알파벳 정말 순수하게 알파벳이 지나온 길을 저장한 뒤에 한번 재귀가 돌때마다 반복문을 돌며 저장된 알파벳을 탐색하는 방식으로 풀었다. 그런데 바로 시간초과 ㅜㅜ □ 해결은 됐지만 시간초과가 된 코드 #include using namespace std; int R1987, C1987; vector input1987(21,vector(21,NULL)); vector check1987(21,vector(21,false)); vector doneAlpha1987; int result1987 = 0; bool checkAlphabet1987(char now, int count){ for(int i=0;iR1987>>C1987; for(int i=1;ia; input1987[i][j] = a; } } backback198.. 공감수 0 댓글수 0 2023. 5. 15.
[백준] 1182 부분 수열의 합 부분 수열을 더하면서 입력한 값과 같게 되는 경우의 수를 구하는 문제인데 백트래킹의 기본적인 문제인데 출력값이 자꾸 하나씩 더 나와서 당황했다. 원인은 원하는 값이 0인 경우 count값이 0부터 시작하여 값이 한개 더 추가된다는 것 이였다. 그래서 조건문에서 count가 1부터 통과되록 조건을 추가 시켜서 해결하였다. #include using namespace std; vector input1182(21,0); vector check1182(21,false); int N1182,S1182; int result1182 = 0; void backback1182(int count, int pos, int sum){ if(sum == S1182 && count > 0) result1182 ++; if( co.. 공감수 0 댓글수 0 2023. 5. 15.
[백준] 1759 암호만들기 약간의 백트래킹 방법에서 살짝만 바뀐 방법으로 문제를 해결할 수 있다. 일반적으로라면 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.. 공감수 0 댓글수 0 2023. 5. 15.
[백준] 6603 로또 주어진 오름차순 수열을 가지고 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 공감수 0 댓글수 0 2023. 5. 15.
[백준] 14502 연구소 문제를 해결하는 아이디어는 가장 넓은 안전 영역을 구하는 것이므로 벽을 설치한 후 바이러스를 퍼트려보고 완료된 그래프를 탐색하여 안전영역의 개수를 출력하면 되는 문제이다. 바이러스를 퍼트리고 안전영역을 찾는건 정말 쉬운 문제인데.. 이놈의 벽..! 해당 문제를 처음 딱 읽고 이해는 갔지만 이 벽이 문제였다. 벽 3개를 어떻게 배치를 할 것인가.. 처음에 반복문을 이용하여 배치를 해보았지만 내 구현 능력이 부족한지 계속해서 실패하였다. ㅜㅜ 결국.. 인터넷의 힘을 빌릴 수 밖에..ㅠ 재귀를 이용하여 벽을 세우는데 약간 신기했다. (새로운 패턴 익히는 중) □ 소스코드 #include using namespace std; vector inputOrginal14502(9,vector(9,0)); vector .. 공감수 0 댓글수 0 2023. 5. 7.
[백준] 2468 안전영역 솔직히 처음 문제를 읽었을 때 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,.. 공감수 0 댓글수 0 2023. 5. 7.
[백준] 4963 섬의 개수 대각선이 포함하여 덩어리 개수를 세면 되는 문제이다. 상하좌우 덩어리를 세는 문제에서 활동 범위를 대각선으로만 늘리면 해결 할 수 있다. □ 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.. 공감수 0 댓글수 0 2023. 5. 7.
[백준] 10026 적록색약 약간 새로운 패턴의 문제였다. 그냥 약간의 노가다(?) 문제 일반인의 덩어리를 세는 부분은 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] ){.. 공감수 0 댓글수 0 2023. 5. 7.
[백준] 11724 연결 요소의 개수 해당 문제는 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 공감수 0 댓글수 0 2023. 5. 7.
[백준] 2018 수들의 합 5 투포인터를 이용하여 연속한 숫자의 합이 입력 값 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 공감수 0 댓글수 0 2023. 5. 5.
[백준] 1780 종이의 개수 종이의 개수 문제는 이전에 블로그에 올렸던 색종이 만들기 문제와 완전 똑같다. #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.. 공감수 0 댓글수 0 2023. 5. 4.
[백준] 1992 쿼드 트리 이전에 블로그에 올렸던 문제 색종이 만들기 문제와 매우 유사한 문제지만 출력방식이 다르다. 처음에 문제를 봤을 때 이해가 정말 안됐었다.. 색종이 만들기 문제는 파란색, 하얀색 종이의 개수를 구하는 문제라면 해당 문제는 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등분.. 공감수 0 댓글수 0 2023. 5. 4.
[백준] 2630 색종이 만들기 해당 문제는 주어진 그래프에서 파란색 종이와 하얀색 종이의 개수를 구하는 문제이다. 예시로 주어진 그래프를 보다보면 패턴이 보이는데 처럼 숫자가 다른경우 계속 쪼개지면서 종이가 나누어 지게 된다. 따라서 재귀함수를 이용해서 개수를 구하면 된다. 처럼 N을 먼저 탐색해보고 숫자가 다른게 하나라도 있다면 반으로 줄이는 방식으로 문제를 해결하면 된다. #include using namespace std; vector input2630(130,vector(130,0)); int blueCount2630 = 0; int whiteCount2630 = 0; void divide2630(int N, int x, int y){ if(N==1){ if(input2630[x][y] == 1) blueCount2630++;.. 공감수 0 댓글수 0 2023. 5. 4.
[백준] 17478 재귀함수가 뭔가요? 재귀함수에 약간의 감을 잡기 위한 문제이다. 재귀를 쓰기전에는 약간의 패턴을 분석하면 쉽게 풀 수 있다. #include using namespace std; void recursive17478(int N, int start){ for(int i=0;i 공감수 0 댓글수 0 2023. 5. 4.
[백준] 9084 동전 배낭 관련 문제들 2문제를 풀고 약간의 고뇌의 시간(?)을 보내니까 약간 어느 정도 감이 올 듯 말 듯 한 거 같다. 예제로 나온 수들은 너무 크기 때문에 내 마음대로 돈의 크기를 대폭 줄여서 생각해 보았다. N= 3, M= 20 동전의 종류: 1, 5, 10 n=5인 행의 10열 에 해당하는 숫자 3은 5원, 1원짜리 동전으로 구성할 수 있는 경우의 수를 계산한 값이다. 배낭 문제에서 흔히 나오는 방식은 j-array[i]를 이용하니 쉽게 규칙을 파악할 수 있었다.. □ 소스 코드 #include using namespace std; void coin9084(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int testCase; cin>.. 공감수 0 댓글수 0 2023. 4. 26.
[백준] 7579 앱 배낭 관련된 문제들을 풀때 2차원 배열에 어떤 값을 넣어야 풀 수 있는지 아직 감이 잡히지 않는 것 같다. 배낭 유형 문제들을 풀면서 감을 익혀야 할 것 같다. 문제 - 1 페이지 www.acmicpc.net 이번 문제도 삽질을 좀 많이 했다.. 2차원 배열에서 행: 입력 횟수, 열: 비용으로 생각하고 풀면 되지만 열에 해당하는 최댓값은 입력받은 모든 비용의 합으로 해야한다. #include #define BYTE 1 #define COST 0 using namespace std; void app7579(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N,M; cin>>N>>M; vector App(N+1); int dp[N+1][1.. 공감수 0 댓글수 0 2023. 4. 26.
[백준] 12865 평범한 배낭 배낭 알고리즘은 DP의 대표적인 문제라고 한다. (사실 처음 봄.. ㅎ) 문제를 풀고 보니 앞선 문제에서 사용했던 LCS 푸는 방법과 유사했다. 예시를 통해서 알아보자 (백준 예제를 살짝 변형한 예제이다) 다음과 같이 입력을 받았다고 하자 index는 arr 배열에서의 index를 의미한다 여기서 weight = 0, value = 1이다. ex) arr [1][weight] = 6, arr [1][value] = 13 LCS 알고리즘에서 DP table에 값을 저장할 때 해당 값의 유무가 아닌 이전 값을 고려하여 정보를 저장했다. (먼저 혼자서 끄적여 본 표..) 위 표에서 자세하게 봐야할 부분은 (n=3, k=7)인 부분이다. arr에서 (n>n>>k; int arr[n+1][2]; int dp[n+.. 공감수 0 댓글수 0 2023. 4. 18.
[백준] 1958 LCS 3 LCS 2와 다르게 이번에는 3개의 문자열을 받아서 처리하는 문제이다. LCS 2에서 두개의 문자열을 비교할 때 반복문 2번을 돌렸다면 이번에는 3번을 돌리면 된다. □ 소스 코드 void LCS1958(){ ios::sync_with_stdio(false); cin.tie(NULL); string arr1, arr2, arr3; cin >> arr1 >> arr2 >> arr3; int LCS[101][101][101] = {0}; for(int i=0;i 공감수 0 댓글수 1 2023. 4. 16.
[백준] 9251, 9252 LCS 1,2 2중 반복문을 돌려서 해당 문자열까지 겹치는 횟수를 2차원 배열에 기록하는 방법으로 문제를 해결했다. 여기서 중요한 것은 2차원 배열에 기록을 할 때 문자 하나하나를 비교해서 기록하는 것이 아닌 문자열과 비교해서 기록해야 한다는 것이다. 예를 들어 왼쪽 문자열(ACAYKP)에서 부분 문자열 A와 위쪽 문자열(CAPCAK)에서 부분문자열 C와 비교한다면 A와 C는 겹치는 부분이 없으므로 0이 된다. 그다음 왼쪽 문자열(ACAYKP)에서 부분 문자열 AC와 위쪽 문자열(CAPCAK)에서 부분문자열 C를 비교해 보면 AC와 C는 겹치는 문자가 C 하나가 있다. 따라서 해당 부분에 1을 기록한다. 그다음 왼쪽 문자열(ACAYKP)에서 부분 문자열 ACA와 위쪽 문자열(CAPCAK)에서 부분문자열 C를 비교해 보.. 공감수 0 댓글수 0 2023. 4. 16.
[백준] 2565, 2568 전깃줄 1, 2 전깃줄 문제를 처음 접했을 때 앞에 가장 긴 시리즈 문제들을 해결을 한 상태라서 되게 쉽게 느껴졌다. 그림을 본 순간 든 생각은 A와 연결된 B애들을 순서대로 적어보자! 였다. 적자마자 수열이 떠올랐다. ㅋㅋ 해당 수열을 가지고 가장 긴 증가하는 수열을 찾고 전체 길이에서 빼주면 답이 나온다. ㅎㅎ 가장 긴 시리즈에서 유용하게 사용했던 Dp + 이진탐색을 활용해서 문제를 해결했다. 전깃줄 2 길이를 구하는 건 쉬운데 또 부분 수열의 요소들을 찾으랜다. 이것 역시 가장 긴 수열 시리즈에서 했던 역추적 방법을 사용하면 풀 수 있다. 역추적을 하고 나면 위에서 작성했던 가장 긴 부분 수열은 {1, 4, 6, 7, 10}이 나오게 된다. 그러면 {8, 2, 9, 1, 4, 6, 7, 10}에서 가장 긴 부분 수.. 공감수 0 댓글수 0 2023. 4. 16.
[백준] 11054 가장 긴 바이토닉 부분 수열 이 문제는 어렵다기보다 아이디어 차이인 것 같다. 문제를 해결한 방법으로 DP를 사용하였다. 일반적인 Dp방법으로 1. (앞 → 뒤) 방향으로 dpI를 담는다. 2. (뒤 → 앞) 방향으로 dpD를 담는다. 그 이후 두 dp들을 더한다. 더한 후 가장 값이 큰 요소를 찾은 다음 1을 뺀다. 소름 돋게 간단하다. □ 소스 코드 void bye11054(){ int n; scanf("%d",&n); vector array; vector dpI(n); vector dpD(n); for(int i=0;i 공감수 0 댓글수 0 2023. 4. 16.
[백준] 14002, 14003 가장 긴 증가하는 부분 수열 4,5 수열 문제를 풀다 보니 4,5번까지 오게 됐다! 14002, 14003은 앞선 문제들(12015, 12738)과 다르게 부분 수열의 최대 길이뿐만 아니라 부분 수열도 출력을 해야 한다. 물론 Dp 방식으로 문제를 풀면 14002는 해결할 수 있지만 14003은 범위 때문에 시간초과로 해결하지 못한다. 이번 문제에서도 아래 문제에서 풀 듯이 이진탐색을 섞어서 풀었다. [백준] 12015, 12738 가장 긴 증가하는 부분 수열 2,3 11053, 12015, 12738 모두 같은 입력 같은 출력을 하지만 범위만 다르다! 11053 12015 12738 수열A 크기 1 ~ 1,000 1 ~ 1,000,000 1 ~ 1,000,000 수열 A 요소의 범위 1 ~ 1,000 1 ~ 1,000,000 -1,000.. 공감수 0 댓글수 0 2023. 4. 16.
[백준] 12015, 12738 가장 긴 증가하는 부분 수열 2,3 11053, 12015, 12738 모두 같은 입력 같은 출력을 하지만 범위만 다르다! 11053 12015 12738 수열A 크기 1 ~ 1,000 1 ~ 1,000,000 1 ~ 1,000,000 수열 A 요소의 범위 1 ~ 1,000 1 ~ 1,000,000 -1,000,000,000 ~ 1,000,000,000 [백준] 11053 가장 긴 증가하는 부분 수열 DP 배열을 푸는 방법을 알고 있다면 엄청 어렵지 않게 해결할 수 있다. 1~n까지 반복문을 돌면서 이전에 받았던 값들을 다시 탐색하면서 찾아가는 방식으로 문제를 해결했다. □ DP 이용 int n; scanf( hj39-develop.tistory.com 11053을 공부할때 Dp로 푸는 방법과 이진 탐색을 이용해서 푸는 방법을 공부 했었다.. 공감수 0 댓글수 0 2023. 4. 16.
[백준] 11055 가장 큰 증가하는 부분 수열 이번 문제는 11053과 다르게 가장 긴 수열의 길이를 찾는 게 아닌 증가하는 수열들 중에서 가장 큰 합을 가지는 부분 수열을 찾는 문제이다. 11053에서 찾은 새로운 방법(이진 탐색)으로 합을 찾아보려고 했지만.. 할 수 없는 건지 실력이 부족한 건지 풀 수가 없었다. ㅠㅠ 더 공부한 후에 다시 도전해 봐야지 그래서 결국 DP를 이용하여 문제를 해결했다. 11053에서 DP를 이용한 방법과 아주 유사하다. 앞선 문제에서는 dp 배열에 길이를 저장했다면 이번 문제에서는 dp 배열에 원소의 합을 저장해 주면 된다. □ 소스코드 void best11055(){ int n; scanf("%d",&n); int array[1001] = {0}; int dp[1001] = {0}; for(int i=1;i 공감수 0 댓글수 0 2023. 4. 15.
[백준] 11053 가장 긴 증가하는 부분 수열 DP 배열을 푸는 방법을 알고 있다면 엄청 어렵지 않게 해결할 수 있다. 1~n까지 반복문을 돌면서 이전에 받았던 값들을 다시 탐색하면서 찾아가는 방식으로 문제를 해결했다. □ DP 이용 int n; scanf("%d",&n); int dp[1001] = {0}; int array[1001] = {0}; for(int i=1;i 공감수 0 댓글수 0 2023. 4. 15.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.