본문 바로가기

PS(Problem Solving)221

[프로그래머스] 코딩테스트 연습 - 같은 숫자는 싫어 (Python) 문제 및 풀이 문제) 프로그래머스 - 구현 - 같은 숫자는 싫어 https://school.programmers.co.kr/learn/courses/30/lessons/12906 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이) 리스트 내에 연속적으로 중복되는 숫자들을 제거하는 문제였습니다. 파이썬 리스트의 마지막 인덱스([-1])을 이용하여 비교해가면 해결할 수 있습니다. 2022. 8. 19.
[프로그래머스] 2020 카카오 인턴십 - 키패드 누르기 (파이썬) 문제 및 풀이 문제) 프로그래머스 - 2020 카카오 인턴십 - 키패드 누르기 https://school.programmers.co.kr/learn/courses/30/lessons/67256?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이) 키 패드 구현과 분기 처리를 통해 쉽게 해결할 수 있는 문제입니다. 키패드를 Dictionary 자료형을 통해 key_pad에 저장합니다. 함수 내에서는 두 엄지손가락의 현재 위치를 추적하고, 숫자를 입력할 때마다 두 손 중 어떤 손을 사용해야 하는지 결정합니다. 이 함수는 숫자 배열 number.. 2022. 8. 6.
[프로그래머스] 2022 카카오 공채 - 신고 결과 받기 (파이썬) 문제 및 풀이 문제) 프로그래머스 - 2022 카카오 공채 - 신고 결과 받기 https://school.programmers.co.kr/learn/courses/30/lessons/92334 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이) K번 이상 신고 당한 유저를 신고 성공한 횟수의 리스트 배열을 return하는 문제였습니다. 오랜만에 풀다보니(특히 Python) 전에 자주 사용했던 Dictionary나 List에만 의존했습니다. 그러다보니 정답에서 index 처리를 위한 자료형이 계속 추가되었습니다. 아래는 프로그래머스에 나온 다른 사람 풀이 중 하나입니다.. 2022. 8. 4.
[백준] 14889번 - 스타트와 링크 (Python) 문제 및 풀이 문제) 백준 - 완전 탐색 - 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 최대 인원 수가 20명이므로 완전 탐색으로 해결할 수 있습니다. Python의 Combination을 활용하여 팀을 나눕니다. 나눈 팀의 능력치 차이의 최솟값을 구하여 해결할 수 있습니다. Python 소스코드) 2022. 4. 3.
[백준] 2250번 - 트리의 높이와 너비 (C++) 문제 및 풀이 문제) 백준 - 트리 - 트리의 높이와 너비 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 트리의 중위 선회를 통해 해방 레벨에서의 최소 idx와 최대 idx를 memo 합니다. 그 후, 1부터 N까지 너비의 최댓값을 찾아 출력합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/2250_%ED%8A%B8%EB%A6%A.. 2022. 3. 18.
[백준] 13302번 - 리조트 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 리조트 https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 날짜와 쿠폰의 개수를 memoization하여 문제를 해결합니다. 쿠폰, 하루권, 3일권, 5일권을 각각 사용할 경우의 최소비용을 구합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/13302_%EB%A6%AC%EC%A1%B0%ED%8A%B8.cpp GitH.. 2022. 3. 18.
[백준] 2075번 - N번째 큰 수 (C++) 문제 및 풀이 문제) 백준 - 우선수위 큐 - N번째 큰 수 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net N * N개의 모든 수를 저장하고 정렬해서 N번째 큰 수를 구하기에는 메모리 제한이 12MB이기에 불가능합니다. 대부분의 정렬 문제는 우선순위 큐로 해결할 수 있습니다. 우선순위 큐를 최소 힙으로 사용하여 문제를 해결했습니다. Input을 최소 힙에 push 하면서 최소 힙이 N개가 되게 유지합니다. 그 후, top을 출력하면 해답을 구할 수 있습니다. C+.. 2022. 3. 17.
[백준] 9935번 - 문자열 폭발 (C++) 문제 및 풀이 문제) 백준 - 문자열 - 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net ans에 문자열을 더하면서 폭발 문자열의 끝과 확인하여 만약 같을 경우 폭발 문자열 전체를 확인하여 같을 경우 pop 합니다. C++ 소스코드) 2022. 3. 17.
[백준] 1613번 - 역사 (C++) 문제 및 풀이 문제) 백준 - 플로이드 와샬 - 역사 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 전/후 관계가 있는 역사 사건들이 주어질 때, 임의의 두 사건의 전/후 관계를 구하는 문제였습니다. 사건의 개수가 최대 400이므로 플루이드 와샬 알고리즘(O(N^3))으로 해결할 수 있습니다. >, < 관계를 1, -1로 저장하여 같은 전/후 관계끼리만 비교가 가능하므로 update 합니다. C++ 소스코드) 2022. 3. 16.
반응형

티스토리툴바