파이썬53 [백준] 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. [백준] 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. [프로그래머스] 2021 카카오 공채 - 메뉴 리뉴얼 (파이썬) 문제 및 풀이 문제) 프로그래머스 - 2021 카카오 공채 - 메뉴 리뉴얼 -> programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr ① 나의 풀이 orders 배열에 저장된 단품 메뉴에서 코스 메뉴로 정할 수 있는 모든 조합을 구한다. 이때, 조합을 구해 그 조합의 길이가 course 배열에 들어 있다면 딕셔너리(possible)에 추가한다. 딕셔너리에서 우리는 코스 메뉴의 길이별로 최대를 구해야 한다. 따라서 배열의 인덱스를 course의 .. 2021. 2. 6. [백준] 1195번 - 킥다운 (파이썬) 문제 및 풀이 문제) 백준 - 구현(Implementation) - 킥다운 -> www.acmicpc.net/problem/1195 1195번: 킥다운 첫 줄에는 첫 번째 기어 파트를 나타내는 1과 2로 구성된 문자열이 주어진다. 두 번째 줄에는 마찬가지로 두 번째 기어 파트를 나타내는 1, 2로 구성된 문자열이 주어진다. 여기서 1은 홈을, 2는 www.acmicpc.net 입력 첫 줄에는 첫 번째 기어 파트, 두 번째 줄에는 두 번째 기어 파트가 1,2로 구성된 문자열이 주어진다. 1은 홈(들어간 부분), 2는 이(튀어나온 부분)를 의미한다. 먼저 너비를 구하기 전에 어떤 경우에 기어가 맞물릴 수 있는지 알아보자. ①: 짧은 기어 파트가 1이고 긴 기어 파트가 2일 때, 서로 맞물려 기어를 끼울 수 있다. ②: 긴.. 2021. 2. 3. [프로그래머스] 2021 카카오 공채 - 신규 아이디 추천 (파이썬) 문제 및 풀이 문제) 프로그래머스 - 2021 카카오 공채 - 신규 아이디 추천 -> programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 카카오계정개발팀에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. 네오에게 주어진 첫 업무는 새로 가 programmers.co.kr ① 나의 풀이 아무 생각 없이 (빡?) 구현했다. 모든 단계를 주어진 new_id를 이용해 처리했다. 1단계: 대문자를 소문자로 치환하는 것이므로 lower() 메서드를 이용해 쉽게 해결했다. 2단계: 알파벳(isalpha()), 숫자(isdigit()), 특수 문자를 확인하며 그것이 아닐 경우 슬라이.. 2021. 2. 3. [백준] 12904번 - A와 B (파이썬) 문제 및 풀이 문제) 백준 - 그리디 알고리즘(Greedy) - A와 B -> www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문자열 S를 T로 바꾸는데 연산이 두 가지인데, 이를 반대 관점에서 해석하여 문제를 풀려고 한다. ① S → T 문자열의 뒤에서 A를 추가한다. 문자열을 뒤집고 뒤에 B를 추가한다. ▼ ② T → S 문자열의 뒤에서 A를 제거한다. 문자열의 뒤에서 B를 제거하고 문자열을 뒤집는다. ① 관점에서 답을 구현하기 위.. 2021. 1. 31. 이전 1 ··· 3 4 5 6 다음 반응형
