본문 바로가기

vividswan

Notice

블로그 이전 완료

Recent Posts

Popular Posts

Recent Comments

Link

깃허브

Calendar

Tags

더보기

Archives

Visits

Today

Yesterday

c++

Algorithm/BOJ 2022. 3. 10. [BOJ] 스도쿠(2580) [백준(BOJ)] 스도쿠(2580) C++ 문제 : BOJ_2580번 스도쿠 입출력 형식만 살짝 다른 같은 문제로 BOJ_2239번 스도쿠도 있습니다. 문제 설명 백트래킹, dfs 완성되지 않은 스도쿠가 주어지고, 이를 완성하는 문제입니다. 스도쿠의 수가 확정되지 않은 곳은 0으로 입력되어 있고, 이 0들을 전부 채운 스도쿠판을 출력해야 합니다. 문제는 스페셜 저지이므로, 하나의 경우가 아닌 여러 경우가 답이 될 수 있는 스도쿠는 그중 하나를 출력하면 정답 처리가 됩니다. dfs와 백트래킹을 이용해야 합니다. Solution 입력 번호가 0인 곳의 좌표들을 하나하나 저장합니다. 저장된 좌표를 하나씩 dfs로 순회합니다. 이때 현재 순회 중인 곳에 맞는 번호가 있으면 다음 순회로 진행하고, 1~9 모든 번..

Algorithm/BOJ 2022. 3. 10. [BOJ] 백조의 호수(3197) [백준(BOJ)] 백조의 호수(3197) C++ 문제 : BOJ_3197번 백조의 호수 문제 설명 이분탐색, bfs 물 공간과 빙판 공간이 있는 지도가 주어지고, L에 두 백조의 위치가 주어집니다. 물 공간과 가로, 세로로 접한 빙판 부분이 하루에 한 번씩 녹는데, 이때 두 백조가 만날 수 있는 최소의 날을 계산하는 문제입니다. 이 문제는 하루에 한 번씩 녹는 빙판 부분도 고려해야 하고, 또 빙판이 녹았을 때 만날 수 있는 최소의 날도 구해야 하기 때문에 bfs와 이분 탐색 두 가지가 쓰이는 문제입니다. Solution 처음에 bfs를 이용하여 빙판이 모두 녹는 최대 날을 이분 탐색의 max 값으로 지정해 주고 이분 탐색을 실행합니다. 최솟값과 최댓값의 중간값으로 bfs를 돌리며 중간값의 날이 되기 전에..

Algorithm/BOJ 2022. 3. 10. [BOJ] 후위 표기식(1918) [백준(BOJ)] 후위 표기식(1918) C++ 문제 : BOJ_1918번 후위 표기식 문제 설명 Stack 중위 표기식으로 예제가 주어지면 이것을 후위 표기식으로 바꾸는 문제입니다. 피연산자는 알파벳 대문자만 나오며, '-'가 가장 앞에 나오거나, '*'가 생략되는 입력은 허용하지 않습니다. stack을 상황에 맞게 활용해서 풀어야 하는 문제입니다. Solution 전체 문자열을 입력받고 아래와 같은 규칙으로 순회합니다. 피연사자는 무조건 화면에 출력한다. '('가 나오면 stack에 push 한다. ')'가 나오면 '('가 나올 때까지 stack을 비우며 출력한 뒤, 마지막 '('도 출력 없이 pop 해준다. 연산자가 나왔을 때 stack에 top에 자신보다 우선순위가 같거나 높은 연산자가 있으면 그..

Algorithm/BOJ 2022. 3. 10. [BOJ] 행운의 바퀴(2840) [백준(BOJ)] 행운의 바퀴(2840) C++ 문제 : BOJ_2840번 행운의 바퀴 문제 설명 구현 저에게는 어려운 구현 문제였습니다. N개의 숫자가 원형으로 쓰여있는 원형 판을 항상 시계방향으로 돌립니다. 이때 돌아간 칸의 수와 가리키는 칸에 쓰여있는 알파벳 문자가 K 번 입력됩니다. 이를 바탕으로 마지막으로 가리키는 칸부터 순서대로 원형의 알파벳을 출력하는 문제입니다. Solution 저는 우선 크기에 맞는 벡터 배열을 할당했습니다. 또 원형 판을 하나의 배열로 생각했고, 순회 시켰습니다. 이때 원형 판이 시계방향으로 돌아간다는 것은 배열의 입장에선 마이너스로 도는 것이기 때문에 회전한 칸 수만큼 마이너스를 하여 문자를 넣어주었습니다. 문제가 어려웠던 이유는 중복된 값을 처리하는 것이었습니다. 문..

