'📂코딩테스트:CodingTest' 카테고리의 글 목록 (7 Page)

[백준 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를 ..

📂코딩테스트:CodingTest

[백준 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과 같..

📂코딩테스트:CodingTest

[백준 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 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다...

📂코딩테스트:CodingTest

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

2023.06.20

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

📂코딩테스트:CodingTest

[백준 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(), 커서를 오른쪽..

📂코딩테스트:CodingTest

[백준 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부터 순서를 부여하면 된다. 처음..

📂코딩테스트:CodingTest

[백준 2108번-파이썬]통계학

2023.06.20

백준 (BOJ) 11729번 https://www.acmicpc.net/problem/2108 사용언어 : PYTHON 1.문제 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. 2.풀이 최빈값을 구하는 것이 문제였는데, 파이썬의 내장 함수인 Collection모듈의 Counter을 사용하여 해결..

📂코딩테스트:CodingTest

[백준 1181번-파이썬]단어 정렬

2023.06.19

백준 (BOJ) 11729번 https://www.acmicpc.net/problem/1181 사용언어 : PYTHON 1.문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 1.길이가 짧은 것부터 2.길이가 같으면 사전 순으로 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 2.풀이 중복 제거는 set함수를 사용하여 제거하고, 정렬은 sort함수를 사용하여 정렬하였다. 이때 상위 조건 A과 하위 조건 B가 있는경우, B로 먼저 정렬 한 후에 A로 정렬해야 한다. 여기선 A가 길이가 짧은 것부터, B가 길이가 같으면 사전 순으로 이다. 따라서 사전 순으로 정렬하고 길이가 짧은 순으로 정렬해..

티스토리툴바