본문 바로가기

Coding

 (195)
string을 int로, int를 string으로 string to int -> stoi 함수 ex) int num = stoi(str); int to string -> to_string 함수 ex) string str = to_string(num);
1991번 트리 순회 노드를 다 잊어버려서 생각보다 오래 걸린 문제 조만간 Linked list 정리하면서 공부할 생각이다. 전위 순회 : 루트 노드 방문하고 왼쪽 자식이 있으면 왼쪽으로 쭉 방문하고 그 후 오른쪽 자식 방문(만약 왼쪽 자식이 있어서 그쪽으로 내려가 면 그 때의 왼쪽 자식을 루트로 생각) 중위 순회 : 왼쪽 자식이 있으면 왼쪽으로 쭉 방문하고 루트방문하고 그 후 오른쪽 자식이 있으면 오른쪽으로 방문한다. 후위 순회 : 왼쪽 자식이 있으면 왼쪽으로 쭉 방문하고 오른쪽 노드가 있으면 오른쪽 노드 방문 하고 더 이상 존재하지 않으면 그때 루트 노드를 방문하며 올라온다(올라온다는 것은 들어간 depth만큼 다시 올라오는 것)
1525번 퍼즐 처음에는 배열로 bfs돌리면서 그때마다 string으로 합쳐서 비교를 하려고 했다. 근데 생각해보니 굳이 배열로 유지해줄 필요가 없이 처음부터 문자열 상태로 쭉 계산해주면 될 것 같아서 string으로 하기로 했다. 참조 사이트 : https://where-i-go.tistory.com/m/100?category=815964
2698번 인접한 비트의 개수 끝나는 지점에 어떤 수가 오는지 계산하면 된다. 예를 들어 val[n][k][0]이라는 것은 n개의 숫자의 인접한 비트의 개수가 k개이며 마지막에 0으로 끝난다는 뜻이다. 그렇다면 val[n][k][0]의 값은 val[n-1][k][0]과 val[n-1][k][0]을 더해서 나타낼 수 있고 val[n][k][1]의 값은 val[n-1][k][0]과 val[n-1][k-1][1]의 합으로 나타낼 수 있다. (val[n-1][k-1][1] -> 마지막에 1과 1이 만나서 +1이 되므로) 이 식을 이용해 풀면 된다.
3055번 탈출 5427번 불 문제와 같은 문제이다. 처음에 고슴도치와 비버 굴을 반대로 봐서 엄청 헤맸다. 분명 예제 3,4번은 불가능한데 왜 가능한 횟수가 나오지? 라고 계속 고민하다가 문제를 다시 읽어보고 둘이 바뀐 것을 깨달았다... #include #include #define visited true #define Non_visited false #define MAX 51 using namespace std; typedef pair pr; char map[MAX][MAX]; int cnt[MAX][MAX]; bool Check[MAX][MAX]; int xx[4]={1,0,-1,0}; int yy[4]={0,1,0,-1}; queue water; queue hedgehog; void bfs(int M, int ..
11778번 피보나치 수와 최대공약수 처음에는 입력받은 두 값의 피보나치 수를 구하고 최대공약수를 구했는데 계속 틀렸다고 나왔다. -> (N%mod, M%mod)의 최대공약수와 (N,M의 최대공약수)%mod가 다르기 때문이라고 한다. 찾아보니 다들 피보나치 성질 중 G{fibo(N),fibo(M)} = fibo{G(N,M)} 이 성질을 이용해서 먼저 최대공약수를 구하고 피보나치 수를 구했다.
13976번 타일 채우기 2 정말 오래 걸렸다. 다른 타일 채우기 문제처럼 단순히 점화식 찾아서 그대로 dp로 풀면 될 줄 알았는데 안된다. 그게 바로 두달 전. 11444번 문제 풀면서 찾아봤던 행렬 계산을 통해 풀었다. F(n) = 3*F(n-2) + 2{F(n-4) + F(n-6) + F(n-8) +........+ F(0)} -> 이 식에서 n 대신 n-2를 대입 F(n-2) = 3*F(n-4) + 2{F(n-6) + F(n-8) + F(n-10) +........+ F(0)} -> 두 식을 빼면 F(n)-F(n-2) = 3*F(n-2) - F(n-4) -> F(n) = 4*F(n-2) - F(n-4)라는 식을 구할 수 있다. 이 식을 2차 행렬로 나타내서 풀면 된다. c[i][j] = (c[i][j]+mod)%mod -> ..
11444번 피보나치 수 6 Fn = Fn+1 + Fn-2 그동안 했던 방식대로 top-down 또는 bottom-up으로 하면 안된다. 행렬을 이용해서 풀어야하는데 이해하기 더럽게 힘들다(바보라서 그런듯). 아무튼 피보나치 수를 행렬로 나타내면 이런 식이 나온다. 이 식을 정리하면 다음과 같다. 어떻게 이 식이 나오는 걸까? (참조 : https://blog.naver.com/skkong89/221490403921) 이 다음은 n을 짝수와 홀수로 나누어 계산해주면 된다 (분할 정렬 알고리즘에 따라 나누어질 수 없을때까지 나눈 후 계산하고 합치고 반복)

티스토리툴바