[백준 / 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

[백준 / C++] 4179번: 불!

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 탐색 (BFS) 접근 방법 J가 F와 동시에 같은 지점으로 이동하면 불에 타 죽는다. 따라서 먼저 F를 이동시킨 후 J를 이동시키는 방법으로 진행했다. 다른 분들은 BFS를 두 번 돌리던데, 하나의 BFS 큐에 J와 F를 넣어서 BFS를 한 번만 돌려도 이 문제를 풀 수 있다. (이렇게 하면 메모리나 시간을 훨씬 단축시킬 수..

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

[백준 / C++] 14500번: 테트로미노 (삼성 SW 역량테스트 기출)

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 구현, 브루트포스 알고리즘 접근 방법 및 구현 ㅗ 모양을 제외한 나머지 모양은 한 지점에서 depth = 4짜리 DFS를 돌리면 구현 가능하다. 신경 써야 할 것은 ㅗ 모양인데, 나는 ㅗ에서 가운데 부분을 기준으로 잡고 상하좌우에서 3개를 골라 그 부분들의 합을 함께 더해주는 식으로 구현했다. 상하좌우에서 3개를 고르는 건 DFS에서 사용한 dy[..

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

[백준 / C++] 2565번: 전깃줄 (LIS 응용)

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 다이나믹 프로그래밍, LIS 접근 방법 전깃줄이 겹치지 않으려면 A 전봇대에서 이어지는 B 전봇대의 번호가 오름차순이어야 한다. 따라서 자르는 전깃줄의 개수를 최소화하려면 LIS를 찾아야 한다. 가장 긴 증가하는 부분 수열만을 남기고 나머지는 다 잘라버려야 한다. 구현 LIS 알고리즘 사용해서 (11053번 포스팅 코드 참고) 가장 긴 수열의 길이를 구하..

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