C++ 알고리즘

☆☆☆☆★윤년을 구하는 문제for, if문 사용하는 기초문제https://github.com/jeongopo/DaliyCodeCpp/blob/master/code2753.cpp

★☆☆☆☆9개의 값을 입력받아 최솟값을 구하는 문제C++ 줄넘김 방식을 몰라서 조금 헤맸음https://github.com/jeongopo/DaliyCodeCpp/commit/32418fba06d7c830533126b70a6332d1c2f661e4

★★☆☆☆입력받은 문자열에서 단어의 개수를 찾는 문제띄어쓰기의 개수만 세면 되는 줄 알고 엄청 짧게 코딩했는데문자열의 맨앞과 맨뒤에 있는 케이스를 처리하기 위해서 약간의 처리가 더 필요했음입력에서 배재했던 공백이 여러번 들어가있는 케이스도 동시에 처리했음https&#x

★☆☆☆☆3개의 숫자 입력을 받아 손익분기점을 계산하는 문제일차방정식을 이용해서 수식을 구하면 되는 문제라 어렵지 않았음https://github.com/jeongopo/DaliyCodeCpp/blob/master/code1712.cpp

★☆☆☆☆n번의 테스트 케이스의 덧셈 결과를 보여주면 되는 문제https://github.com/jeongopo/DaliyCodeCpp/blob/master/code10950.cpp

★★★☆☆처음에 문제 이해를 제대로 안하고 시작해서, 중간에 1을 여러번 빼는 케이스에 대해 처리하지 않았다뒤늦게 코드를 수정해서 Bottom-up 방식으로 재귀함수를 써서 결과를 구했는데 오답처리가 되었다높은 수로 올라가면 문제가 발생하는 것으로 보이는데, 조건을 좀

★★★☆☆내가 DP에 진짜 약하다는걸 느낀 문제,,자꾸 큰 수부터 내려가면서 생각하는데, 중복되는 경우의 수가 있을 수 있다고 생각해서 식이 점점 복잡해졌다결국 1시간 넘겨서 인터넷 참고해보니 피보나치와 같은 원리DP에 대한 기본 개념이 부족한것같다https:

★★☆☆☆DP 기초문제. 앞의 DP 두 문제를 이해하고나니 금방 풀 수 있었다.앞의 두 문제보다는 더 직관적으로 수식을 세울 수 있었다.https://github.com/jeongopo/DaliyCodeCpp/blob/master/code9095.cpp

★★★★☆이전에 접근했던 DP 방식대로 하려고하니까 해결이 안됐다30분정도 고민해보니 재귀함수가 나을것같아서 재귀함수로 풀었는데, 시간초과가 나왔다..배열에 저장하는 방식을 써야할것같아서 그제서야 2차원배열이 생각나서 그방식으로 사용했다.중간 수식에서 오류가있어서 어찌

★★☆☆☆10844번 문제와 비슷한 유형의 DP 문제끝자리수보다 작은 경우의 수를 모두 더하면 되는 문제for 문이 3개나 들어가서 효율성 측에서는 좋지 않을 것 같다..https://github.com/jeongopo/DaliyCodeCpp/commit/44

★★☆☆☆난이도의 경우 앞선 DP 문제들보다 훨씬 쉬웠지만,출력에서 일정한 값으로 나눈 값들을 반환하도록 했던 기존의 문제들과 달리처리 과정이 빠져 있어서 타입을 long long으로 설정해줘야하는 함정 아닌 함정이 있었다.

★★★☆☆이전 DP 문제들과 마찬가지로, 배열의 값에 최댓값들을 집어넣으면서 처리하면 되는 문제위, 아래, 안고르기 의 3가지 경우를 선택하여 한 줄씩 늘려간다는 방식으로 접근했다다른사람들의 코드를 보니, 안고르기의 경우는 어차피 합산되지 않으므로, max값을 구하는

★★☆☆☆앞에 포도주를 몇 번 마셨는지에 따라서 경우의 수가 달라진다.각 선택에 대한 경우의 수를 모두 구한 후, 최댓값을 출력해주면 되는 문제https://github.com/jeongopo/DaliyCodeCpp/commit/ca5d6665edad7a6f8

★★☆☆☆계속 dp를 2차원배열로 쓰다가 다시 1차원배열로 썼더니 어색했다배열 안에 어떤 값을 넣어야할지를 고민하게되었지만,오히려 다른문제보다 더 간단하게 수식과 대입을 진행할 수 있었다.https://github.com/jeongopo/DaliyCodeCpp

★★☆☆☆11053 문제의 변형문제큰 변형은 아니고 배열 안에 넣어주는 값을 증가값으로만 정해주면 되는 문제였다. https://github.com/jeongopo/DaliyCodeCpp/commit/a4e77834823232a52ae3853015f0e42ab