Algorithm/BOJ 2022. 3. 10. [BOJ] 회전하는 큐(1021) [백준(BOJ)] 회전하는 큐(1021) C++ 문제 : BOJ_1021번 회전하는 큐 문제 설명 Deque 1 ~ N까지의 수가 양방향 순환 큐에 나열되어 있는 상태에서 M 개의 원소를 뽑아야 합니다. 이때 나열되어 있는 방식이 순환 큐이기 때문에 첫 번째 위치의 원소만 뽑아낼 수 있고, 첫 번째 위치가 아니라면 순환으로 왼쪽 혹은 오른쪽으로 회전하며 원소를 첫 번째 위치로 이동시켜 뽑아야 합니다. 이때 왼쪽 오른쪽으로 회전하는 횟수의 최소를 구해야 합니다. Solution N이 50보다 작기 때문에 무슨 방법을 쓰든 구현만 해낸다면 정답 처리가 될 것입니다. 저는 deque을 사용했는데, 이유는 다음과 같습니다. 첫 번째 원소를 삽입, 삭제할 수 있다. 마지막 원소를 삽입, 삭제할 수도 있다. 인덱스..

Algorithm/이론 2022. 3. 10. [알고리즘] 이진 트리 탐색 이진 트리 탐색 C++ 이진 트리에서의 전위 순회, 중위 순회, 후위 순회를 알아봅시다. 이진 트리 트리 구조이므로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 또한 사이클 역시 존재할 수 없다. 각각의 노드가 최대 두 개의 자식 노드를 가지고 있음 자식 노드를 각각 왼쪽 자식 노드, 오른쪽 자식 노드라고 칭한다. 전위 순회, 중위 순회, 후위 순회의 탐색을 가지고 있다. 최상위 루트 노드를 가지고 있다. 전위 순회 전위 순회의 진행은 깊이 우선 순회라고도 하며, 다음의 세 가지 순서로 진행된다. 부모 노드를 방문한다. 왼쪽 자식 노드를 방문한다. 오른쪽 자식 노드를 방문한다. 즉, 부모 노드가 1, 왼쪽 자식 노드가 2, 오른쪽 자식 노드가 3이라면 1 -> 2 -> 3의 순으로 방문한다. 중위..

Algorithm/BOJ 2022. 3. 9. [BOJ] 오르막 수(11057) [백준(BOJ)] 오르막 수(11057) C++ 문제 : BOJ_11057번 오르막 수 문제 설명 DP DP로 해결할 수 있는 오르막 수입니다. 1부터 1,000의 수 중 하나인 N이 주어지면, N 자리로 이루어진 오르막 수의 개수를 구하는 문제입니다. 여기서 오르막 수란, 가장 큰 자릿수부터 가장 작은 자릿수가 오름차순으로 올라가야 하는데, 이 문제에선 수가 같아도 오름차순으로 인정해 줍니다. 또 특이한 점은 수가 0으로 시작할 수 있습니다. Solution 저는 2차원 dp 배열을 만들어 문제를 해결했습니다. dp[수의 길이][가장 큰 자릿수의 수] -> 만족하는 수의 오르막 수의 개수 우선 N이 1인 경우를 생각해봅시다. 문제의 조건이 '수는 0으로 시작할 수 있다.' 임으로, 0,1,2,3 .....

Algorithm/BOJ 2022. 3. 9. [BOJ] 제곱수의 합(1699) [백준(BOJ)] 제곱수의 합(1699) C++ 문제 : BOJ_1699번 제곱수의 합 문제 설명 DP DP로 풀 수 있는 기본문제 동전 2와 유사한 제곱수의 합 문제입니다. 1부터 10만까지의 수 중 하나가 주어졌을 때, 그 수를 제곱수로 표현할 수 있는 최소항 개수를 구하는 문제입니다. 예를 들어, 11의 경우엔 11 = 2^2 + 2^2 + 1^2 + 1^2 + 1^2 5개 항도 가능합니다. 하지만, 11 = 3^2 + 1^2 + 1^2 의 3개항으로도 표현이 가능하므로 11이 주어지면 3을 출력해야 합니다. Solution 항의 개수를 최소한으로 쓰기 위해 처음 했던 생각은, 단순하게 주어진 수와 최대한 가까운 제곱수를 구하는 것이었습니다. 예를 들어, 145면 12^2, 100이면 9^2과 같이..

이전 1 2 3 4 5 6 7 다음

티스토리툴바