AndroidTeacher

programmers.co.kr/learn/courses/30/lessons/72412 5: queryl[j].remove("and") for i in range(len(infol)): for j in range(len(queryl)): flag = 0 for k in range(4): if infol[i][k] != queryl[j][k]: if queryl[j][k] != '-': flag = 1 break if flag == 0: if int(infol[i][4]) >= int(queryl[j][4]): answer[j] += 1 return answer 효율성을 통과하기 위해 사용한 방법은, 딕셔너리(자바의 hash와 비슷한 파이썬의 자료구조), 이분탐색(BinarySearch)를 이용했습니다. ..

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 예를 들어, A = {10, 20, 10, 30, 20, 50} 인 경우 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이다. 풀이 과정 먼저, 풀이과정 두가지를 이용할 수 있는데, 하나는 이진탐색을 직접 구현하여 수열이 들어갈 자리를 찾는 방법이고 다른 하나는 내장 모듈인 bisect를 이용한 방법이다. 먼저 풀..

www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 설명 이 문제에서 A라는 배열의 각 칸에는 다음과 같이 자기 인덱스의 곱을 담고있다. ( 즉 N[2][3] = 2*3 ) 1 2 3 2 4 6 3 6 9 이러한 배열을 B라는 1차원 배열에 오름차순으로 나타내었을 때, k번째 인덱스에는 어떤 수가 있는지를 출력하는 문제이다. 풀이 과정 처음에는 N*N크기의 1차원 배열을 만들어 for문을 이용해 1*1부터 N*N까지의 수를 모..

www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 지난번에 풀었던 10815번 숫자카드 1 문제의 상위 호환 문제이다. 숫자카드1 문제의 경우 이진탐색을 하여 찾고자 하는 숫자가 있으면 단순히 1을 출력하는 문제였다면, 이 문제는 찾고자 하는 숫자의 개수까지 구해야 한다. 처음에는 숫자카드 1처럼 이진탐색을 한 후에 찾은 숫자는 리스트에서 제외를 해주고 다시 이진탐색을 추가하는 식으로 해서 개수를 구했는데, 이진탐색임에도 불구..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제는 내가 현재 가지고 있는 서로 다른 길이의 랜선들을 잘라서 동일한 길이의 새로운 랜선을 여러개 만드는 것이다. 내가 가지고 있는 랜선의 개수 K와 새로 만들 랜선의 개수 N을 입력받는다. 예를 들어 K=4, N=11 이라면 4개의 긴 랜선을 잘라 11개의 짧은 랜선을 만드는 것이다. 이 때, 11개를 만들 수 있는 랜선의 최대 길이를 구하면 된다. 즉, 11개를 ..

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 문제에 대한 자세한 설명은 위 링크에 기술 되어있다. 쉽게 풀어쓰자면 동굴의 길이(N)와 높이(H)를 입력받는다. 동굴은 석순과 종유석으로 구성되어 있는데, 석순은 아래에서 자라는 고드름 종유석은 천장에서 나는 고드름이라고 생각하면 된다. 문제에서 동굴의 길이만큼 석순과 종유석의 길이를 입력받는데, 번갈아 가면서 입력받는다. ( 석순과 종유석은 각각 동굴의 길이 1만큼 차지한다) 예를 들어, 1 3 ..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이 문제는 내가 입력한 숫자들이 상근이가 가지고 있는 숫자들에 존재하는지 확인하는 문제이다. 변수 n은 상근이의 숫자 카드 개수, card 는 그 카드들의 숫자 목록이다. m은 내 카드 개수, check는 내 카드들의 숫자 목록이다. 즉 check의 요소들이 card에 존재 하는가를 검사 하면 된다. 이렇게 요소들을 확인하는 문제는 이진탐색(Binary Search)..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제에서 주어진 대로, N개의 집에 C개의 공유기를 설치한다. 이 때, 가장 인접한 두 공유기 사이의 거리가 최대 가 되도록 해야 한다. 즉, 집의 좌표가 [ 1, 2, 4, 8, 9 ] 이고 공유기를 3개 설치 할 때, 공유기를 1, 4, 8 혹은 1, 4, 9 에 설치를 해야 가장 인접한 두 공유기 사이의 거리(1, 4)가 3이 되고, 이 3..

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 어렸을 때 해봤던 '뿌요뿌요' 게임을 구현한다고 생각하면 될 것 같다. 코드의 풀이 방식은 다음과 같다. 1. 맵(graph)을 돌면서 '.'이 아닌 것(뿌요)을 발견하면 BFS를 실행한다. 2. BFS로 진입하여 현재 터뜨릴 수 있는 뿌요를 모두 터뜨려 준다. 3. 뿌요가 터졌기 때문에 맵을 한번 정리해준다(gravity) 4. 터뜨릴 수 있는 뿌요가 계속 남아있을 때 ..