'🥇코딩테스트:Algorithm' 카테고리의 글 목록 (6 Page)

[백준 1107번-파이썬]리모컨

2023.06.20

백준 (BOJ) 1107 https://www.acmicpc.net/problem/1107 사용언어 : PYTHON 1.문제 2.풀이 2-1. 시도했다가 실패한 풀이 N : 5457 M : 3 고장난 버튼 : [5,7] 이면 입력이 가능한 버튼들은 [0,1,2,3,4,5,6,8,9]이다. 5457의 첫 번째 숫자 5가 없으므로 첫 번째 숫자를 4 혹은 6을 입력하는 것이 최소로 이동할 수 있는 수가 될 것이다. 이 때 4를 입력한 경우는 뒤에 숫자를 최대한 큰 수로 입력해야 하고, 6을 입력한 경우는 최대한 작은수를 입력해야 한다고 생각하여 문제를 풀고자 했다. 2-2. 올바른 풀이 브루트포스 알고리즘 0 ~ 999899+1 까지 리모컨으로 입력할 수 있는 모든 숫자들을 비교하며 최솟값을 찾는다. N의 ..

🥇코딩테스트:Algorithm

[백준 11053번-파이썬]가장 긴 증가하는 부분 수열

2023.06.20

백준 (BOJ) 11053번 https://www.acmicpc.net/problem/11053 사용언어 : PYTHON 1.문제 2.풀이 A={10,20,10,30,20,50}을 예로 들어 생각해보았다. dp[i] = A[0], A[1], ... A[i] 일때 '증가하는 부분 수열'에서 A[i]의 위치(인덱스)값 이다. i=0 일 때 dp[0]는 A[0] 즉 10의 '증가하는 부분 수열'={10} 에서 위치 즉 1 이다. i=1 일 때 dp[1]는 A[1] 즉 20의 '증가하는 부분 수열'={10,20} 에서 위치 즉 2 이다. i=2 일 때 dp[2]는 A[2] 즉 10의 '증가하는 부분 수열'={10,20} 에서 위치 즉 1 이다. i=3 일..

🥇코딩테스트:Algorithm

[백준 11052번-파이썬]카드 구매하기

2023.06.20

백준 (BOJ) 11052번 https://www.acmicpc.net/problem/11052 사용언어 : PYTHON 1.문제 2.풀이 최적해(최댓값)을 구하는 문제이므로 다이나믹 프로그래밍을 사용하여 풀 수 있었다. 최적해의 일부분이 그 부분에 대한 최적해가 DP 순환식을 세우는 출발점임을 생각했다. N이 4이고 P1=1, P2=5, P3=6, P4=7인 경우 최댓값 = max(P4를 선택하지 않은 경우, P4를 선택한 경우)이다. 이때 P4를 선택하면 N의 갯수를 모두 채우기 때문에 P4하나만 살 수 있다. 따라서 max{(P1,P2,P3)의 조합을 이용해서 4를 만들 수 있는 최댓값, 7}이 된다. 위 최적해의 일부분 (P1,P2,P3)의 조합을 이용해서 4를 만들 수 있는 최댓값 = (P3를 ..

🥇코딩테스트:Algorithm

[백준 1463번-파이썬]1로 만들기

2023.06.20

백준 (BOJ) 1463번 https://www.acmicpc.net/problem/1463 사용언어 : PYTHON 1.문제 2.풀이 다이나믹 프로그래밍 (Bottom up) 방식으로 풀어야 했다. 2-1.순환식을 세우기 순환식을 세우는 사고의 출발점은 '최적해의 일부분이 그 부분에 대한 최적해인가?' 라고 배웠다. 정수 N을 1로 만드는 최소 횟수를 구하는 함수를 D(N)이라고 하자. 최적해를 생각해보면 다음과 같다. D(10)은 10을 2로 나눈 D(5)와, 10에서 1을 뺀 D(9)중 더 작은 값 + 2로 나누거나 1을 뺀 연산횟수 1과 같다. D(12)는 12를 3으로 나눈 D(4)와, 12를 2로 나눈 D(5), 12에서 1을 뺀 D(11) 중 더 작은값 + 연산의 횟수 1과 같..

🥇코딩테스트:Algorithm

[백준 6588번-파이썬]골드바흐의 추측

2023.06.20

백준 (BOJ) 6588번 https://www.acmicpc.net/problem/6588 사용언어 : PYTHON 1.문제 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다...

🥇코딩테스트:Algorithm

[백준 17298번-파이썬]오큰수

2023.06.20

백준 (BOJ) 17298번 https://www.acmicpc.net/problem/17298 사용언어 : PYTHON 1.문제 2.풀이 시간제한이 1초이기 때문에 중첩 반복문으로 풀게되면 시간초과가 나올것 같아서 스택을 사용하여 풀어야겠다고 생각했다. 처음에는 큰 수에 생각이 사로 잡혀서 스택에 가장 큰 값을 유지하면 안될까? 라는 생각을 계속하였다. 1시간 정도 고민해보다 도저히 안될것 같아서 다른분들의 풀이를 검색하였다. 검색을 통해 알게된 아이디어는 다음과 같다. 스택에 수열의 가장 큰 값을 유지하는 것이 아닌, 스택의 제일 윗 값보다 큰 값이 나올때 까지 수열의 값들을 차례대로 쌓는 것이었다. 그러다가 스택의 제일 위의 값보다 큰 수열의 값이 나오면 그 수는 스택 제일 윗 값의 오큰수가 된다...

🥇코딩테스트:Algorithm

[백준 1406번-파이썬]에디터

2023.06.20

백준 (BOJ) 1406번 https://www.acmicpc.net/problem/1406 사용언어 : PYTHON 1.문제 2.풀이 시간복잡도를 고려해야하는 문제였다. 처음에는 현재 커서의 위치를 저장하는 cursor변수와, 리스트의 insert, del 메소드를 사용했는데 이렇게 하니 시간초과가 발생했다. 두 메소드의 시간복잡도가 O(n)이고, 이것을 m번 반복하기 때문이었다. 이 시간초과 문제를 해결하기 위해선 시간복잡도가 O(1)인 pop()과 append()연산을 사용해야 했다. 그리고 cusor변수를 두 개의 리스트를 사용해서 구현할 수 있었다. 커서를 기준으로 리스트 st와 tmp_st로 나누었다. 커서를 왼쪽으로 옮기면 st에서 pop()하여 tmp_st에 append(), 커서를 오른쪽..

🥇코딩테스트:Algorithm

[백준 18870번-파이썬]좌표압축

2023.06.20

백준 (BOJ) 18870번 https://www.acmicpc.net/problem/18870 사용언어 : PYTHON 1.문제 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 즉 [2,10,15,1,1] 라는 데이터가 있으면 값의 대소관계만 고려한 데이터로 변환하라는 것이다. (위 예시의 정답 : [1,2,3,0,0]) 2.풀이 각 원소의 중복을 제거하고 정렬 한 다음, 각 값에 0부터 순서를 부여하면 된다. 처음..

티스토리툴바