본문 바로가기

728x90

Algorithm

[백준알고리즘] 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라고 했을 때 대회에 .. 더보기
[백준알고리즘] 2448번: 별 찍기 - 11 -Python [백준알고리즘] 2448번: 별 찍기 - 11 -Python https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (k ≤ 10) www.acmicpc.net 와;; 난해했다.. 사실 코드는 그럭저럭 바로 짜기 시작했었는데 이것저것 걸리는 것들이 많았다.. 우선 출력시 *의 끝부분까지만 출력하는 것이 아니라 * 뒤에도 빈 공간을 출력해주어야 했다. 그리고 초기 테이블에 이상한 값이 끼었었는지 똑같은 코드인데도 계속 100퍼센트에서 틀리길래 table 생성 부분만 조금 손봤더니 정상적으로 통과했다. 나는 분할정복 개념으로 문제를 풀었다. 큰 삼각형에서 작은 서브 삼각.. 더보기
[백준알고리즘] 11725번: 트리의 부모 찾기 -Python [백준알고리즘] 11725번: 트리의 부모 찾기 -Python https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리의 연결 정보가 주어졌을 때 각 노드의 부모를 모두 출력하는 문제이다. 처음 주어진 입력 정보를 각 노드의 번호별로 리스트를 통해서 유지했다. 그 후 head[]라는 부모 노드의 번호를 가리키는 리스트를 생성해주었고, 1번 노드부터 BFS 방식으로 문제를 풀었다. 각 노드와 연결된 노드 중에서 아직 head[]에 부모 노드가 결정되지 않은 노드는 현재 노드를 부모로 하도록 해주었다. 사이클이 없.. 더보기
[백준알고리즘] 1167번: 트리의 지름 -Python [백준알고리즘] 1167번: 트리의 지름 -Python https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다) 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되 www.acmicpc.net 와 이 문제도 되게 오래 걸려서 풀었다... 오래 걸린 이유는 두 가지로 뽑을.. 더보기

728x90