본문 바로가기

Algorithm77

[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.
[Programmers] 큰 수 만들기(Python) / Greedy programmers.co.kr/learn/courses/30/lessons/42883?language=python3 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 난 개인적으로 어려웠던 문제다. Greedy 알고리즘은 뭔가.. 쉽고도 어려운 알고리즘이다. stack 으로 구현한 Greedy한 풀이.. 어려워서 다른 사람 풀이를 참고했다. stack에 값이 있고, k가 남아있다면 stack의 마지막 값과 현재 value를 비교해 value가 크다면 k를 사용하며 stack의 마지막 값을 빼준다. 앞에서부터 탐색하며 비교해주기 때문에 k를 다 써버린다면 뒷 부분은 사실 그리디하게 풀 수 없기 때문에 최적해가 아닌 경우가 발생할 수 있겠다. 그리디의 약점이 무조건 최적해를 보장하지는 않는.. 2021. 2. 26.
[BOJ] 2468. 안전 영역(Python) / BFS www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 어렵지 않은 BFS 문제였다. 실제로 난이도 실버1. 기본적인 BFS 틀에 조건만 이동할 위치를 현재 비의 양과 비교해 더 높을 때마다 BFS를 확장시켰다. 이 때, 비의 양이 달라질 때마다 경우가 달라지므로 나름의 아이디어를 내서 visited를 재활용하기 위해 새로 방문 표시를 할 때는 현재 비의 양으로 표현해 비의 양이 다른 경우와 구분했다. 비의 양을 결정한 후 결과(안전영역의 갯수, temp)가 나올 때마다 .. 2021. 2. 25.
[SWEA] 1953. 탈주범 검거 (Python) / BFS swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 5번째 풀어보는 문제라 거의 외우다시피 한 문제다. 풀 때마다 조금씩 아이디어가 달라지긴 하지만 큰 틀은 바뀌지 않는다. 깔끔한 BFS 문제로 pass까지 42분 소요했다. 터널 1~7가지 종류를 각각 상하좌우로 뚫려있는지 여부를 0, 1로 미리 마스킹해두어 현 위치에서 나갈 수 있고, 이동할 위치에서 들어올 수 있는지 확인하며 bfs를 탈주범이 갈 수 있는 위치를 확장했다. 고려해야 할 부분이라면, bfs 함수.. 2021. 2. 25.

티스토리툴바