★★★☆☆기본 개념은 어렵지않았는데, 식으로 표현하는 과정이 복잡했다. (내 기준..)증가수열과 감소수열 배열의 값을 따로 배열로 설정하여 저장하는데, 마지막 값을 간단하게 asci+desi 로 표현하기 위해서 des에서 n+i-1로 값을 복잡하게 설정해야 했다. 양방

★★★☆☆DP는 이제좀 쉽다고 생각하고있었는데자신감있게 이 문제를 풀자마자 시간초과가 나왔다..O(N^2)의 시간을 줄이기 위한 알고리즘을 새로 구현하는게 어려웠던 문제기존에 생각했던 방식을 모두 버리고 다시 시작해야했다.https://github.com/je

★★★☆☆엄청 어려운건아니었는데, 2차원배열을 사용해서 하니까, 배열의 안에 어떤 값을 넣어줄지를 고민해줘야했다스스로 난이도를 올려버림..(효율성은 낮아지고...)직관적으로 이해하기에는 좋은 코드이지만 다른 풀이도 참고했다dp를 2차원 배열로 설정하고, 행은 n, 열은

★★☆☆☆접근 방식은 간단하고, 코드 짜는 것도 어렵지 않았다.가장 처음에 n에 가장 가까운 제곱수와 나머지의 합으로 표현했다가 오답 처리가 되었다.(11=dp3+dp2) 알고보니, 12의 경우, 9+1+1+1 의 4항으로 표현하는 것보다4+4+4의 3항으로 표현 가능

★★★☆☆지난 번의 2\*n 타일링 문제를 변형한 문제풀었던 기억을 상기시키면서 코드를 작성했더니뭔가 허무하게? 정답처리가 되었다일단 처음에 감을 못잡아서 6까지는 직접 어느정도 구해보았다.그 결과 홀수는 경우의 수가 없다는 것,2칸, 4칸, 6칸으로 고정된 모양의 결

★★☆☆☆지금까지 DP 문제를 풀때는 보통 n번째의 경우에서 하나 또는 두개를 분리해내서 일반항을 구하는 경우가 일반적이었는데 이문제는 결과들을 쭉 나열해서 규칙성을 찾는 방식이었다..그 일반항에 어떤 규칙이나..이런것들은 딱히 없는것같아서 다소 허무했다이게 맞다고,,

★★☆☆☆멍하니 풀다가 제출해봤는데 정답처리가 됐다..찾아보니 다 나처럼 풀었음for문을 3개나 쓴다고..? 2개만 쓸 수 있을 것 같은데...우선 전형적인 dp문제이므로, 4와 5의 예시를 생각하면서,5의 경우의 수를 구하는 데 4의 경우의 수를 어떻게 활용할 수 있

★★☆☆☆알고리즘을 생각하는 과정은 어렵지 않았는데, 입력을 받는 과정이 어려웠다..C와 같으면서 달라서 뻘짓을 많이했다..(이게 더 심각한거 아닐까)맨처음에 정수로 입력받아서 처리했다가, int로는 5000자리수를 받을 수 없다는걸 제출하고서야 알아서, 그뒤로 cha

★★☆☆☆다른 dp문제와 동일한 방식의 문제.말을 복잡하게 해놓았지만 단순하다.처음에 알고리즘을 짤 때, 어려웠던 부분은 같은 카드팩을 여러개 사는 경우도 있을 수 있다는 거였는데,다시 생각해보니 앞에 했던 자연수의 합? 6=1+1+2+2 이런식으로 표현했던 그 문제와

★☆☆☆☆기존에 알고 있던 정렬 알고리즘을 사용해서 직접 구현했다.n의 범위와 정수들의 범위가 1000보다 작았기 때문에 구현하는 것이 어렵지 않았다.가장 기억에 잘 남아있던 정렬 방법으로 알고리즘을 구현했다.선택 정렬법을 사용해서, index를 저장한 후, 더 작은

★★☆☆☆2750번과 같은 방식으로 풀려고 했는데 시간 초과가 나왔다..알고보니 C++에서는 algorithm 이라는 라이브러리가 있어서, 그 안에서 정렬 함수를 호출할 수 있었다.직접 구현헀던 삽입 정렬의 경우에는 for문을 2개 사용하여 O(n^2)의 시간 집적도가

★★☆☆☆STL 문제인데, sort의 개념을 잘 몰라서 참고하면서 풀었다.sort(arr.begin(),arr.end()) //default 오름차순 sort(arr.begin(),arr.end(),grater()) // int값 내림차순sort(arr.begin(),

★★★☆☆기본 알고리즘은 단순하지만, 코딩이 어려웠다.sort 정렬에 대한 이해가 부족하다는 것을 느꼈다.Location class를 생성하고, 그 안에 age, name 값을 설정한다.compare 정렬 함수에 return true를 사용했다가 invaild comp

★★☆☆☆문자열을 사전순으로 정렬하는 식을 사용할 줄 알아야하는 문제단순하게 비교문을 사용해서 구현할 수 있었다.https://github.com/jeongopo/DaliyCodeCpp/commit/7b04ac730e50d221e1f179e481daafd4dd

