본문 바로가기
728x90

알고리즘339

[python] 백준 2659 십자카드 문제 https://www.acmicpc.net/problem/2659 2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 문제 해결 주어진 입력값을 가지고 시계수를 구하는 함수를 만든다. 그 방법은 맨 앞의 숫자를 맨 뒤로 옮겨가며 가장 최솟값이 나오는 수를 구하면 된다. 1111은 가장 작은 시계수인 것은 명백하다. x를 입력값을 십자모형의 카드에 넣어 얻은 시계수라고 하면 1111부터 x까지 시계수의 개수를 구하면 되는 문제이다. CODE import sys input = sys.stdin.readline def clock_num(n): .. 2023. 10. 18.
[C++] 백준 3059 등장하지 않는 문자의 합 https://www.acmicpc.net/problem/3059 3059번: 등장하지 않는 문자의 합 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성되어 있고, 문자열 S가 주어진다. S는 알파벳 www.acmicpc.net 문제 해결 문자의 ASCII 숫자를 활용해서 해결하는 간단한 문제 CODE #include #include using namespace std; int main() { int t; cin >> t; for (int T = 0; T > s; int answer = 0; for (int i = 0; i <.. 2023. 10. 15.
[python] 백준 14923 미로 탈출 https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 문제 해결 전형적인 BFS문제 그러나 편하게 BFS를 돌리면 시간초과가 난다.(벽을 한 번만 깰 수 있다는 것을 활용해야함) 그래서 array를 3차원으로 해서 n*m*2차원을 만든다. (board[i][j][k]: (i,j)에 있고 k개의 magic 사용 가능) 도착점 왔으면 최소이동횟수이므로 cnt출력하면 끝 CODE import sys input = sys.stdin.rea.. 2023. 10. 14.
[python] 백준 17835 면접보는 승범이네 https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 문제 해결 다익스트라를 이용해야 한다는 것은 쉽게 알 수 있다. 그러나 출발점→도착점 이동을 모두 계산하기에는 계산해야하는 양이 많아 시간복잡도에서 걸린다. 따라서 도착점에서 시작해서 각 출발점까지 얼마나 걸리는지 계산하는 것이 더 빠르다. CODE import sys input = sys.stdin.readline import heapq d.. 2023. 9. 29.
728x90