알고리즘 문제풀이
-
[프로그래머스/Level 3] 순위 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 15. 14:11
programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 플로이드 와샬을 이용하는 문제였습니다. 해당 알고리즘을 이용하여 모든 정점에서 다른 정점으로 갈 수 있는 여부(경기 결과를 알 수 있는지)를 확인합니다. 예를들어 a->b이고 b->c이면 a->c 가 된다는 것을 의미합니다. n = 5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 가 입력값으로 주어졌을 때, 플로이드 워셜을 이용하면 다음과 같이 배열이 완성됩니다. 출/도 1 2 3 4 5 1 false true false false true 2 fals..
-
[백준/BOJ] 9251번 LCS (C++)알고리즘 문제풀이/백준 2021. 2. 14. 20:44
www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 새롭게 알게된 점 LCS의 개념을 알게됨 DP 유형의 문제, 위의 링크를 참고하여 해결했습니다. #include using namespace std; int dp[1001][1001]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); string s1, s2; cin >> s1 >> s2; for(int..
-
[백준/BOJ] 14502번 연구소 (C++)알고리즘 문제풀이/백준 2021. 2. 10. 14:34
www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 삼성 역량 테스트 기출 문제 : DFS + BFS 벽을 3개씩 세우는 모든 경우의 수는 DFS를 통해 구현하고, 이렇게 세워진 벽에서 바이러스가 퍼져나갔을 때 안전영역의 최대 개수는 BFS를 통해 구하도록 구현하였습니다. #include #include #include using namespace std; int n, m, answer; int map[9][9]; int dx[4] = {-1, 0, 1, 0}; int dy..
-
[프로그래머스/Level 3] 이중우선순위큐 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 10. 13:51
programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 최소 힙과 최대 힙 두개를 이용하여 구현하였습니다. 구현은 두개의 힙을 이용했지만, 실제로는 하나의 힙을 이용하는 것이므로, 현재 남은 원소의 개수를 기록할 cnt 변수를 두는 것이 핵심이었습니다. #include #include #include #include using namespace std; vector solution(vector operations) { vector answer; int cnt = 0; priority_queue minPq; // 최소 힙 priority_queue maxPq; // 최대 힙 for(auto o : operat..
-
[백준/BOJ] 16948번 데스 나이트 (C++)알고리즘 문제풀이/백준 2021. 2. 9. 21:56
www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net BFS를 통해 해결할 수 있는 간단한 문제였습니다. #include #include #include using namespace std; int n, r1, c1, r2, c2; int map[201][201]; int dx[6] = {-2, -2, 0, 0, 2, 2}; int dy[6] = {-1, 1, -2, 2, -1, 1};..
-
[프로그래머스/Level 3] 디스크 컨트롤러 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 9. 17:45
programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 우선순위 큐를 이용하여 비선점 SJF 스케줄링을 구현하는 문제였습니다. #include #include #include #include #include using namespace std; int solution(vector jobs) { int answer = 0, idx = 0, time = 0; // idx : jobs의 인덱스, time : 현재 실행시간 // 작..
-
[LeetCode/easy] Single Number (C++)알고리즘 문제풀이/LeetCode 2021. 2. 8. 23:17
leetcode.com/problems/single-number/ 먼저 hash를 이용한 풀이입니다. unordered_map을 선언하여 key는 수, value는 빈도 수를 저장합니다. iterator로 map을 탐색하면서 value 값이 1인 key를 리턴하면 해결할 수 있습니다. class Solution { public: int singleNumber(vector& nums) { unordered_map um; for(auto n : nums) { um[n]++; } for(auto it = um.begin(); it != um.end(); it++) { if(it -> second == 1) { return it -> first; } } return 0; } }; 다음은 bit 연산을 이용한 풀..
-
[백준/BOJ] 16928번 뱀과 사다리 게임 (C++)알고리즘 문제풀이/백준 2021. 2. 8. 22:51
www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net BFS 유형의 문제입니다. 뱀과 사다리 부분의 구현이 추가된 것 빼고는 숨바꼭질 2와 비슷해서 쉽게 해결했습니다. #include #include using namespace std; int n, m; int map[101]; bool visit[101]; vector r, s; int dx[6] = {1, 2, 3, 4, 5, 6}; int snakeOrLadde..