★★★☆☆알고리즘 구현은 어렵지 않았지만, 메모리 축소나 시간단축이 어려웠다.메모리의 제한이 8MB 였기 때문에, 10,000,000 개의 입력을 모두 받으면 메모리 초과가 발생=> 입력 값들이 10000 이하의 자연수이므로 배열의 index를 이용해,입력값의 횟수만

★★★☆☆class 만들어서 용량 적게 쓰려고 했다가 시간초과....알고리즘수정했는데 제대로 수정을 못해서 엄청난 오답을 겪었다...숫자 범위를 잘못설정해서 overflow가 발생하기도 했다 8ㅅ8Class에 숫자와 count 값을 넣고, for문을 이용하여 새로운 값

★☆☆☆☆그냥 수 입력받아서 정렬->출력만 해주면 되는 문제간단해서 살짝 당황했다전체시간이 1100ms가 들던데 채점이 엄청 느릿느릿하게 굴러가서 어찌저찌 정답처리는 받았는데..다른 방법이 있나 찾아봤는데 다들 이렇게풀었더라..https://github.com

★★☆☆☆원래는 직접 스택을 구현하라고 하지만.. STL을 사용해서 구현했다.스택을 구현하는 방법에서 class와 배열, vector 등 다양한 방법을 사용하는 것 같다.https://github.com/jeongopo/DaliyCodeCpp/commit/c7

★★★☆☆이전에 알고리즘, 자료구조 수업에서 계산기 과제가 있었는데그때 해결했던 방식과 같은 방법으로 해결했다.출력을 대문자로 하지 않고..테스트 케이스가 바뀔때 스택을 초기화해주지 않는 실수들을 해서 오답처리가 되었었지만기본 알고리즘 자체는 쉽게 구현되었다.stack

★★★★☆개인적 난이도...다풀고나서 다른 코드를 보니 이렇게 쉬울수가없다어떻게든 풀려고 안간힘을 썼다..놀랍게도 정답처리가 되었고 푸는데 1시간도 안걸렸다(1시간이 넘었다면 다른 코드로 정답처리가 되었을텐데..)일단 노력이 가상해서 나의 풀이를 적긴 하지만..이렇게

★★☆☆☆문자열 기초 문제코드 짜는건 어렵지 않았고, 범위가 넘어갈 때의 경우를 처리하는 게 조금 난이도 있었다.13을 더했을 때, Z보다 더 커진다면 -13을 하도록 코드를 짰다.숫자와 문자의 구분은 isalpha 함수를 사용했고,대문자와 소문자의 경우를 간단하게 i

★★☆☆☆C와는 다른 문자열 처리 함수들을 익히느라 조금 시간이 걸렸다.문자열에서 정수로 수를 변환하는 과정에서, atoi를 사용했다가 overflow가 발생했다.(out of range error가 났다)string으로 네 수를 입력받은 후,append 함수로 두 수

★★☆☆☆기본 정렬을 사용해서 문자열을 사전식으로 배열하는 문제string tem으로 임시 문자열을 만들고,그 문자열에 append를 통해 i번째부터 len-i개만큼의 문자열을 복사한다.tem을 vector에 넣고, sort 정렬을 통해 오름차순 정렬해주면 된다.

