내가 그린 코딩 그림

이 문제는 이진트리가 주어지고 targetSum에 맞는 경로를 찾는 문제입니다. 경로를 구하는 문제의 경우 BFS, DFS 등을 이용하지만 최단거리를 구하는게 아닌 경우 DFS를 보통 활용하기 때문에 트리, 경로 라는 힌트로 DFS를 써야겠구나 정도는 먼저 떠올릴 수 있습니다. 사실 저는 한번에 풀지 못했고 풀이를 보면서도 많이 헷갈렸습니다. DFS 숙달이 아직 안되었다는 얘기인데 여러 풀이를 보면서 가장 괜찮은 방법이라고 할 만한 것을 찾았습니다. 포인트는 크게 다음과 같습니다. 1. 경로를 담기위한 path 벡터, 답변을 담기위한 2차원 벡터 v 2. path에 담아주고 targetSum 연산 3. 리프노드 인지 검증합니다. 4. 리프노드가 아닐경우 처리 // https://leetcode.com/p..

간단해 보이지만 막상 순서를 잘 조립하려면 N-1로 돌려야할지 N으로 돌려야할지 바로 안떠오를 수 있는 문제고 실제로 비슷한 난이도의 문제보다 오려걸렸고 서브태스크에 걸려 계속 틀린 문제. 이런 문제는 애초에 한 번 익숙해져 놔야 더 안틀릴 듯 하다. 이게 문제의 서브태스크인데 사실 문제 자체의 입력조건을 잘 신경써야 한다 개인적으로 이 문제의 핵심은 다음과 같다. 1. minCost가 등장 했을 때 대처로직 2. 최소값, 최대값에 유의한 개념 주유소 자체가 많이 주어져 시간 초과가 나는 문제인가? 생각을 하면서 괜한 시간에 신경을 썼는데 이는 for문으로 돌더라도 한 번만 돌기 때문에 O(n)의 시간복잡도를 가지기 때문에 시간초과가 날 일 자체가 없다. 제출했다가 틀린 답(이걸로 제출하면 17점을 받게..

#include using namespace std; vector a[54]; int n; int parentNode; // 부모 노드 int root; // 루트 위치 int target; int answer; int dfs(int here){ int result = 0; bool childCheck = false; // 이 for문을 돈다는 것은 자식이 있다는 것 for(int there : a[here]){ if(target == there) continue; result += dfs(there); childCheck = true; } if(childCheck==false) return 1; return result; } int main(){ cin >> n; for(int i=0; i> paren..

문제와 제한 사항은 위와 같습니다. 처음으로 참여했던 알고리즘 스터디에서 나온 문제인데, 플로이드 와샬 알고리즘을 활용해서 풀 수 있습니다. 해당 알고리즘은 각 정점의 노드 간 최단 거리는 구하는 알고리즘입니다. 해당 알고리즘에 대해서 이해하려고 할 때 추천하는 영상입니다. 만약 이 영상을 보고 풀 수 있다면 풀어보고, 코드를 보려는 분들은 맨 아래에 정답 코드를 활용하시면 됩니다. 문제 정답 /** * 순위 문제 * 권투선수들의 순위를 구할 수 있는 선수의 수를 리턴(선수 100명 이하, 경기결과 4500개 이하) */ #include using namespace std; bool a[101][101]; // 승리 여부 표시 int solution(int n, vector results){ int an..

[알고리즘] 백준 1629 곱셈 문제 힌트 1. 모듈러(%) 연산의 기본 성질 a를 b번 곱하는 것을 c로 나눴을 때 나머지를 식으로 표현하면 다음과 같다. a(b번제곱)%c = x; b를 2라고 하면 다음과 같다 (a*a)%c = x; 이는 다음과 같이 표현해도 같다 a%c * a%c = x; 즉, 2제곱을 이런식으로 나눠 표현할 수 있다는 것에서 힌트를 얻을 수 있다. 2. 재귀 함수로 표현 이를 재귀함수로 표현해서 식을 작성해보자. 문제 정답 #include using namespace std; typedef long long ll; ll a,b,c; ll result; ll make_result(ll a, ll b){ // 기저사례 if(b == 1) return a%c; // 그냥 10 1이 들..

문자열을 지정받아 아스키 코드를 활용하면 된다. char a = s[i]; 형식으로 지정하는 경우 아스키코드값을 넘어가게 되면 문자열이 깨지기 때문에 int로 정의해 마지막에 char로 바꿔주는 첫번째와 같은 방법은 정답이 될 수 있지만 두 번째의 경우 정답이 될 수 없다. 정답이 되는 경우 #include using namespace std; // A = 65 , Z = 90, a = 97 , z = 122 string s; // 주어지는 문자열 string rot13; int bigA = 'A', bigZ = 'Z', smallA = 'a', smallZ = 'z'; int main() { getline(cin, s); for(int i=0; i= bigA && a bigZ) { a -= 26; } ..