본문 바로가기
728x90
반응형

코딩/백준

알고리즘 - Python / 백준 - 1758번 : 알바생 강호 1758번: 알바생 강호 (acmicpc.net) 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 풀이 간단한 정렬 문제이다. 비싼 금액을 받아야 하므로 , 비싼금액부터 싼금액 순으로 정렬해 계산값을 모두 더해 출력하면 된다. 파이썬을 사용해 정렬을 구현하지는 않았고 , 문제 자체는 정렬 알고리즘만 구현하면 되는 문제다. import sys n = int(sys.stdin.readline()) stack = [] for _ in range(n): stack.append(int(sys.stdi.. 더보기
알고리즘 - Python / 백준 - 1041번 : 주사위 1041번: 주사위 (acmicpc.net) 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 풀이 주사위를 쌓아 보이는 면의 숫자합이 가장 작도록 쌓고 그 합을 구하는 문제이다. 주사위를 놓을 때 한 면만 보이는 경우 , 두면이 보이는 경우 , 세면이 보이는 경우로 나뉜다. 한 면의 경우는 주사위 6개의 면중 가장 작은 수 , 두면의 경우는 그리디 알고리즘을 통해 가장 숫자가 작은 면과 붙어있는 4개의 면중 그다음으로 작은 면을 고르면 된다. 세면의 경우도 그리디 알고리즘으로 구현하려 .. 더보기
알고리즘 - Python / 백준 - 2023번 : 신기한 소수 2023번: 신기한 소수 (acmicpc.net) 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 n ( 1 ~ 8 ) 자리 수를 왼쪽에서부터 1,2,... n 자리로 잘라 읽었을 때 모두 소수인 수를 신기한 소수라고 하고 , 입력받은 자릿수의 신기한 소수를 모두 출력하면 된다. 왼쪽에서 부터 잘라 읽었을 떄 모두 소수가 되야 하므로 , 기존에 있던 소수 뒤에 0 ~ 9를 붙여 다음 자릿수의 소수후보들을 만들고 그 소수후보들중에서 소수를 추려 각 자릿수 배열에 넣는 방식으로 해결하였다. 소수 .. 더보기
알고리즘 - Python / 백준 - 1074번 : Z 1074번: Z (acmicpc.net) 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 풀이 2^N * 2^N 쿠기의 배열을 Z모양으로 탐색한다. 한번에 정사각형 모양으로 탐색하므로 쪼갤 수 있는 가장 작은 단위까지 쪼개면서 세면된다. 4등분을 한 후 , 등분에 따라 0 , SIZE * 1/4 , SIZE * 2/4 , SIZE * 3/4 의 인덱스로 쪼개고 각각을 더해가면서 몇번째로 탐색하는지 알아낼 수 있다. 문제의 예제인 2 3 1 의 경우 , 처음 쪼갤때는 SIZE * 2/4 인 조각에 속하.. 더보기
알고리즘 - Python / 백준 - 1780번 : 종이의 개수 1780번: 종이의 개수 (acmicpc.net) 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 풀이 3의 제곱수로 이루어진 정사각형의 종이를 한 정사각형안에 같은 숫자로만 이루어지도록 하고 그렇지 않으면 9등분을 반복하는 문제이다. 따라서 더 잘라야할 상황이 나오면 더 자르도록 분할해서 해결하면 된다. 재귀함수를 통해서 문제 분할을 구현하였다. import sys stack = [] n = int(sys.stdin.readline()) for _ in range(n): stack.append(l.. 더보기
알고리즘 - Python / 백준 - 2116번 : 주사위 쌓기 2116번: 주사위 쌓기 (acmicpc.net) 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 풀이 주사위가 n개 있고 각 주사위의 윗면과 아랫면이 같도록 맞추어 쌓아 올리고 그때 , 옆면의 수를 모두 더하여 가장 큰 수를 출력하는 문제이다. n이 최대 10,000 이고 , 가장 아래 주사위의 윗면을 컨트롤 하는 것으로 위쪽의 모든 주사위들을 어떻게 세울지 정해지므로 계산 횟수가 크지 않을 것이라 생각하고 특별한 알고리즘을 사용하지 않고 구현해보았다. 가장 밑의 주사위의 윗면이 1 ~ 6 일때의 경우를 모두 살.. 더보기
알고리즘 - Python / 백준 - 1389번 : 케빈 베이컨의 6단계 법칙 1389번: 케빈 베이컨의 6단계 법칙 (acmicpc.net) 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 입력 노드가 1 ~ N 까지로 들어오고 , 모든 노드를 최단거리로 갈때 거치는 간선의 수의 합이 가장 작은 노드를 찾는 문제이다. BFS로 풀면 될 듯 싶어 , BFS로 노드를 탐색하고 해당 노드까지 가는데 걸린 간선수를 따로 리스트에 저장했다. 이후 그 노드에서 다른 노드로 간선을 하나 이동했다면 , 리스트에 저장한 이전 노드까지 움직이는데 거.. 더보기
알고리즘 - Python / 백준 - 18870번 : 좌표 압축 18870번: 좌표 압축 (acmicpc.net) 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이 문제 내용은 받아온 수들을 정렬해 순서를 정해주는 문제 였다. 중복되는 수의 경우 같은 순서에 위치 하게 된다. 힙 구조를 이용한 힙 정렬을 이용해 정렬하고 , 이전에 pop 된 수와 비교하여 같으면 index를 증가시키지 않도록 구현했다. import sys import heapq n = int(sys.stdin.readline()) heap = [] sta.. 더보기
반응형

티스토리툴바