★★★☆☆그냥 약수들을 계속 나누어서 구하면 간단하게 풀 수 있는데,숫자가 커지는 경우와 효율성을 고려하여 유클리드 호제법을 사용하려고 하니까 어려웠다.유클리드 호제법에 따르면,a와 b의 gcd(최대공약수)는 b와 a%b 사이의 최대공약수와 같다.(증명을 열심히 봤지만

(문제 원래 이름은 그냥 최대공약수인데 다른 최대공약수 문제를 풀었어서 헷갈릴까봐 다르게 표기함)★★★☆☆직접 최대공약수를 구하려고하니까 overflow가 발생해서,일정 수준 이상으로는 정답이 안나왔다...알고보니 규칙을 잘못 파악했던 문제간단하게 두 숫자의 최대공약수

★★☆☆☆문제가 무슨 말인지를 이해하는 데에 조금 걸렸지만, 이해하니까 쉬운 문제였다. O(n^3)라서 시간 초과 걸릴까봐 걱정했는데 그러진않았다 그냥 두 개의 숫자의 gcd를 계속해서 더해주면 되는 문제 유클리드 호제법을 그대로 사용했다.

★★☆☆☆진법 변환하는 원리만 이해해서 적용하면 되는 문제vector로 구현했더니 xmemory 문제가 또 발생해서...코드를 입력하고 에러가 없으면 바로 제출을 해버리는 식으로 풀었다 ㅠㅠb진법의 경우, n을 b로 나눈 나머지 값이 뒷자리부터 채워진다.그렇기때문에 나

★☆☆☆☆지난번에 했던 진법 변환 2의 역연산 과정문자열의 뒤에서부터 접근하면서 알파벳일 때와 문자열일 때로 구분(10이상, 10이하로 구분)해서long long 타입의 결괏값에 공비 r과 곱해서 계산해주었다.중간에 타입 변환 문제인지 값이 잘못나왔었는데, (int)값

★★☆☆☆기본 알고리즘 자체는 진수법 계산을 활용하면 돼서 꽤 간단했다마지막에 100%에서 틀려서 해결하느라 조금 시간이 걸렸다..앞선 진법 변환 문제에서 stack을 사용하는 것이 효율적으로 보여, stack으로 사용했다.8진수는 2진수를 3자리씩 끊어서 그 값을 계

★★☆☆☆오랜만에 문제를 풀어서 그런지..허술하게 풀어서 여러번 도전했다알고리즘 자체는 어렵지 않았다.https://www.acmicpc.net/problem/1212그림을 넣기도 민망한 수준이긴한데, 입력은 string으로 받고(333,334크기까지 받아야하

★★★☆☆기본 식을 도출하는 데에 시간이 오래 걸렸다.코드를 작성하는 것은 2진수 법에 근거해서 짜다보니 오래걸리지 않았다.2진수의 경우, 10진수 값을 2로 계속 나누고, 그 나머지 값을 역순으로 출력하면 되었다.\-2진수의 경우, 2진수와 동일한 방식으로 진행할 때

★★☆☆☆기존에 알고 있는 소수의 정의에 따라 코드를 짜면 되는 문제소수는 1과 자기 자신으로밖에 나누어지지 않는 숫자이므로 나눈다고 생각하기 쉽지만,나누어서 접근할 경우 매 숫자마다 계속해서 나누어주어야 하므로 비효율적이다.따라서, 역으로 2부터 배수에 해당하는 숫자

★★☆☆☆a->b진법으로 옮기는 문제직접 옮긴다고 생각하지 않고, a->10->b 순서로 옮긴다는 생각이 들면 푸는 데에 오래걸리지 않는다.친절하게 a진법의 자릿수를 주기때문에 굳이 메모리를 더 차지하지 않고, 입력받으면서 바로 10진수로 변환해주었다.변환한 값이 0이

★★☆☆☆알고리즘 자체는 어렵지 않았다.지난번에 풀었던 소수구하기 문제를 기반으로 에라토스테네스의 체를 통해 소수를 구한다.이번에는 bool 배열로 구현해주었다.구한 소수들을 기반으로 소수의 합을 구하는 코드를 짠다. 여러 숫자의 합이면 애를 먹을뻔 했지만, 두개의 숫

★★☆☆☆굳이 소수의 개념까지 가지 않고도 풀 수 있는 문제기존에는 소수를 모두 구한후에 다음 소수를 찾아서 나누는 과정을 거쳤는데,굳이 그럴필요 없이 계속 숫자를 증가시키기만해도 되는 것을 발견했다.낮은 숫자부터 접근하므로, 6으로 나누게 될 일은 없는 것이다.그런데

★★★☆☆알고나면 간단하지만 풀때는 생각안나는 문제..직접 팩토리얼을 구해보니 20! 이상으로는 overflow가 발생했다.그렇다면 숫자를 분해해보아야한다는 생각이 들었다.단순하게 10,2,5의 경우만 생각했는데 5의 제곱수에 해당하는 숫자들이 영향을 끼친다는 것을 알

★★☆☆☆직전에 풀었던 팩토리얼 0의 개수를 활용하면 어렵지 않다.맨처음에는 우선..25C12를 직접 구해보았다...ㅋㅋㅋ조합의 기본식을 적어보았더니, 조합이 결국 팩토리얼들의 연산으로 이루어진다는 것을 알았다.팩토리얼 0의 개수 문제의 알고리즘을 활용하기로 했다.분모

★★☆☆☆연결요소가 무엇인지 몰라서 개념을 공부해야했지만,그래프에서는 dfs와 bfs를 사용하면 된다고 생각하니 구현은 금방 되었다.연결 요소(Connected Component) 는 그래프 내에서의 묶음? 과 같은 개념이다.모든 그래프가 이어져있는것만은 아니기때문에

★★★★☆DFS와 BFS가 뭔지도 잘 모르는 상태에서 시작했더니 체감 난이도가 높았다..(열혈 자료구조 책 참고. 내가 이해한대로 정리하기)1\. DFS 1) 깊이우선탐색. 한 길로 깊게 파고들어간다. 2) 어떠한 우선순위에 따라(이 문제에서는 숫자가 더 작은 정점)

★★★★☆알고리즘을 짜는건 어렵지않았지만 메모리 초과를 처리하는게 어려웠다..이분그래프는 그래프들의 정점의 집합을 서로 인접하지 않게 분할할 수 있는 그래프이다.무슨 뜻이냐면, 2개의 색으로 그래프를 색칠할 때, 모든 정점들이 인접하는 정점과 다른 색을 가지고 칠해지는

