본문 바로가기

vividswan

Notice

블로그 이전 완료

Recent Posts

Popular Posts

Recent Comments

Link

깃허브

Calendar

Tags

더보기

Archives

Visits

Today

Yesterday

알고리즘

Algorithm/BOJ 2022. 3. 12. [BOJ] 퇴사(14501) [백준(BOJ)] 퇴사(14501) C++ 문제 : BOJ_14501번 퇴사 문제 설명 완전 탐색 n 개의 날이 있고, n+1일째 퇴사를 합니다. 이때 각 요일마다 할 수 있는 일에 필요한 기간과 그에 대한 보상이 각각 주어집니다. n+1 째는 퇴사하므로 일할 수 없고, n 일 안에 처리할 수 있는 일들 중에서 최대한의 보상을 받을 수 있게 할 일을 골라야 합니다. n이 최대 15임으로 완전 탐색으로 해결할 수 있습니다.(O(2^n)) Solution 재귀 함수를 만들고, 해당 일을 선택하는 경우와 선택하지 않는 경우로 마지막 일까지 순회합니다. 이때, expired를 만들어서 이전 요일에서 선택한 일에 대한 일을 하는 중이 아닌 경우 현재 일을 선택하는 경우로 재귀 함수를 사용할 수 있습니다. Desc..

Algorithm/BOJ 2022. 3. 12. [BOJ] 평범한 배낭(12865) [백준(BOJ)] 평범한 배낭(12865) C++ 문제 : BOJ_12865번 평범한 배낭 문제 설명 DP(냅색 알고리즘) DP 문제 중 유명한 문제인 평범한 배낭 문제입니다. 물품의 수와 배낭에 담을 수 있는 최대 무게가 주어집니다. 이어서 각각 물품의 무게와 가치가 주어지며, 가방 안에 최대 무게를 초과하지 않게 넣었을 때 최대 가치를 출력하는 문제입니다. 이때 주의할 것은 각각의 물품은 하나만 들어갈 수 있으므로, 하나의 물품이 중복되게 들어가는 경우의 수는 피해야 합니다. Solution dp를 이용한 풀이를 해봤습니다. 2차원 dp를 다음과 같이 만들었습니다. dp[i 번째까지 물건을 사용했을 때][무게가 j 일 때] = 최댓값 1~n까지의 물건에서 현재 최댓값을 알고자 하는 무게가 j라고 했을..

Algorithm/BOJ 2022. 3. 11. [BOJ] 외판원 순회(2098) [백준(BOJ)] 외판원 순회(2098) C++ 문제 : BOJ_2098번 외판원 순회 문제 설명 비트마스킹 n 개의 여행지가 있을 때, 각 여행지에서 다른 여행지로 갈 수 있는 비용이 주어집니다. 이때 비용을 최소한으로 해서 출발한 여행지에서 모든 여행지를 방문한 뒤 다시 출발한 여행지로 돌아오는 비용을 구하는 문제입니다. 이때 한 번 방문했던 여행지는 다시 방문할 수 없습니다. 비트 마스킹 외에도 여러 가지 방법으로 해결할 수 있는 유명한 문제입니다. 여행지의 수가 최대 16이기 때문에 16개의 자리수를 만들고 비트 연산으로 방문한 여행지를 체크하는 방식으로 비트 마스킹으로 해결할 수 있습니다. Solution recursion 함수를 만들어 줍니다. 이때, 함수의 내용은 recursion(현재 도시..

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을 사용했는데, 이유는 다음과 같습니다. 첫 번째 원소를 삽입, 삭제할 수 있다. 마지막 원소를 삽입, 삭제할 수도 있다. 인덱스..

이전 1 2 3 4 5 6 7 8 다음

티스토리툴바