본문 바로가기

PS(Problem Solving)221

[백준] 4386번 - 별자리 만들기 (C++) 문제 및 풀이 문제) 백준 - 최소 스패닝 트리 - 별자리 만들기 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 별자리를 이어 최소 비용으로 모두를 연결되게 만드는 문제였습니다. 모두가 연결되어야하고 최소 비용을 사용해야되므로 최소 스패닝 알고리즘으로 쉽게 해결할 수 있었습니다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/4386.. 2021. 12. 12.
[백준] 9019번 - DSLR (Python) 문제 및 풀이 문제) 백준 - BFS - DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 만들 수 있는 수 중에서 최소 명령을 사용하는 것을 탐색하는 문제였습니다. BFS로 탐색하면서 queue에 (숫자, 명령어)를 넣고 명령어를 만들 수 있는 모든 경우의 수(D, S, L, R)를 탐색했습니다. 파이썬 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Pr.. 2021. 12. 10.
[백준] 1647번 - 도시 분할 계획 (C++) 문제 및 풀이 문제) 백준 - 최소 스패닝 트리 - 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/1647_%EB%8F%84%EC%8B%9C%20%EB%B6%84%ED%95%A0%20%EA%B3%84%ED%9A%8D.cpp GitHu.. 2021. 12. 9.
[백준] 2467번 - 용액 (C++) 문제 및 풀이 문제) 백준 - 투 포인터 - 용액 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 처음에는 N번의 반복문을 통해 이진 탐색으로 구하려다가 투 포인터를 이용하는게 더 구현하기 쉬워 투 포인터를 사용했습니다. C++ 소스코드) 2021. 12. 8.
[프로그래머스] 코딩테스트 고득점 Kit - 단어 변환 (Python) 문제 및 풀이 문제) 프로그래머스 - BFS - 단어 변환 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 단어별로 개수를 저장하기 위해 파이썬의 자료구조인 딕셔너리를 사용했습니다. 딕셔너리를 모두 0으로 초기화하여 방문 여부를 판단했습니다. BFS를 통해 탐색하면서 target이 나올 때 결괏값을 return 합니다. Python 소스 코드) Full Code) https://g.. 2021. 12. 7.
[프로그래머스] 코딩테스트 고득점 Kit - 네트워크 (C++) 문제 및 풀이 문제) 프로그래머스 - DFS - 네트워크 https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 0번째부터 n번째까지 DFS로 네트워크를 탐색합니다. solution 함수에서 만약 visited하지 않았던 컴퓨터면 새로운 네트워크이므로 answer에 1을 더해줍니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/Programmers/blob/main/%EC%B.. 2021. 12. 7.
[백준] 17298번 - 오큰수 (C++) 문제 및 풀이 문제) 백준 - 자료구조 - 오큰수 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 스택(Stack)을 이용하여 풀이했습니다. 기본적으로 1부터 N까지 순회하면서 스택에 넣습니다. 만약 오큰수가 존재하면 스택에서 pop을 진행하고 answer에 오큰수를 memo합니다. 반복문이 끝났는데도 스택에 숫자가 존재한다면 오큰수가 존재하지 않는 숫자들이기에 -1을 출력하게 합니다. C++ 소스코드) Full Code) https://github.com/Chococ.. 2021. 12. 6.
[프로그래머스] 코딩테스트 고득점 Kit - 주식 가격 (C++) 문제 및 풀이 문제) 프로그래머스 - 자료 구조 - 주식 가격 https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr BOJ 2493번 - 탑과 굉장히 유사한 문제여서 비슷하게 풀었습니다. 이 문제는 스택으로도 풀 수 있지만, Brute Force로도 풀이가 가능해서 효율성 채점에서 더 많은 T.C가 필요해 보입니다. BOJ 2493번 해설 https://chocochip101.tistor.. 2021. 12. 4.
[백준] 2493번 - 탑 (C++) 문제 및 풀이 문제) 백준 - 자료 구조 - 탑 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 스택을 이용해 해결했습니다. 먼저 N부터 1번째까지 스택에 넣어주면서 만약 신호를 받을 수 있는 탑이 들어올 경우 answer에 번호를 적습니다. 반복문이 끝난 후에도 스택에 남아 있는 경우는 신호를 받지 못한 경우이므로, answer에 0으로 저장합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_So.. 2021. 12. 4.
반응형

티스토리툴바