본문 바로가기

알고리즘204

[Python] sort( ), sorted( ), lambda ⊙list.sort() 1. 따로 반환하는 값이 없으므로(None) 새로운 변수 선언이 필요 없다. 2. '리스트명.sort()'와 같은 방법으로 작성한다. 3. key parameter가 None으로 설정되어 있으므로, 문자열 리스트를 문자 길이 순으로 정렬하고 싶다면 list.sort(key=len)으로 작성한다. a = [3, 2, 5, 1, 4] a.sort() print(a) #[1, 2, 3, 4, 5] ⊙sorted(list) 1. 기존에 선언된 리스트 원본을 변화시키지 않는다. 2. 순서대로 정렬한 리스트를 반환하므로 새로운 변수를 선언해야 한다. 3. 'newList = sorted(list)'와 같은 방법으로 작성한다. a = [3, 2, 5, 1, 4] b = sorted(a) pri.. 2021. 2. 27.
[백준] 1043번 - 거짓말 (파이썬) 문제) 백준 - 분리 집합 - 거짓말 -> www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 분리 집합 문제이므로 set() 자료형을 사용하자. 진실을 아는 사람(witness_set)의 번호와 각 party마다(parties) 참가자들을 집합 자료형으로 입력받는다. 각 파티들을 순회하면서 witness_set와 party의 교집합(intersection)이 존재하면 party의 모든 참가자들을 witness에 추가한다. 교집합이 존재하지 않을 경우 과장된 이야기를 할 .. 2021. 2. 24.
[백준] 1068번 - 트리 (파이썬) 문제) 백준 - 그래프 이론/트리 - 트리 -> www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 인접 행렬 방식으로 graph를 False로 초기화한다. 2. 입력으로 들어온 부모 노드들의 정보를 이용해 graph의 연결을 채워주고 root를 선정한다. 3. 세 번째 줄 입력에 나오는 지울 노드의 모든 연결을 끊어준다.(False로 설정) 4. dfs로 root부터 탐색해 리프 노드 개수를 구해준다. 반성) 트리 문제라 생각해서 인접 행렬의 활용과.. 2021. 2. 20.
[백준] 11051번 - 이항 계수 2 (C++ / 파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic programming) - 이항 계수 2 -> www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 주어지는 N과 K가 최대 1000이므로 기본 조합 공식으로 팩토리얼로 구한다면 시간 초과가 날 것이다. 따라서 우리는 동적 계획법을 이용하여 시간을 줄일 것이다. 고등학교 수학 시간에 조합 관련 개념에서 우리는 다음과 같은 수식을 배웠다. (기억이 안난다면, 지금 알아 놓도록 하자.) 이 식을 이용해 우리는 동적 계획법의 수열을 쉽게 새울 수 있다. 우리가 구할 값을 dp[n][k]라 했을 .. 2021. 2. 20.
[백준] 2293번 - 동전 1 (파이썬) 문제) 백준 - 동적 계획법 (Dynamic programming) - 동전 1 -> www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 주어진 동전들을 이용해서 k원을 만드는 방법의 수를 구하는 것이다. 아래 을 보자. dp[k]를 만들 수 있는 경우의 수라 하자. i(화폐가치)가 1일 때 dp[5] = dp[4]이다. 엄밀히 말하면, 현재 dp[5] 값이 0이기 때문에 dp[5] = dp[5] + dp[4]라 볼 수 있다. i(화폐가치)가 2일 때 dp[5] .. 2021. 2. 11.
[백준] 10942번 - 팰린드롬? (파이썬/C++) 문제) 백준 - 동적 계획법 (Dynamic programming) - 팰린드롬? -> www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net dp를 n x n의 2차원 배열로 선언한다. 예를 들어 리스트의 인덱스에 대해 1부터 3까지 팰린드롬이라면, dp[1][3] = True로 설정한다. 즉, 부분 리스트 인덱스의 시작 start와 인덱스의 끝 end를 이용해 검사해 팰린드롬일 경우 dp[start][end]를 True, 아닐 경우 False로 정한다. 팰린드롬의 검사는 검사하려는 부분 리스트의 내부.. 2021. 2. 9.
반응형