https://www.acmicpc.net/problem/10451★★☆☆☆기존 dfs 개념을 활용하면 어렵지 않은 문제순열은 각 정점이 하나의 정점만을 가리키게 되고,예시 1의 경우 다음과 같은 순열을 얻게 되는데, 가리키는 정점을 계속 따라가다가, 이미 방

https://www.acmicpc.net/problem/2331★★☆☆☆그래프와 연관된 문제인 것은 알아서 dfs로 풀까 싶었는데, visited 배열의 메모리를 다 잡고가는것이 효율적인것인지 의문이 들었다..그래서 vector를 만들어서 있는 값이 나오면

https://www.acmicpc.net/problem/9466한 학생이 가리킨 다음 학생을 따라 진행해야 하므로 DFS가 적절하다팀에 속한 학생들을 찾고, 전체 인원수에서 제외해준다한 학생은 한 명만을 가리킬 수 있으므로, 일반 int 배열을 사용해준다기존

https://www.acmicpc.net/problem/2667★★★☆☆한 집마다 인접한 집을 모두 체크해야 하므로 BFS가 적절하다bfs 내부에서, 상하좌우의 집과의 연결성을 확인해주어야 한다deque에는 집의 좌표값을 pair로 입력한다배열의 인덱스 값을

https://www.acmicpc.net/problem/4963단지번호 붙이기와 마찬가지로, BFS 탐색을 사용한다. (DFS 사용해도 무관)★ 높이가 h, 너비가 m이지만 배열의 최댓값은 i가 h, j가 m 이다.(이것때문에 한참 더 걸렸다..)BFS의 경

https://www.acmicpc.net/problem/7576주변에!! 있는 토마토가 함께 익게 되므로 BFS가 적합하다고 생각했다.BFS의 내부에 상하좌우에 접근하는 코드를 작성한다. (배열값에 넣어도 됨)BFS를 탐색하면서, 해당 토마토를 익게 만든 토

https://www.acmicpc.net/problem/2178최단 경로를 찾아야하므로, BFS를 사용해야 한다. (DFS의 경우, 처음 찾게된 경로로만 탐색하게 되므로 최단경로라는 보장이 없다.)입력을 붙여서 받기 때문에 char 배열에 문자 하나씩 입력받

https://www.acmicpc.net/problem/2146다리를 만들기 위해서는, 다리의 시작점(대륙)과 다리의 끝점(대륙)을 알아야 한다.=> 대륙을 구분하기 위한 그래프 탐색 1회를 진행한다 (연결요소 문제 참고) DFS를 사용했다.하나의 대륙을 정

https://www.acmicpc.net/problem/1991이진 트리이므로, 각 노드는 0~2개의 하위 노드를 갖는다.=> 가로가 2인 배열을 만들 수 있다.시작은 'A'에서부터만 시작한다.노드는 A부터 대문자 순서대로 받지만, 입력은 순서대로 받지 않는

https://www.acmicpc.net/problem/11725부모부터 말단 노드까지 하나의 경로로 끝까지 진행해야 하므로 DFS가 적절하다벡터 배열을 만들어서 각 노드와 연결된 노드의 개수를 찾는다.상단부터 하단까지 진행하면서, parent 배열에 부모

https://www.acmicpc.net/problem/1167트리의 하나의 노드로부터 다른 노드까지 탐색을 통해 접근하고, 공통의 max거리를 업데이트 하면서 진행한다.최단, 최장 길이에 대한 것이므로 BFS로 먼저 접근했다. (큰 차이가 없는 것 같아 D

https://www.acmicpc.net/problem/1654랜선의 길이는 반드시 1~(랜선 중 최대 길이) 의 값을 갖는다랜선의 길이는 2^31-1 이므로, unsigned int 를 사용해야 한다모든 길이로 잘라볼 수 있으나 시간초과가 발생한다. =>

https://www.acmicpc.net/problem/2110거리의 범위는 1~(처음집과 끝집의 거리) 이다.빠르게 정답 거리를 찾아내기 위해 이진탐색을 사용한다.첫 집을 고정시켰을 때 대부분의 경우 답을 찾아낼 수 있다.(참고 : https://

https://www.acmicpc.net/problem/11662두 점 사이의 거리를 t에 대한 함수로 구하면 2차함수가 나온다. => 삼분탐색!a와 b까지의 거리를 100이라고 하면, 그때의 1/3지점을 p, 2/3 지점을 q로 내분점을 구한다.p에서의 거

https://www.acmicpc.net/problem/10816당연히 1초의 시간 제한이 있으므로 m개의 카드를 모두 다 확인할 수는 없다.algorithm 헤더에는 upper_bound 라는 유용한 함수가 있다.이분탐색을 활용하여 만들어진 알고리즘이다.u

https://www.acmicpc.net/problem/10815원하는 숫자가 있는지 탐색해야 하므로, 가장 빠른 탐색인 이중탐색을 사용한다이중탐색의 결과가 나오지 않는 경우 0을 반환한다앞선 STL upper_bound 함수를 사용해도 되나, iterato

