Algorithm
-
[hackerrank] Ema's Supercomputer(c++)Algorithm/hackerrank 2020. 10. 22. 23:47
www.hackerrank.com/challenges/two-pluses/problem Ema's Supercomputer | HackerRank Determine the product of the areas of two pluses on a grid. www.hackerrank.com 풀이과정 1. 주어진 그리드 맵에서 그림과 같이 크로스를 2개 그려서 두 크로스의 곱의 최댓값을 구하는 문제이다. 2. BFS를 이용하여 크로스를 그려주었다. 4방향 모두 이동 할 수 있는지 체크를 하고, 한 방향이라도 갈 수 없다면 취소하고 리턴 시켰다. 3. 모든 경우의 수를 체크해줘야 한다. * 현재 위치에서 최대로 9칸 크로스를 그릴 수 있어도, 5칸 크로스의 경우도 따지고 들어가야한다. (곱의 최댓값이다.) 소스..
-
[hackerrank] Climbing the Leaderboard(c++)Algorithm/hackerrank 2020. 10. 21. 23:21
www.hackerrank.com/challenges/climbing-the-leaderboard/problem Climbing the Leaderboard | HackerRank Help Alice track her progress toward the top of the leaderboard! www.hackerrank.com 풀이과정 1. ranked는 내림차순(4,3,2,1)으로 정렬되어 있으며, player는 오름차순(1,2,3,4)이다. 2. 중복값은 같은 등수로 처리되기 때문에 원소에서 제거하고 시작하였다. 3. 꼴등부터 시작하여 현재 Player의 점수보다 현재 랭킹점수가 더 크면 반복문을 종료하여 현재 랭크를 정해준다. 4. player는 오름차순이므로 다음 플레이어는 현재 플레이어보다 등..
-
[HackerRank] Extra Long Factorials(c++)Algorithm/hackerrank 2020. 10. 20. 23:34
www.hackerrank.com/challenges/extra-long-factorials/problem Extra Long Factorials | HackerRank Calculate a very large factorial that doesn't fit in the conventional numeric data types. www.hackerrank.com [문제풀이] 1 ~ 100 사이의 N을 입력받아 해당 N의 팩토리얼 값을 구하는 문제이다. N이 30만 넘어도 c++ 64bit unsigned long long의 최댓값을 넘게 된다. 따라서 배열을 이용하여 각 자리수로 생각하고 접근하여 문제를 해결하였다. [소스코드] 더보기 void extraLongFactorials(int n) { int ..
-
[프로그래머스] 단어 변환Algorithm/Programmers 2020. 10. 17. 18:08
programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제풀이 dfs를 이용하여 현재 단어와 한 개의 알파벳만 차이나는 words를 찾아 이동시킨다. 소스코드 더보기 #include #include using namespace std; int visited[50] = { 0, }; int answer = 987654321; bool checkChangeWord(string s1, str..
-
[프로그래머스] 디스크 컨트롤러Algorithm/Programmers 2020. 10. 17. 17:18
programmers.co.kr/learn/courses/30/lessons/42627?language=cpp 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를�� programmers.co.kr 문제 풀이 1. 처음에는 순열을 이용하여 모든 경우의수로 접근했으나 풀리지 않았다. (문제를 꼼꼼히 읽어봐야한다..) 2. jobs[X][0]은 요청온 시간이며, jobs[X][1]은 작업이 소요되는 시간이다. 3. jobs를 요청 온 시간으로 오름차순으로 정렬한다. 4. 작업량이 적은 순으로 priority_queue를 생성했다. 5. 현재 ..
-
[백준][17136번] 색종이 붙이기(c++)Algorithm/백준 2020. 10. 5. 23:32
www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크�� www.acmicpc.net 풀이과정 (완전탐색) 주어진 종이에 1로 채워진 칸을 주어진 색종이를 이용하여 가장 적은 수로 붙일 수 있는 경우를 구하면 된다. 1. 모든 경우를 따져야한다. 따라서 1로 채워진 칸을 pos 벡터에 담았다. 2. 현재 pos에서 사용 할 수 있는 색종이를 찾아 붙여 나갔다. 사용 된 칸이라면 다음 pos로 넘어간다. 소스코드 더보기 #include #include #include #define M..
-
[백준][17406번] 배열 돌리기 4Algorithm/백준 2020. 10. 4. 17:46
www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이과정 1. 주어진 연산을 모두 한 번씩 이용하였을 때 행의 값이 최솟값이 되는 수를 구하는 문제이다. 2. 완전탐색으로 연산의 순서를 바꿔가면서 모든 경우의 수를 구했다. 3. 연산이 모두 사용되었을 때 최솟값을 구했다. 소스코드(c++) 더보기 #include #include #include #include using namespace std; struct rotation {..
-
[백준][17471번] 게리맨더링Algorithm/백준 2020. 10. 2. 16:51
www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이과정 1. 완전탐색과 BFS를 이용하여 풀었다. 완전탐색을 사용한 이유는 해당 구역마다 선거구가 될 수 있는 두 경우를 체크해야 하기 때문이다. BFS를 사용한 이유는 현재 정해진 선거구역이 모두 연결 된지를 체크하는 과정이 필요했다. 2. 완전탐색을 이용하여 모든 조합의 경우를 구하며 매 조합마다 BFS를 이용하여 구역마다 연결 된지를 체크했다. 소스코드 더보기 #include #include #include #include ..