본문 바로가기

Python43

[백준] 짝수 팰린드롬 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/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 배열의 모든 요소들을 0으로 만드는 최소횟수를 구하는 방식으로 바꿔서 생각해보면 편하다. 최소횟수가 되기 위해서는 나누기 연산을 최대한 활용해야하는데 그렇게 하기 위해서 nums의 모든 요소들을 짝수로 만들어주고 나누기를 진행해주면 된다. # 문제링크: https://www.acmicpc.net/problem/12931 import sys input = sys.stdin.readl.. 2023. 2. 6.

티스토리툴바