네발로 코딩하는 포메라니안

1. 문제 https://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 2. 풀이 과정 n이 5이고 검사하는 값을 mid = 6이라고 할 때, 6보다 작거나 같은 값의 수는 아래와 같다. 1*1, 1*2, 1*3, 1*4, 1*5 2*1, 2*2, 2*3, 2*4 ,2*5 3*1, 3*2, 3*3, 3*4, 3*5 4*1, 4*2, 4*3, 4*4, 4*5 5*1, 5*2, 5*3, 5*4, 5*5 각 행에서 6보다 작은 값의..

1. 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 2. 풀이과정 입력된 값을 하나씩 읽어가면서, 결과 배열에 들어갈 위치를 이진탐색을 통해 찾는다. #입력 : 10 20 15 30 70 50 10 10 20 10 15 10 15 30 10 15 30 70 10 15 30 50 결과 배열의 마지막 값보다 크면 제일 뒤에 추가하고, 아니면 자기보다 작은 값들의 뒷자리를 차지하도록 만든다. 방법 1) 이진탐색 구현 import sys inp..

1. 문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 2. 풀이 과정 방법 1) 다음 코드에서는 사전 자료형을 사용하였다. - 이진탐색을 시도했으나 시간 초과로 실패하였다. 하나의 값을 찾을 땐 효율적이지만, 다수의 값을 찾고 그 값들이 중복 가능할 때는 특정 값의 개수를 저장해놓고 꺼내서 출력하는 것이 더 빠르다. import sys input = sys.stdin.readline n = int(inpu..

1. 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 2. 풀이 과정 방법 1) 자신의 앞에 있는 값들 중 자신과 작으면서 길이가 최대인 값에 1을 더한 값이 자신이 최대가 될 수 있는 값이다. n = int(input()) arr = list(map(int, input().split())) result = [0]*(n) result[0] = 1 for i in..

1. 문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2. 풀이 과정 피보나치 수열이 사용되는데, 이유는 아래 그림을 참고하길 바란다. n= int(input()) def case_count(n): if n

1. 문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 2. 풀이과정 방법 1) DFS 이용 - Python 시간 초과, PyPy로 제출 import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [input() for _ in range(n)] visited = [False]*26 dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] r..

1. 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 2. 풀이 과정 필요한 개념 : 조합, BFS 3개의 벽을 어디 세울지에 대해 조합을 사용하고, virus가 퍼지는 과정을 BFS를 통해 수행한다. 방법1) 재귀를 이용한 조합 import sys, copy, collections input = sys.stdin.readline n, m = map(int, input().split()) dx = [-1, 0, 1, 0] dy = [0, 1, 0, -..

1. 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 풀이 과정 import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] q = deque() graph = [] for i in range(m): graph.append(list(..

1. 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 2. 풀이 과정 방법1) deque 라이브러리 활용하기 from collections import deque n, m = map(int, input().split()) miro = [list(map(int, input())) for _ in range(n)] dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] #BFS => 최단 거리 def bfs(graph): q = deque() q.append((..

1. 문제 https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 2. 풀이 과정 1~n까지의 합 = n(n+1)/2 이므로 n(n+1)/2 ≤ (입력값)을 만족하는 n의 최댓값을 구하면 된다. n(n+1)/2 ≤ (입력값) => n(n+1) ≤ 2*(입력값)이다.여기서 n(n+1)은 n*n < n(n+1) < (n+1)(n+1)을 만족한다. 모든 항에 루트를 씌우면, n < ${(n(n+1))}^.5$ < n+1이 된다. int형으로 바꾸면 소수점을 버리니 n을 반환할 수 있으며, ${(n(n+1))}^.5$ ≤ 2*(입력값)이므로 n+1을 반환할 수도 있다. 따라서..