Algorithm48 1629. 곱셈(C++) 재귀를 이용하여 푸는 문제다. 처음에는 정말 어려웠다. 우리가 아는 상식대로 그냥 제곱해서 풀면 안됨? 이라면서 그냥 풀어보려고 했으나.. 수의 크기가 어마어마 해서 그걸로는 턱없이 부족했다. 강의에서 문제를 푸는 사고를 설명해줬다. a^n * a^n = a^2n 이다. (??????????????) (뭐 어쩌라고) 그러니까 그 다음 공식을 보면 굳이 주어진 식 그대로 풀지 않고서도 반으로 나누어서 푸는 식으로도 문제의 답을 구할 수 있다라는 의미이다. 그 아래의 1번 도미노가 쓰러진다. 그러면 k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다라는 공식이 성립이 된다라는 뜻이다. 그럼 1승을 계산할 수 있다라는건, k승을 계산했으면 2k승과 2k+1승도 O(1)에 계산할 수 있다라는 결과에 도달한다. 이.. 2021. 4. 21. 2178. 미로 탐색 (C++) 개인적으로는 이 문제가 그림 문제보다 쉬웠다. 미로의 최소칸 수를 구하는 문제다. BFS를 이용하여 지나간 곳이 아니거나 0이 아닌곳만 열심히 이동하다보면 나오는 문제다. #include using namespace std; #define X first #define Y second string board[102]; int dist[102][102]; int n,m; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 0; i > board[i]; } for(int i = 0; i < n; i++) fil.. 2021. 4. 18. 1926. 그림 (C++) 이번 문제느 BFS를 이용하여 푸는 문제였다. BFS를 사실 학교 다녔을 때 배웠던 기억이 있긴한데, 그게 뭐였는지는 까맣게 잊고 있었다.. 그런데 이번에 강의를 통해서 다시금 기억과 구현을 하게 됐고, 그 첫번째 문제로 이 문제를 택했다. 이 문제는 BFS 를 사용하는데 있어서 가장 기본적인 문제라고 생각한다. 문제에서 보면 그림의 개수 와 그림중 가장 넓이가 넓은 것을 출력하라고 했다. 원하는 수가 두개이다. 예제 입력 1을 보고 설명해보자면, 1로 시작하는 그림은 총 4개, 가장 큰 그림은 9의 크기인 우 하단의 그림이 될 것이다. 이걸 어떻게 풀면 될까? BFS를 사용하자! BFS : 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 BFS는 나중에 다른 글로 자세히 설명하겠다.. 2021. 4. 18. 2504. 괄호의 값 (C++) 한 3일 걸린 듯 하다..끝끝내 혼자 힘으로 풀지는 못했다.. 거의 다 왔는데 항상 이런다.. 암튼 이 알고리즘을 생각하기가 너무 어려웠다. 괄호마다 곱하는 수도 다르고 닫는 위치에 따라 더할지 곱할지가 정해지니 머리가 터질 지경이었다. 알고리즘은 다음과 같다. 1) 왼쪽 괄호가 나올 때마다 스택에 넣는다. tmp를 선언하고 소괄호가 나올 때엔 2를 곱하고 대괄호가 나올 때엔 3을 곱한다. tmp 는 0으로 초기화하는것이 아닌 1로 초기화를 해줘야 한다. 곱하기는 0과 곱하면 무조건 0 이지않은가. 2) 출력의 문구에서 볼 수 있듯이 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다고 했다. 그래서 그 조건문 또한 bool로 구분하여 추가했다. 3) 오른쪽 괄호가 나올경우 스택에서 뺀다. 3-1.. 2021. 4. 16. 덱 덱은 Restricted Structure의 끝판왕 같은 느낌의 자료구조 인데, 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 참고로 자료구조에서의 덱은 deque고, Doble Ended Queue라는 뜻이다. 덱의 성질 1. 원소의 추가/ 제거 O(1) 2. 제일 앞/뒤의 원소확인 O(1) 3. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 하지만 특이하게도 STL deque에서는 인덱스로 원소에 접근할 수 있다. #include #include using namespace std; int main() { deque dq; dq.push_back(1); dq.push_back(2); for(int i = 0; i < dq.size(); i++) { cout 2021. 4. 14. 5430 . AC (C++) 하..AC 나오는 문제였다. 아니 풀이는 다 풀었는데 50퍼에서 계속 틀렸읍니다. 뜨니 멘탈이 와르르.. 아무튼 이 문제는 덱을 이용하여 푸는 문제이다. 근데 문제 중간에서 R을 입력하면 뒤집는다고 나와있는데, 굳이 덱에 있는 숫자들을 돌릴 필요는 없다라는 걸 이틀만에 깨달았다;;; 생각보다 간단하게 생각하면 된다. bool을 이용해 뒤집었을때, 안뒤집어졌을때, 에러가 났을때, 안났을때 등을 설정해놓으면 생각보다 쉽게 문제를 풀 수 있었다. 근데 아까 50퍼에서 틀렸다는건 아마도 input 단계에서 입력하는 방법이 잘못 됐던것 같다. 난 그냥 숫자만 입력하면 되는줄 알았지만, ㄹㅇ 예시 입력 페이지에서 나오는 것처럼 입력을 해야 했던 것이었다. 이것도 이틀만에 알아채서 그거 찾아보며 구현을 하느라 좀 걸.. 2021. 4. 14. 이전 1 ··· 3 4 5 6 7 8 다음 IT_learning's Commit
