CS/Algorithm 문제
[BaekJoon] 백준 15649번 N과 M(1)
[BaekJoon] 백준 15649번 N과 M(1) 문제: www.acmicpc.net/problem/15649 내코드 백트래킹 문제: 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 백트래킹 문제를 처음 풀어보는 것이기도 했고, 구현 과정이 상당히 어려웠다. 리스트에 값을 하나씩 넣어주면서 풀어주는 문제 만약 1-4의 수가 있고, 2자리 수열을 만들어줘야 한다고 가정해보자. [1, x] -> [1, 2] -> [1, 3] -> [1, 4] -> [2, x] -> [2, 1] -> [2, 3] -> [2, 4] 이런식으로 리스트에 수가 들어갈것 수가 사용될때마다 visited에서 해당 값은 True로 처리 n, m = map(int, input().sp..
[BaekJoon] 11729번 하노이 탑 이동 순서
[BaekJoon] 11729번 하노이 탑 이동 순서 문제: www.acmicpc.net/problem/11729 내코드 A,B,C 기둥이 있고, n개의 원판이 있다고 생각하자 A기둥에 n개의 원판이 있을 때 C 기둥으로 옮기려면 n-1개를 B기둥으로 옮기고 나머지 가장 큰 한개를 C로 옮기고 B기둥에 있는 n-1개를 C로 옮기면 된다 이렇게 생각하면 재귀가 적용이 된다. 위의 3과정을 그대로 코드로 옮겨주면 된다. n-1개의 원판을 옮기는 방법, n-2개... 이렇게 반복되는 것 주의) 원판이 한개인 경우는 한번만 옮기면 되므로 따로 처리해준다. def hanoi(n, a, b, c): # 원판이 한개인 경우는 한번만 옮기면 되므로 따로 처리 if n == 1: print(a, c) # a기둥에 n개의..
[BaekJoon] 백준 1629번 곱셈
[BaekJoon] 백준 1629번 곱셈 문제: www.acmicpc.net/problem/1629 내코드 이 문제는 일단 brute force 방식으로 접근하면 O(n) 시간 복잡도로 풀수 있지만 이 경우에 시간 초과가 남 분할 정복 방식으로 풀어야하는 문제: 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 간단하게 생각하면 a^b mod c를 풀어야 하는 문제 여기서 b=2k+1 일때 a^b = (a^k)^2xa이고 b=2k일때 a^b = (a^k)^2임을 생각해보자 예를 들어 2의 16제곱이면 brute force 방식은 16번 계산해줘야하지만 분할 정복을 하면 2의 8제곱한 결과를 제곱해주면 된다. 즉, 2의 8제곱은 2의 4제곱의 제곱이고, 2의 4제곱은 2의 제곱의 제..
[BaekJoon] 백준 13549번 숨바꼭질 3
[BaekJoon] 백준 13549번 숨바꼭질 3 문제: https://www.acmicpc.net/problem/13549 내코드 - 기존의 bfs랑 약간 다른 문제 - 그렇게 쉽지도 어렵지도 않은 문제 - 전에 풀었던 [BaekJoon] 백준 1697번 숨바꼭질 문제와 내용은 비슷하지만 priority queue를 이용해서 순간이동 하는 경우를 따로 처리해줘야하는 점이 달랐다. - 순간이동하는 경우 시간이 소요되지 않기 때문에 고려해서 priority queue를 사용해주면 된다. #include #include #include #define MAXNUM 100001 using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(..
[BaekJoon] 백준 6593번 상범 빌딩
[BaekJoon] 백준 6593번 상범 빌딩 문제: https://www.acmicpc.net/problem/6593 내코드 - 간단한 bfs 문제 - 다른 점은 3차원 배열을 이용한다는 것. - x, y, z 위치만 헷갈리지 말고 맞춰주자. #include #include #include #define MAXNUM 30 using namespace std; int dx[] = { 0, 0, 1, -1, 0, 0 }; int dy[] = { 1, -1, 0, 0, 0, 0 }; int dz[] = { 0, 0, 0, 0, 1, -1 }; int main(void) { ios::sync_with_stdio(false); cin.tie(0); int l, r, c; cin >> l >> r >> c; ch..
[BaekJoon] 백준 5014 스타트링크
[BaekJoon] 백준 5014번 스타트링크 문제: https://www.acmicpc.net/problem/5014 내코드 - 간단한 bfs문제: queue이용, 너비 우선 - 알고리즘 1. 처음 있는 위치를 큐에 넣는다. 2. 큐에서 pop을 해서 pop한 위치를 기준으로 u를 더해준 값과 d를 빼준 값을 얻는다. 2-1. 여기서 만약 가고 싶은 층과 일치하면 출력후 return 3. u를 더해준 값이 최대 층보다 커지거나 d를 빼준 값이 1보다 작아지면 안되므로 아닌 경우에만 push를 해준다. (이때 visited == false인 것도 확인. 처음 방문할때가 최소값이므로 false일때만 push해준다.) 4. 2-3을 큐가 빌때까지 반복한다. 5. 큐가 비어서 나온경우 원하는 층에 갈수 없는 ..
[BaekJoon] 백준 2146번 다리 만들기
[BaekJoon] 백준 2146번 다리 만들기 문제: https://www.acmicpc.net/problem/2146 내코드 - 어렵게 생각했지만 생각보다 간단했던 문제 - bfs 및 dfs로 풀수 있는 문제다. - 알고리즘 1. 각 섬을 bfs로 돌며 1, 2, ... 라벨링 해준다. 즉, map에서 같은 섬은 같은 번호를 가지고 있다. 2. (섬의 개수 - 1)번 만큼 for문을 돌면서 각각의 섬 번호에 대해 bfs_search()함수를 돌려준다. 3. bfs_search() 함수가 1번 섬에 대해 도는 경우를 생각해보자. 3-1. 1번으로 라벨링된 지점을 모두 queue에 넣어준다. 3-2. queue가 빌때까지 상하좌우의 지점에 대해 만약 바다면 push해주는 것을 반복한다. 3-3. 바다가 ..
[BaekJoon] 백준 9202번 Boggle
[BaekJoon] 백준 9202번 Boggle 문제: https://www.acmicpc.net/problem/9202 내코드 - 어려운 문제 - 트라이 자료구조를 이용하는 문제 - 알고리즘은 다음과 같다 1. 단어 사전의 모든 단어들을 Trie에 저장해 준다. 2. dfs를 통해 삽입된 단어와 일치하는 경우 set에 담는다. (중복 제거) #include #include #include using namespace std; const int ALPHABET = 26; int w, b; bool visited[4][4]; string map[4]; set res; int dx[8] = { -1, 0, 1, -1, 1, -1, 0, 1 }; int dy[8] = { -1, -1, -1, 0, 0, 1, ..