본문 바로가기
반응형

알고리즘

5213. 진수의 홀수 약수 5213. 진수의 홀수 약수 숫자의 범위가 커서 시간제한이 문제일 것 같았다. 따라서 testcase 를 받기전에 get_f 함수를 통해서 각각의 f[x] 값들을 미리 구해주었다. 그리고 조금 더 시간을 단축하기 위해서 sum 이라는 배열을 통해서 sum[x] 는 1~X 까지 f[X] 의 합을 구했다. 따라서 정답을 구할 때는 sum[R]-sum[L-1] 을 통해서 구할 수 있었다. get_f 에서 최대 루트 1000000 까지 돌고, main 함수에서 1000000 번 돌기 때문에 1억번으로 시간제한을 통과할 것이라고 생각하고 코드를 구현하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#incl.. 더보기
1248. 공통 조상 1248. 공통 조상 공통 조상 같은 경우에는 LCA라고 하여, 해당하는 노드의 높이를 맞춰준 후에 같이 부모 노드로 거슬러 올라가면서 같은 노 드가 될 때까지 while 문을 이용하여 구할 수 있습니다. 또한 문제에서 해당하는 조상 노드의 서브 트리의 크기를 구하라고 하였는데, 이는 분할정복을 이용하여 get_size() 함수에 서 자식 노드의 존재 여부를 파악하면서 재귀함수로 구현하였다. 처음에 get_size 에서 ret 값을 0으로 초기화 했었는데, 생각 해보니 그렇게 하면 노드가 자기 자신도 서브 트리의 크기에 포함을 해야하므로 ret 의 초기값을 1로 수정하였다. 1234567891011121314151617181920212223242526272829303132333435363738394041.. 더보기
1938번 1938번 - 통나무 옮기기 단순한 BFS로 풀려고 했는데, 생각해줘야 할 예외 사항이 많아서 경우의 수를 나누었다. 일단 처음에 입력받는 부분에서 통나무 B위치(bx,by,bd) 와 마지막 놓을 E의 위치를 (ex,ey,ed) 를 구해주었다. 이때 bx,by 는 통나무 중심의 좌표이고, bd 는 통나무가 놓인 방향을 나타냈다. bd 가 0 이면 세로, 1이면 가로 방향. 통나무 중심의 위치는 통나무가 가로이건 세로이건, for 문 두번을 돌때 2번째가 통나무가 중심인 것으로 찾았다. 또 중심값을 통해 통나무의 방향도 알아낼 수 있었다. 그리고 BFS를 수행하는 함수를 보면, 구조체를 만들어서 통나무의 좌표와 방향을 갖는 구조체를 큐의 인자로 넣는다. chek 배열 같은 경우는 3차원 배열을 설정하여 c.. 더보기
2665번 2665번 - 미로만들기 오랜만에 문제를 풀어보니까 머리가 굳은 거 같다. 문제를 처음에 너무 어렵게 생각해서 '벽부시고 이동하기' 와 같이 차원을 늘린 bfs를 사용하려고 고민했었다. 하지만 그냥 단순한 BFS에 조건만 추가해서 문제를 풀 수 있었다. 기본적으로 모든 map 의 값을 INF 로 지정된 큰 수를 저장한다. 그리고 BFS에서 4가지 방향을 보면서 조건문으로 나보다 적은 횟수로 이동가 능한 점을 큐에 넣는다. 즉 0,0 에서는 벽을 길로 바꿀 필요없이 이동가능하므로 dist 값을 0 으로 갖는다. 하지만 만약 0,1 이 벽이라면 0,1 까 지 가는 방법은 벽을 1번 바꾼값이 된다. 따라서 0,0 까지 가는 벽을 바꾸는 방법의 수 + 1이 된다. 이런식으로 나보다 작은 값으로 바꾸면서 이동하면.. 더보기
FrogRiverOne 동적 할당을 통해서 check 배열을 만들어줬다. 그리고 for문을 통해서 A 배열을 0부터 확인하기 시작한다. 만약 A[i] 의 값이 X 보다 작고, A[i] 가 처음 나왔으면 cnt ( X 이하의 수가 나온 갯수 ) 를 늘려준다. 그러면서 cnt 가 X 의 값과 같아지는 순간에 i 값을 리턴한다. 하지만 A 배열을 다 돌아도 값이 나오지 않으면 -1 을 리턴한다. 더보기
15649번 15649번 - N 과 M (1) 개인적으로 이런 간단한 기본 문제가 있으면 좋겠다고 생각했는데 문제가 생겼다. 문제를 풀다보면 응용해서 써야하는 자주 접하는 기본 문제인 것 같다. 그래서 재귀를 이용해서 풀었고 , 비트연산을 이용해보기도 하였다. 12345678910111213141516171819202122232425262728293031323334353637#include int n, m;int num[9];bool used[9];void go(int cnt){ if (cnt == m) { for (int i = 0; i 더보기
5170. 상원이의 직선 긋기 게임 5170. 상원이의 직선 긋기 게임 D5 치고는 굉장히 쉬운 문제였다. 일단 주어진 점의 갯수가 200개 이므로, 나올 수 있는 직선의 갯수는 200C2 로 19900 개가 된다. 따라서 모든 경우의 수를 탐색한다고 하더라도 시간 초과가 나올 수 없는 문제라서 완전탐색을 이용해서 문제를 풀었다. 2중 for문을 통해서 전체의 직선을 모두 구하고, get_incline 함수를 이용해서 직선의 기울기를 중복 생각없이 모두 vector 에 담았다. 그리고 sort 를 이용해서 vector 를 정렬하고, 중복되는 수를 빼가면서 수를 세줬다. 이때 tmp 값을 초기에 10000으로 설정한 이유는, x,y 좌표의 범위가 -1000 에서 1000 사이 이므로 기울기가 가장 클 때는 1000 이다. 따라서 1000보다.. 더보기
4676. 늘어지는 소리 만들기 4676. 늘어지는 소리 만들기 문자열을 이용한 간단한 문제였다. 하이픈이 들어가는 위치를 배열에 모두 저장해서 합산한다. ( 길이가 20까지 이므로 하이픈이 들어갈 수 있는 위치는 0~20이다) 그리고 다시 for문을 돌면서 해당하는 위치에 그 숫자만큼 입력해서 정답을 구한다. 123456789101112131415161718192021222324252627282930313233343536373839#include#includeusing namespace std; int main(){ int tc; cin >> tc; for (int t = 1; t > s; cin >> h_num; for (int i = 0; i > pos; total[pos]++; } for (int i = 0; i 더보기
반응형

티스토리툴바