본문 바로가기

PS78

[SWEA] 4014. 활주로 건설(Python) swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 어렵지 않은 삼성 모의 SW역량테스트 문제였다. 문제 푸는 데 1시간 정도 소요. 가로(행) 탐색, 세로(열)의 모든 케이스를 check_slope 함수에 넣어 가능하면 1, 불가능하면 0 리턴. check_slope () 함수에서 같은 높이이면 cnt += 1 높이 1 높아질 때, 그동안의 쌓아온 거리가 경사로 길이보다 크거나 같다면 가능한 경우이므로 cnt = 1로 초기화 높이 1 낮아질 때, 현재 쌓아온 거.. 2021. 3. 7.
[BOJ] 1759. 암호 만들기(Python) / DFS www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net DFS 알고리즘과 combination 모듈을 활용한 것 두 가지 방법으로 풀어보았다. 물론 조합(Combination)을 구한다는 본질은 같다. 파이썬 풀이는 다음과 같다. 방법 1 - dfs로 comb 함수 구현. 시간은 148ms 소요 import sys input = sys.stdin.readline def comb(depth, k, temp): if depth == L: vowel = 0 for s in t.. 2021. 3. 4.
[BOJ] 2583. 영역 구하기(Python) / BFS www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net # 22분 소요 아주 간단한 BFS 문제 M*N크기 맵 1로 초기화 Input 받은 내용을 미리 M*N크기의 맵에 0으로 그려줌 이후 맵에서 1일 때 연결된 곳 BFS 이용하여 0으로 지워주면서 갯수 셈 연결된 곳 0으로 지우는 작업 끝날 때마다 resut += 1, parts에는 갯수 append 해주고, 마지막 출력할 때 sort 파이썬 코드는 다음과 같다. import sys input.. 2021. 3. 4.
[BOJ] 2485. 가로수(Python) www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3≤N≤100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수 www.acmicpc.net gcd(Greatest Common Devisor) 최대공약수 구하는 함수 이용해서 148ms로 시간 단축 => 통과 파이썬 코드는 다음과 같다. import sys input = sys.stdin.readline from math import gcd n = int(input()) trees = [] gaps = [] for i in range(n): trees.append(int(input())) if i.. 2021. 3. 4.
[BOJ] 9095. 1, 2, 3 더하기(Python) / DP www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 처음에 combination으로 풀려다가 숫자를 자세히 보니 규칙성 발견 => DP로 접근해보자 4번째 수 이후로 이전의 세 수의 합의 값을 가짐. n은 10까지 수를 가지므로 미리 리스트로 만들어놓는다. 인덱스에 해당하는 값을 찾아 간단하게 풀 수 있는 문제. 파이썬 코드는 다음과 같다. import sys input = sys.stdin.readline dp = [1, 2, 4] for i in range(3, 12): dp.append(dp[i-3]+dp[i-2]+dp[i-1]) # print(dp) n.. 2021. 3. 4.
[BOJ] 6588. 골드 바흐의 추측(Python) www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net # 33분 소요 에라토스테네스 체 이용해서 미리 소수 테이블을 만들어 놓는다. 참고(https://wikidocs.net/21638) 이를 만드는 데 시간, 메모리 미리 소요해놓고 답을 구하는 데 걸리는 시간은 최소화한다. 가장 작은 소수인 2부터 두 수가 모두 소수인 가장 빠른 경우 정답 리턴 파이썬 코드는 다음과 같다. import sys input = sys.stdin.readlin.. 2021. 3. 4.

티스토리툴바