본문 바로가기

728x90

Python

[백준알고리즘] 10971번: 외판원 순회 2 -Python [백준알고리즘] 10971번: 외판원 순회 2 -Python https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 두 가지 방법으로 문제를 풀었다. 첫 번째 방법은 처음에 푼 방식으로 말 그대로 완전 탐색을 위해서 모든 경우를 탐색하도록 했고, 두 번째 방법은 찾아보니 다들 비트 마스크를 이용해서 문제를 풀었길래 공부해서 다시 .. 더보기
[백준알고리즘] 1451번: 직사각형으로 나누기 -Python [백준알고리즘] 1451번: 직사각형으로 나누기 -Python https://www.acmicpc.net/problem/1451 1451번: 직사각형으로 나누기 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자이다. www.acmicpc.net 브루트 포스 방식으로 해결을 해야 한다. 애를 많이 먹고 다른 분들의 풀이를 살펴본 후 해결했다. 처음에 풀었던 방식으로는 각 테이블을 그룹 1, 2, 3으로 직접 나누었다. 이중 for문을 돌려가며 시작점을 설정하고, 그룹이 시.. 더보기
[백준알고리즘] 1107번: 리모컨 -Python [백준알고리즘] 1107번: 리모컨 -Python https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 브루트 포스로 해결해야 하는 건지 모르고 이상하게 풀었었다... 조건을 다 맞추려고 하다 보니 오류가 계속 발생하고 통과가 안 되는 반례가 계속 존재했다. 이 문제의 경우에는 MAX가 500000으로 depth도 얕기 때문에 recursion depth도 6으로 낮고, 0~9.. 더보기
[백준알고리즘] 1744번: 수 묶기 -Python [백준알고리즘] 1744번: 수 묶기 -Python https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열 www.acmicpc.net 주어진 조건은 아래와 같다. 수열에서 임의의 두 수를 곱할 수 있다. 한 번 묶여서 .. 더보기
[백준알고리즘] 2873번: 롤러코스터 -Python [백준알고리즘] 2873번: 롤러코스터 -Python https://www.acmicpc.net/problem/2873 2873번: 롤러코스터 문제 상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다. 어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다. 이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가 www.acmicpc.net 문제의 규칙만 잘 생각하면 된다. 분류는 그리디 알고리즘으로 되어있으나 내가 푼 .. 더보기
[백준알고리즘] 10610번: 30 -Python [백준알고리즘] 10610번: 30 -Python https://www.acmicpc.net/problem/10610 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는 www.acmicpc.net 만들 수 있는 30의 배수 중에서 가장 큰 수를 출력해야 한다. 여기서 배수 판정법을 .. 더보기
[백준알고리즘] 2875번: 대회 or 인턴 -Python [백준알고리즘] 2875번: 대회 or 인턴 -Python https://www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 문제 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 그런데 올해에는 대회에 참여하려는 학생들 중 K명을 반드시 인턴쉽 프로그램에 참여하라는 학교의 방침이 생기게 되었다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문 www.acmicpc.net 이번 문제는 간단하게 풀었다. 대회 팀의 수를 t라고 했을 때 대회에 .. 더보기
[백준알고리즘] 2261번: 가장 가까운 두 점 -Python [백준알고리즘] 2261번: 가장 가까운 두 점 -Python https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 점이 여러 번 주어질 수도 있다. www.acmicpc.net 진짜 어이없는 문제다. 문제를 푼 코드가 별 차이 없어 보이는데 내 거만 왜 통과를 안 하는지... 코드는 아래 블로그의 코드를 거의 참조해서 겨우 통과했는데... 이전에 통과하지 못한 코드도 별 차이 없는데 안된다.. 게다가 내가 짠 코드는 PyPy에서만 통과를 한다. ㅡㅡ 대체 무슨 차이인지 모.. 더보기

728x90