본문 바로가기

분류 전체보기154

[백준] 짝수 팰린드롬 https://www.acmicpc.net/problem/21925 21925번: 짝수 팰린드롬 (1, 1), (5, 6, 7, 7, 6, 5), (5, 5) www.acmicpc.net 반례 찾기가 힘들었던 문제입니다. 스택으로 탐색하면서 짝수 팰린드롬을 만족하는 경우 매칭되는 문자의 인덱스를 저장해둡니다. 단순히 스택만 이용했을 때에는 짝수 팰린 드롬을 만족하지 못하는데에도 정답이라고 나오는 경우가 있습니다. 매칭되는 문자의 인덱스를 저장한 다음 이것을 짝수 팰린드롬을 만족하는지 체크하는데에 사용됩니다. import sys # sys.stdin = open("input.txt", "r") # 숫자의 개수 n = int(input()) # 숫자들 nums = list(map(int, input().sp.. 2023. 2. 13.
[백준] 폴더 정리(small) https://www.acmicpc.net/problem/22860 22860번: 폴더 정리 (small) main 폴더 하위에는 FolderA 폴더 하위에 있는 File1, File2, FolderB 폴더 하위에 있는 File1, File3이 있다. 파일의 종류는 File1, File2, File3 총 3가지이고, 파일의 총 개수는 File1, File2, File1, File3 총 4개이다. mai www.acmicpc.net DFS와 SET을 활용하여 풀 수 있는 문제입니다. 현재 폴더의 하위에 폴더를 만난 경우에는 하위 폴더로 탐색을 시작하게 되고 탐색이 끝나면 하위 폴더들 밑에 있는 파일의 종류와 숫자를 리턴으로 받게 됩니다. 파일의 개수는 더해주고 파일의 종류는 SET이므로 현재 폴더 종류에 .. 2023. 2. 12.
[백준] 탑 보기 https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 스택을 이용하면 풀 수 있는 문제입니다. 빗물문제와 비슷해서 풀이법을 비교적 쉽게 떠올릴 수 있었습니다. 해당 문제를 풀으신 분들은 빗물문제도 도전해보시면 좋을 것 같습니다. 왼쪽 -> 오른쪽, 오른쪽 -> 왼쪽으로 탐색하면서 본인보다 작은 건물들을 스택에서 제거해주면됩니다. 왼쪽 -> 오른쪽을 예시로 설명드리겠습니다. 왼쪽에서 오른쪽으로 탐색하면서 스택에는 빌딩들의 인덱스를 저장하게 됩니다... 2023. 2. 11.
[백준] A를 B로 https://www.acmicpc.net/problem/13019 13019번: A를 B로 첫째 줄에 A, 둘째 줄에 B가 주어진다. 두 문자열의 길이는 같으며, 길이는 50을 넘지 않는다. 또, 알파벳 대문자로만 이루어져 있다. www.acmicpc.net 그리디 문제입니다. 그리디 문제에 약해서 풀이까지 애를 먹었습니다. 아이디어는 간단합니다. 먼저 문자열을 정렬해서 비교했을 때 같은 문자들로 구성되어 있지 않으면 아무리 이동시켜도 만들 수 없습니다. 이제 두 문자열은 같은 문자들로 구성이 돼있음이 보장됩니다. 다음으로, 이제 A와 B의 뒤에서 부터 문자를 비교하여 같은 경우에는 이동시킬 이유가 없으므로 계속해서 버립니다. 이제 A와 B의 마지막 문자가 다르므로 A에서 이동이 필요합니다. 마지막 문.. 2023. 2. 10.
[백준] 산책(small) https://www.acmicpc.net/problem/22868 22868번: 산책 (small) 첫 번째 줄에는 정점의 개수 $N$과 두 정점 사이를 잇는 도로의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째 줄부터 $M + 1$ 번째 줄까지 정점 $A, B$가 공백으로 구분되어 주어진다. 정점 $A$와 www.acmicpc.net S -> E로의 최단거리를 구해 해당 경로를 위해 사용된 정점을 제외하고 E -> S로의 최단거리를 구해주면 된다. 간선의 길이가 1으로 고정이 되어있으므로 BFS를 2번 돌려서 풀이가 가능합니다. 이 문제의 포인트는 최단 경로를 위해 사용된 노드들을 기록해야하는데 이는 S -> E를 위한 BFS를 돌릴 때 현재 노드의 이전 노드를 기록해두면 됩니다. 다음 노드를 .. 2023. 2. 10.
[백준] 원 이동하기 2 https://www.acmicpc.net/problem/22948 22948번: 원 이동하기 2 좌표평면에 원의 중심이 x축 위에 있는 $N$개의 원이 존재한다. $N$개의 원 중 임의의 두개의 원을 선택했을 때 내접, 외접 등 교점이 존재하지 않도록 존재한다. 하나의 원이 다른 원 안에 포함될 www.acmicpc.net A원과 B원 사이의 경로를 구하는 문제입니다. 먼저, 저는 크게 2가지 케이스로 나누어서 진행하였습니다. A와 B중 한쪽이 나머지 한쪽에 포함되는 경우, 그렇지 않은 경우로 나누었습니다. 1. 한쪽이 나머지 한쪽을 포함하는 경우 어느 원이 더 큰 원인지를 판별하기 위하여 반지름을 비교하게 됩니다. 만약, 도착원인 B가 더 작은 경우에는 B를 포함하고 도 큰 원들의 리스트에 시작원인 .. 2023. 2. 9.
[백준] 뉴스 전하기 https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 문제를 제대로 파악하는데 시간이 걸린 문제입니다. 처음에는 단순 BFS로 접근했다가 부하 직원에게 동시에 통화가 불가능하다는 조건을 깨닫고는 풀이를 1차 변경, 간접 상사 직원도 통화가 가능하다고 생각했는데 직속 부하 직원에게만 통화가 가능하다고 해서 2차 풀이 변경, 무조건 현재 노드를 루트로 하는 서브트리의 노드 개수가 많은 노드부터 BFS로 탐색하는 풀이로 진행했다가 마지막으로 각각의 서브트리에서.. 2023. 2. 8.
[백준] 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 3차원 배열을 이용하여 BFS를 해야하는 문제입니다. 단순하게 [벽을 부쉈는지 여부][y][x]로 정의하고 각각의 상태에서 가질 수 있는 최소 거리를 저장해두면 된다. 즉, 벽을 부수고 도달할 수 있는 최단거리와 벽을 부수지 않고 도달할 수 있는 최단 거리중 더 짧은 거리를 답으로 출력하면 된다. import sys from collections import deque i.. 2023. 2. 7.
[백준] 원판 돌리기 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net Deque를 활용한 구현, 시뮬레이션 문제입니다. 지문을 제멋대로 해석하는 바람에 살짝 해맸던 문제입니다. 회전한 다음 지워진 숫자가 없는 경우 평균을 구해 더하거나 빼는 작업을 진행해야하는데 각 원판별로 체크를 해서 진행하는 줄 알았는데 원판 전체에 대해 지워진 경우가 없을 때에만 작업을 해줘야합니다. 그리고 x배수의 원판을 회전시켜야하는데 이부분에서 실수가 있었습니다. 포인트가.. 2023. 2. 7.

티스토리툴바