https://www.acmicpc.net/problem/11728처음에는 단순하게 벡터를 하나만 정의해서 저장한 후 정렬을 해주었다. 이 경우에는 1차원 배열이기 때문에 가능했지만, 2차원 배열이 되거나, 배열의 크기가 기하급수적으로 커진다면 효율성이 굉장히

https://www.acmicpc.net/problem/1780분할 정복에서는 큰 문제를 작게 분할하면서 문제를 해결하는데, 이 문제의 경우 문제에서 이미 분할하는 방법을 정의하고 있다. 이에 따라서 코드를 짜기만 하면 된다.99 에서 33 1\*1 로 점점

https://www.acmicpc.net/problem/11729알고리즘에서 기본으로 많이 배우는 하노이의 탑가장 아래의, n 원판을 옮기기 위해서는 n-1원판이 모두 3 장대가 아닌 다른 장대에 있어야 한다.=> n-1 원판을 최종 원판이 아닌 다른 원판으

https://www.acmicpc.net/problem/1992종이의 개수와 비슷한 방식의 문제. 큰 범위를 보고, 조건에 해당하지 않으면 4개로 분할한다.(cf. 종이의 개수에서는 조건에 해당하지 않으면 9개로 분할했다.)분할할 때 괄호를 추가하고, 분할이

https://www.acmicpc.net/problem/2447재귀를 사용하여 구하라고 했으므로, 분할정복으로 접근한다.N 전체를 표현하기 위해서는 결국 3의 제곱수일때의 패턴들이 반복된다.N을 계속 3으로 나누고 N\*N 에서 가운데를 비우는 과정들을 반복

https://www.acmicpc.net/problem/2448별 찍기 문제는 중앙선을 기준으로 n을 빼고, 더한 값을 이용해서 깔끔하게 구할 수 있다.먼저 전체 삼각형 별을 중앙을 기준으로 찍어준다.이 문제의 경우, 가운데 삼각형 부분의 별을 제거하게 되는

https://www.acmicpc.net/problem/11047무조건 K장의 금액을 만들면, 가장 큰 금액의 동전을 사용하는 것이 최솟값이 된다. 따라서 단순하게 큰 동전부터 계산해주면 된다.

https://www.acmicpc.net/problem/2875n,m,k 의 범위가 매우 작았으므로 그리디 알고리즘으로 접근했다.(그리디 알고리즘 : 현재의 가장 빠른 답을 추려내기)따라서, 우선 k를 고려하지않고 팀을 짠 다음, k를 이후에 빼주는 식으로

https://www.acmicpc.net/problem/10610우선 30의 배수가 갖는 특징을 파악해보았다. 30의 배수이기 때문에 무조건 0을 하나는 가지고 있어야 한다.마지막에 수를 출력하게하는데, 이 문제에서 N은 10^5까지나 되는 개수의 숫자를 가

https://www.acmicpc.net/problem/1783처음에는 직접 함수를 구현하려고 했지만, n과 m의 범위가 엄청나게 큰 것을 보고 다른 방법을 고안하게 되었다.이때, 가로로는 오른쪽밖에 못가지만, 세로는 비교적 자유롭게 움직일 수 있다는 것을

https://www.acmicpc.net/problem/1744우선 오름차순을 해서 큰수끼리 묶어주면 된다.큰양수는 큰양수끼리, 큰음수는 큰음수끼리 곱하는 것이 이득이다. (음수x양수 는 안됨)양수와 음수로 나눠서 접근해본다면=> 양수 : 큰 양수끼리 곱해야

https://www.acmicpc.net/problem/1107이용할 수 있는 버튼의 개수는 10개(0~9)로 한정되어 있다.가장 근사한 값을 버튼으로 누르고, +/-로 이동해야 한다.=> 가장 근사한 값은 무엇일까? => 내가 이동하려는 값과 최종 채널 값

https://www.acmicpc.net/problem/1451직사각형을 나누는 과정에서 무조건 가로를 1~m, 세로를 1~n까지 돌려보아야 한다=> 완전탐색, 브루트포스 brute force 문제이 문제의 경우 2차원 배열을 쓰게되므로 코드를 짜기 굉장히

https://www.acmicpc.net/problem/10819모든 경우를 비교해볼 수 밖에 없으므로 브루트포스(brute force), 완전탐색 문제이다.수학에서 배운 순열을 이용하면 금방 풀 수 있는 문제이다.마침 STL 에 next_permutatio

https://www.acmicpc.net/problem/10971가장 처음으로는 BFS 함수를 이용하여 구현해 보았다..그러나 시간 초과가 발생했다. 아무래도 직접 모든 노드를 돌아다니는 것이 많은 비효율을 가져온 것 같았다.따라서, 굳이 돌아다니지 않고 경

https://www.acmicpc.net/problem/1697X에 있을 때 수빈이는 순간이동을 하거나, +1이동, -1이동 중 하나를 선택하게 된다.각 선택에 따라 경로를 추적해서 진행해나가야 한다.=> 여기서 BFS처럼 이동하고 있음을 알 수 있다.BFS

