[백준 / C++] 9019번: DSLR

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 탐색 (BFS) 접근 방법 BFS 함수에서 현재 숫자에서 D, S, L, R 연산을 해 큐에 집어 넣는다. 그리고 visited 배열을 통해 방문한 숫자 (0 ~ 9999)를 체크하여 중복된 숫자를 방문하지 않도록 해준다. 구현 방법 현재 레지스터의 숫자를 저장할 int 형과 현재까지의 연산과정을 적은 string 형을 pair..

• format_list_bulleted PS/백준
• · 2023. 8. 7.
• textsms

[백준 / C++] 2467번: 용액 (이분탐색 X, 투포인터 X, 조금 다른 풀이)

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 난이도: solved.ac 골드 5 접근 방법 서로 다른 두 수의 합이 0과 가장 가까운 것을 찾아야 하는 문제다. 합이 0과 가장 가까우려면 어떤 특징이 있을지에 대해 생각해 보았다. 합이 0과 가까우면, 두 수의 절댓값이 서로 비슷하다는 특징이 있다는 것을 발견했다. 이의 역은 성립하지 않는데, 절대값이 비슷하다고 합이 0과 가까운 것은 아니다. 하지만 합이 0과 가까운 두 수는 절대값이..

• format_list_bulleted PS/백준
• · 2023. 8. 7.
• textsms

[백준 / C++] 1662번: 압축

https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 난이도: solved.ac 골드 5 손으로 이 문제를 푼다고 하면, 길이를 계산할 때 가장 안쪽 괄호부터 개수를 세어서 계산한다. 따라서 i 겹의 괄호 안에 몇 개의 숫자가 있는지를 저장하는 len이라는 배열을 만들었다. 편의상 괄호의 겹 수를 level이라고 표현하겠다. 예를 들어 level 3(세 겹의 괄호 안에 있는)인 숫자의 개수가 4개면, len[3] = 4가 된다. 여기서 주의해야..

• format_list_bulleted PS/백준
• · 2023. 8. 7.
• textsms

[백준 / C++] 1068번: 트리 (DFS)

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 그래프 탐색 (DFS) 구현 방법 부모 노드의 번호를 index로 갖는 벡터에 해당 자식 노드의 번호를 저장한다. (Ex. 4번 노드의 부모가 2면, graph[2].push_back(4)) 그리고 삭제할 노드의 번호를 입력받는데, 삭제할 노드가 루트 노드라면 트리는 아예 없어지므로 0을 출력하게 한다. 삭제할 노드가 루트 노드가 아니라면 D..

• format_list_bulleted PS/백준
• · 2023. 8. 6.
• textsms

[백준 / C++] 1987번: 알파벳 (DFS)

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 탐색 (DFS) 접근 방법 및 구현 맨 왼쪽 위 알파벳부터 DFS를 돌리면 된다. 방문한 알파벳을 표시하기 위해서 알파벳은 총 26개이므로 26칸짜리 배열 visited를 선언해 A부터 Z까지 index = 0 ~ 25을 갖도록 해주었다. 따라서 인접한 상하좌우의 알파벳을 방문했는지 O(1)에 체크할 수 있다. 코드 #include ..

• format_list_bulleted PS/백준
• · 2023. 8. 4.
• textsms

[백준 / C++] 11052번: 카드 구매하기 (dp)

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 다이나믹 프로그래밍 (dp) 접근 방법 및 구현 1개의 카드부터 시작해 N개의 카드까지 차례로 구매하는 데 필요한 최대 금액을 계산한다. 계산한 값은 배열 P에 저장했다. 최대 금액을 계산하는 방법은 간단하다. i개의 카드를 살 때 최대 금액을 계산한다고 해보자. 이때 1개부터 i - 1개의 카드를 살 때의 최대 금액은 이미 알고 있다고 하자. i개의 카..

• format_list_bulleted PS/백준
• · 2023. 8. 4.
• textsms