공부혜옹

의외로 굉장히 쉬웠던 문제였다. 갔던길을 또다시 갈 수 있으나 두 지점을 점프해서 갈 수는 없다 꼭 한칸씩 이동해야한다는 것이다. 제약사항이 없는 상태에서 한칸씩 이동할 수 있는 상황이고, 이때 모든 n개의 노드를 방문하는 가장 최소의 움직임은 n-1일 수 밖에 없다. #include #include using namespace std; int t, n, m; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while(t--){ cin >> n >> m; for(int i=0; i> a >> b; } cout

처음엔 두가지 노드를 동시에 조상을 거슬러 오려니 어떻게 같은 조상을 찾을 수 있는지 조금 막막했다. 옛날에 비슷한 문제를 풀어봤던것같은데..ㅜㅜ 노드와 함께 깊이를 저장해 거슬러올라올까 하다가 굳이 그렇게 복잡하게 생각할 필요 없이 노드1을 루트 조상까지 먼저 쭉 방문하게 하고 나머지 노드2의 조상을 탐색하다가 노드1이 이미 방문한 노드를 공통조상으로 판별하였다. #include #include #include #include #include using namespace std; int t, n; int node1, node2; void func (int tree[],int check[],int num){ if(tree[num] == 0){ if(check[num]==1){ cout > b; //b의 ..

문제이름이 버블소트라 일단 버블소트를 설명하자면 첫번째 인덱스부터 바로 다음 인덱스의 값과 비교하여 현재 기준이 되는 인덱스가 더 클경우 다음 인덱스와 자리를 바꿔주는 정렬이다. 1회 정렬이 끝날때마다 맨 끝순서에 가장 큰 수들이 정렬된다. 버블 정렬은 해당 블로그를 참고했다 https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html [알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 버블소트를 공부한 후 버블 소트를 직접 구현해 swap할 때마다 변수의 숫자를 증가시켜주었는데 아쉽게도 시간초과가 났다. 즉 이..

처음엔 문제 그대로 수열을 재귀적으로 계속 만들다가 수열의 크기가 n 이상이 되면 재귀를 끝내고 해당 수열[n]으로 문자를 찾아주는 코드를 작성했으나 역시나 메모리 초과로 실패하였다. 따라서 수열을 직접 구현하기보단 n자리에 위치한 문자가 m인지 o인지 자체에 집중하며 풀이했다. 수열은 세가지 조건을 합하여 만들어지는데 s(k-1) 부분 / 새로 만들어지는 부분 / s(k-1) 부분 이 새로 만들어지는 부분에 n이 위치한다면 m인지 o인지 바로 알 수 있다. 그 이유는 n에서 s(k-1) 부분 만큼의 길이를 제거하고 난 후 n이 1이면 m 그 외의 숫자이면 o이기 때문이다. 바로 이 새로 만들어지는 부분에 n이 위치할 수 있도록 계속해서 수열을 짧게 줄여주면 된다. 짧게 줄이는 방법은 다음과 같다. 1...

처음엔 정사각형이 되지 않을 조건을 먼저 생각해 보았는데 정사각형 특성상 정사각형일때만 해당되는 조건이 훨씬 명확하고 적은것같아 방향을 바꾸었다. 정사각형이 될 조건은 1. 모든 변의 길이가 같다 2. 대각선의 길이가 서로 같다 주어지는 네개의 점을 이용해 거리를 계산하면 6개의 길이가 나온다 이때 점을 미리 사각형의 형태로 나열한 후 거리를 구하는것 보다 일단 6개의 길이를 다 구한후 sort하면 나머지 두개의 길이가 대각선의 길이임을 알 수 있다. (정사각형은 변의 길이보다 대각선의 길이가 항상 길기 때문) #include #include #include #include using namespace std; int t; int x1, x2, yy1, y2; int func(int x1, int yy1..

어린왕자가 진입/이탈해야하는 경우는 출발점과 도착점 사이에 꼭 통과해야하는 원이 존재하는 경우 이다. 이때, 출발점과 도착점이 같은 원에 있다면? 그원안에 행성이 얼마나 많은지와 상관없이 ( 피해서 갈 수 있으니 ) 진입/이탈해야할 경우가 없다. 따라서 출발점과 도착점사이에 곡 통과해야하는 원이 있는지를 판별하기 위해 두 점과 원의 중심간의 거리를 비교한다. 거리가 원의 반지름보다 크다면 해당 점이 원의 외부에 위치하는 것으로 꼭 원을 통과해야한다. #include #include using namespace std; int t, n; int x1, x2, y1, y2; int x, y, r; int total; int cnt; int main(){ cin >> t; for(int i = 0; i< t;..

어떻게 하면 효율적으로 풀 수 있을까 치킨집 주위로 가까운집이 몇갠지 세서 통계내야하나 별 생각을 다하다가 결국 dfs를 이용해 완전탐색하기로 했다. 치킨집 조합을 모두 구해서 각 조합별 도시의 최소치킨거리를 구해 가장 작은 치킨거리를 보유한 조합을 선택한다. #include #include #include #include using namespace std; int n,m ; int arr[51][51]; bool check[14]; int ans = 987654321; vector chicken; vector home; int calc(pair a, pair b){ return abs(a.first-b.first) + abs(a.second-b.second); } void DFS(int idx, in..

보자마자 가장 큰 자릿수에 있는 알파벳부터 차례대로 숫자를 부여해 계산하면 되겠다라고 간단히 생각해서 코딩하다가 그렇다면 다른자릿수에 있는 같은 알파벳 ex) abcd + gaf 에서 a의 경우는 어떻게 처리해야할지 막막해졌다.. 따로 저장해서 일일히 표기를 해둘까하다가 내가 생각한 접근방법이 처음 부터 틀렸다는 생각이 들었고 다시 로직을 짜기 시작했다. 우선 가장 큰자릿수에 가장큰 수 9를 적용해야 수의 합이 최대가 된다는것은 명확한 사실이다. 문제는 가장 큰자릿수의 알파벳이 무엇인지 판별하는것. 처음에 보이는 자릿수에 따라서 무턱대고 숫자를 부여했다면 이번엔 글자 자체에 자릿수를 한번 부여해보는식으로 접근했다. 위 이미지에서 c의 경우 1000자리와 10자리 두군데에 분포해있기 때문에 c라는 알파벳 ..