https://www.acmicpc.net/problem/1963이 비밀번호는 무조건 4자리인데, 4자리 중 어느 자리를 바꿀 것인지에 따라 실행 순서가 달라질 수 있다. 이 경우, 앞선 BFS문제들과 마찬가지로 최소실행을 구해야 하기때문에 BFS가 더 적합하

https://www.acmicpc.net/problem/9019"최소한"의 명령어를 생성한다고 했으므로 최솟값을 구해야 하는데, DFS는 한 길로 쭉 파기 때문에 최솟값, 최댓값을 구하는 문제와는 거리가 멀다.=> 한번에 한 단계씩 진행하면서, 원하는 값이

문제는 길었지만 결국 일반좌석이 있다면 그 옆에는 반드시 컵홀더가 하나 있고, 커플좌석이 있다면 그 사이에는 없다는 것.그리고 컵홀더의 개수만 구해주면 된다.왼쪽에서 오른쪽으로 좌석을 나아가면서 일반 좌석이면 -> 바로 옆자리에 컵홀더가 있으므로 컵홀더 개수를 늘려준

https://www.acmicpc.net/problem/2720결국 다른 거스름돈 문제와 비슷하지만, 차이점은 단위를 쿼터, 다임으로 사용하여 0.25달러, 0.1달러처럼 표기한다는 것이다.이 경우, 다른 문제를 풀듯이 돈을 단위로 나누게되면 값이 더 커져버

https://www.acmicpc.net/problem/1026원래대로라면 간단하게 a 배열과 b 배열을 각각 오름차순, 내림차순 정렬해서 큰수는 큰수끼리, 작은수는 작은수끼리 곱해주면 되는 문제였다그러나, b 배열을 재배열하면 안된다는 조건으로 인해 난이도

https://www.acmicpc.net/problem/1541최솟값을 구해야 하므로, - 값이 커질수록 좋다.즉, -가 나오고 그 뒤에 +가 나왔다면 그 사이를 괄호로 묶어주어야 최솟값이 된다.ex) 55-50+40 -> 55-(50+40) 가 한번이라도

https://www.acmicpc.net/problem/2217로프를 10, 15를 사용하면, 그 때의 가능한 최대 무게는 20이다.=> 가장 작은 값인 10의 2배10,15,20 의 로프가 있다고 할 때, 최소인 10의 로프를 쓴다면, 15,20은 무조건

https://www.acmicpc.net/problem/1789서로다른 n개의 자연수들의 개수가 많아야 하므로, 가장 작은수부터 더해야 갯수가 가장 많다=> 1부터 하나씩 값을 빼준다10의 경우, 1+2+3+4 로 딱 맞아떨어지기때문에 4번째 반복문의 값을

두 배열의 값이 같은지 확인하기 위해, 두 배열을 모두 오름차순 정렬한다.단순하게 0이 아니면 6자리를 모두 돌아다니면서 값이 같은지 확인할 수 있다.=> 더 큰 케이스의 경우를 위해, 반복문 실행을 최대한 줄이려면 내 로또번호가 당첨번호 자리보다 작아지면 그 숫자가

https://www.acmicpc.net/problem/1946처음엔 가장 단순하게 서류 심사 결과와 면접 성적이 같이 나와있으므로, vector안에 pair<int,int> 값을 넣어주었다.그리고, first 값을 배열하고, 이후 second 값을 모

https://www.acmicpc.net/problem/1463처음에는 최솟값을 구해야 하고, 그때의 연산이 3종류이기 때문에 단순하게 BFS를 이용해서 풀었다.구하고나서 보니, 구하는 경로값이 필요한 경우가 아니고, 연산 값들이 연속적이었기 때문에 DP를

https://www.acmicpc.net/problem/1339처음에는 단순하게 가장 자릿수가 높은 곳부터 큰수를 넣어주면 된다고 생각했으나, 반례로 인해 오답이 되었다.결국 브루트포스로 next_permutation 순열 함수를 사용해서 최대 10! 의 계

https://www.acmicpc.net/problem/1003당연히, 기존에 있는 DFS식, 재귀함수식 함수를 그대로 사용하면 시간초과가 난다.n번째 값은 n-1과 n-2의 값을 더해서 이루어지고, 이는 0의 호출과 1의 호출에서도 동일하게 적용된다.=>

https://www.acmicpc.net/problem/1715가장 작은 숫자들을 계속해서 2개씩 더해주면 된다.=> 앞의 두 값을 더해주고, 그 값들을 정렬해서 다시 작은 값 2개를 더해주면 된다!반복문을 사용해서 값이 2개보다 적어질 때까지 계속해서 더해

https://www.acmicpc.net/problem/1149최솟값을 구하기위해 경로를 탐색한다고 생각하여 처음에는 DFS로 접근했다.=> 그러나 시간초과...경로탐색의 경우, n번째의 결과에 1~n-1까지의 모든 경우의수가 영향을 끼치지만, 이 문제는 오

