728x90 Python 썸네일형 리스트형 [백준알고리즘] 1517번: 버블 소트 -Python [백준알고리즘] 1517번: 버블 소트 -Python https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 당연히 일반적인 방법으로 문제를 해결할 경우 시간 초과가 발생할 것이란 것을 알고 있었다. 그런데 그거 외에는 방법을 모르겠어서.. 각각의 값마다 앞의 인덱스에서 자신보다 큰 값의 개수를 새는 것까지는 생각했는데 결국 O(N^2)을 벗어날 수 없었다. # 여기서 앞에 존재하는 큰 값의 개수를 세는, 역순으로 존재하는 수의 개수를 찾는 .. 더보기 [백준알고리즘] 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 생성 부분만 조금 손봤더니 정상적으로 통과했다. 나는 분할정복 개념으로 문제를 풀었다. 큰 삼각형에서 작은 서브 삼각.. 더보기 [백준알고리즘] 2447번: 별 찍기 10 -Python [백준알고리즘] 2447번: 별 찍기 10 -Python https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (3, 9, 27, ...) (N=3k, 1 ≤ k < 8) www.acmicpc.net 모든 공간을 *로 채워준 다음에 지워야 할 부분들을 지워주었다. 각 상태에서 9개의 구역을 나눠 가운데에 위치한 구역은 모두 빈칸 ' '을 만들어주어야 한다. 그리고 나눠진 작은 구역들도 반복해서 수행해준다. 아래에 새롭게 푼 코드를 추가했는데 재귀를 사용해서 더 깔끔하게 풀었다. def rm(i, j, size): if size == 1: return new_size = size//3 for ri in .. 더보기 [백준알고리즘] 11729번: 하노이 탑 이동 순서 -Python [백준알고리즘] 11729번: 하노이 탑 이동 순서 -Python https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 오랜만에 하노이탑 문제를 푼 것 같다. 분할 정복 문제.. 더보기 [백준알고리즘] 11728번: 배열 합치기 -Python [백준알고리즘] 11728번: 배열 합치기 -Python https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. www.acmicpc.net 그냥 서로 다른 두 배열을 정렬된 상태로 출력하는 문제이다. 아래처럼도 풀어봤고, 각각 정렬된 두 배열에서 작은 값부터 하나씩 비교해서 결과를 출력하는 코드도 작성했으나 아래의 코드가 조금 더 빨랐고 간단해 보여서 그냥 잔뜩 파이썬스러운 코드만 올렸다. 1 2 3 4 5 6 import .. 더보기 [백준알고리즘] 10815번: 숫자 카드 -Python [백준알고리즘] 10815번: 숫자 카드 -Python https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 www.acmicpc.net 처음에 주어진 수들이 존재하고, 다음에 주어지는 값들이 여기에 존재하는지 판.. 더보기 [백준알고리즘] 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 와 이 문제도 되게 오래 걸려서 풀었다... 오래 걸린 이유는 두 가지로 뽑을.. 더보기 이전 1 ··· 8 9 10 11 12 13 14 ··· 22 다음