본문 바로가기

알고리즘문제7

[프로그래머스]조이스틱 C++ 문제풀이, 그리디 알고리즘(Greedy) 코딩테스트 연습 - 조이스틱 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 이 문제에서 제일 어려웠던 부분은 문제를 이해하는 것이었다. 처음에는 전부 'A' 로 세팅되어있는 문자열을 가지고 있다. 그리고 이 문자열을 인자로 들어오는 문자열로 바꿔야하는데 그 최소 횟수를 구하는 것. a -> b -> c -> d .... z 반대로 a -> z -> y -> x 이런식으로도 갈 수 있다. 그리고 문자는 대문자만 사용한다는 조건이 있으니 대놓고 아스키 코드를 이용하라는 문제이다. 아스키 코드.. 2021. 2. 4.
[프로그래머스]베스트앨범 C++문제풀이(map활용) [프로그래머스]베스트앨범 C++문제풀이(map활용) https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr bool cmp(const pair &a, const pair &b) { return a.second.first > b.second.first; } vector solution(vector genres, vector plays) { vector answer; // unordered_mapm_map; //uno.. 2020. 10. 26.
[프로그래머스]카펫 문제 풀이C++ (완전탐색, 약수 구하기) https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr [프로그래머스]카펫 문제 풀이C++ (완전탐색, 약수 구하기) 제한사항 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다. 카펫의 가로길이는 세로 길이와 같거나, 세로 길이보다 깁니다. 입출력 예 brown yellow return 10 2 [4, 3] 8 1 .. 2020. 10. 25.
[백준 14502번]연구소 with 삼성전자 SW역량테스트 문제 [백준 14502번]연구소 with 삼성전자 SW역량테스트 문제 BFS/Brute force https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 배열이 주어지고 0은 빈 칸, 1은 벽, 2는 바이러스이고 바이러스는 인접한 배열(빈 캰)로 전염된다. 벽은 3개를 만들 수 있고 이 때 바이러스가 전염되지 않는 빈칸의 최대 개수를 출력해라 구현 아이디어 이 문제는 벽 3개가 설치되는 모든 경우의 수를 체크해야한다. 주어진 배열의 크기가 3 2020. 10. 10.
[백준 1463번]다이나믹 프로그래밍 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net #include using namespace std; int DP[1000001] = { 0 }; int Solve(int v) { int t = DP[v - 1]; if (v % 3 == 0) { if (DP[v / 3] < t) t = DP[v / 3]; } if (v % 2 == 0) { if (DP[v / 2] < t) t = DP[v / 2]; } return t + 1; } int main() { DP[2] = 1; DP[3] = 1; for (int i = 4; i < sizeof(DP)/4; i+.. 2020. 9. 3.
[백준 9095번]다이나믹 프로그래밍 1,2,3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net www.youtube.com/watch?v=R9WCxrPs2b8 규칙을 찾아내면 무척 간단한 문제다. 물론 나는 다이나믹 프로그래밍을 이제야 공부하기 시작해서 나에겐 쉽지 않은 문제였다. 우선 규칙을 찾으려는 방향성은 올바르게 갔다. 이 문제는 n 값이 11로 제한되어있어 메모제이션 방식을 사용하지 않고 재귀를 통한 완전탐색으로도 충분히 풀리는 문제이다. 너무 대충 끄적거린거라 좀 부끄러운데 뭐 대략 설명해보자면 우선 1,2,3 까지의 수는 미리 구해놔야한다. ex) 1 = 1 , 2 = 2, .. 2020. 8. 30.

티스토리툴바