https://www.acmicpc.net/problem/9996\*는 공백을 대신할 수 있기때문에, 앞과 뒤만 맞으면 된다.개인적으로, 테스트케이스가 너무 잘못돼서 풀기 어려웠던 문제였다..ad\*bcd 라는 패턴이 있다면, 시작은 ad로, 끝은 bcd로 끝

https://www.acmicpc.net/problem/1213이래서 커플이 문제야..팰린드롬은 앞으로 읽거나 거꾸로 읽어도 같은 문자열을 뜻한다.즉 모든 문자는 짝수개 있거나, 단 하나만 홀수개로 있어야 한다.나의 경우, 입력을 받을때 문자의 개수를 카운트

https://www.acmicpc.net/problem/1620문제가 정말 길지만,, 단순하게 포켓몬 도감에 숫자를 넣으면 포켓몬 이름을, 포켓몬 이름을 넣으면 숫자를 출력하라는 문제이다 (문제 읽기가 귀찮아서 드랍하는 사람이 있었을것같다)나의 경우, 이름으

https://www.acmicpc.net/problem/2468이 문제도 문제가 꽤 길지만, 결국 물의 높이를 기준으로 연결요소를 구하면 되는 문제이다.대신 물의 높이가 고정이 아니고, 직접 모든 물의 높이를 확인해주어야한다. 배열의 크기와 높이의 범위가 작

https://www.acmicpc.net/problem/3986괄호맞추기 문제처럼 짝을 맞춰야하는 문제에서는 stack이 유리하다. 가장 가까운곳과 짝을짓는게 겹칠 위험이 덜하기때문에, stack에 넣고 그때의 top값과 같다면 짝을지어주면 된다.만약 모든

https://www.acmicpc.net/problem/2910단순하게 sort 함수를 사용해서, 빈도가 더 높은 순서대로 정렬하면 된다. sort의 세번째 인자인 cmp함수에서 빈도와 첫번째 인덱스 값을 비교해주면 된다.처음에 count를 숫자 값을 사용하

https://www.acmicpc.net/problem/4949기존에 풀었던 괄호문제와 동일하게 풀면 된다.이 경우, 입력값에 공백이 포함되어 한줄이아닌 한 단어별로 입력이 받아졌는데, getline(cin,string) 함수를 사용해서 입력을 받아주었다.

https://www.acmicpc.net/problem/15686결국엔 m개의 치킨집을 골랐을 때, 그때 각각의 집으로부터의 치킨집까지의 최소거리를 구하는 문제였다원래는 DFS로 직접 조합을 구현하는 문제였지만 next_permutation에 중독된 나는 그

https://www.acmicpc.net/problem/2589결국 가장 먼 두 지점을 구하는 문제이고, "가장" 긴 거리를 구하는 문제에는 BFS가 가장 적절하다. (한번에 한단계씩 이동하기때문에 가장 길거나, 가장 짧은 거리를 구할 때에는 BFS가 더 적

https://www.acmicpc.net/problem/1439처음엔 어딜 먼저 뒤집어야할지 모르니까 BFS로 경로탐색을 해야 한다고 생각했다그러나 메모리 부족.. 1010 이 반복되는 길이 100의 문자열을 넣어 실행해보니 128MB가 훌쩍 넘었다그래서 B

11659 : 구간 합

https://school.programmers.co.kr/learn/courses/30/lessons/86491?language=cpp기왕이면 큰 값들끼리 비교해서, 가장 큰 값에 다른 큰 값들이 묻히도록,, 하기 위해 큰 값들끼리만 비교해주기로 한다즉, 나

주어진 시간은 1초. n은 3만밖에 안되므로 O(n^2)의 케이스로도 처리는 가능하다.결국 하나의 노드는 반드시 다른 하나의 노드만을 가리키기 때문에 배열로 처리해도 상관없다잘 보면 결국 일정한 크기의 윈도우를 옆으로 이동시켜주면 된다 \-> 슬라이드 윈도우를 쓰자!

https://www.acmicpc.net/problem/20055단순하게 모든 행동을 구현하면 된다컨베이어 벨트로 회전하게 되어있지만, 굳이 다른 자료구조를 쓸 필요 없이 vector를 써도 된다 \-> 대신 이 경우 컨베이어 벨트의 회전에서 erase와

https://www.acmicpc.net/problem/1976여러 번 접근할 수 있는 경로에 대해 갈 수 있는지만 파악하면 되므로, DFS와 BFS 모두 상관없지만 반환값을 통해 갈 수 있는지 여부를 빠르게 반환하기 위해 BFS를 쓰려고 한다시간은 2초,

https://www.acmicpc.net/problem/2961단순히 재료를 넣는지 마는지에 따라 결과의 최솟값을 구하는 문제반복적이므로 재귀를 통해 해결했다\-> 하지만 이 문제는 밑의 비트마스킹 방법을 사용하는것이 더 효율적인 것 같다https: