본문 바로가기

Algorithm(알고리즘)/BOJ(백준) 문제풀이64

백준 2751번 파이썬 | 수 정렬하기 2 | Sort 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 풀이 해당 문제는 시간 초과를 내면 안되므로 O(nlogn)으로 풀면 된다. 파이썬 내장함수가 O(nlogn)이기에 사용했지만 에러가 떳다.. 방법은 총 3가지이다. 첫번째 방법은 파이썬 내장함수 sorted를 사용하고 python3을 pypy3으로 바꾸는것. 두번째 방법은 input을 sys.stdin.readline()으로 받는 것... 2020. 9. 28.
백준 1920번 파이썬 | 수 찾기 | binary search(이분 탐색) www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이.. 2020. 9. 26.
백준 10994번 파이썬 | 별 찍기 -19 | 재귀함수 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 출력 첫째 줄부터 차례대로 별을 출력한다. 풀이 n에 따라서 (4*n -3) 만큼의 칸수들이 생기며 테두리를 감싸고 있는 것들의 내부에는 똑같은 것들이 반복된다. 따라서 recursion으로 n을 1씩 줄이면서 x,y좌표의 값들을 2씩 더해준 후 재귀함수로 풀면 쉽게 풀 수 있다. (처음에 이 로직을 생각하는 것이 익숙하지 않을 수도 있으니 연습하자..) def draw(n, idx): if n == 1: starMap[idx][idx] = '*' return ; l = 4 * n -3 for i in range(idx, l+idx): #위 아래 starMap[idx][i] = '*' star.. 2020. 9. 22.
백준 1063번 파이썬 | 킹 | 시물레이션 문제 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 행을 상징한다. 열은 가장 왼쪽 열이 A이고, 가장 오른쪽 열이 H까지 이고, 행은 가장 아래가 1이고 가장 위가 8이다. 예를 들어, 왼쪽 아래 코너는 A1이고, 그 오른쪽 칸은 B1이다. 킹은 다음과 같이 움직일 수 있다. R : 한 칸 오른쪽으로 L : 한 칸 왼쪽으로 B : 한 칸 아래로 T : 한 칸 위로 RT : 오른쪽 위 대각선으로 LT : 왼쪽 위 대각선으로 RB : 오른쪽 아래 대각선으로 LB : 왼쪽 아래 대각선으로 체스판에는 돌이 하나 있는데, 돌과 같은 곳으로 이동할 때는, 돌을 킹이 움직.. 2020. 9. 18.

티스토리툴바