분류 전체보기
-
[백준/BOJ] 16929번 Two Dots알고리즘 문제풀이/백준 2021. 1. 11. 23:49
www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 브루트 포스(완전 탐색) + DFS 유형의 문제였습니다. (다시 풀기) 문제의 조건에서 싸이클의 의미가 무엇인지 아는게 중요한데, DFS 탐색을 진행하면서 처음 탐색을 시작했던 좌표로 다시 돌아오는 것을 의미합니다. 따라서 시작 좌표로 다시 돌아오기 위해서 종료 조건 체크를 방문 체크 전에 해주어야 합니다. 이때 종료 조건에서 cnt >= 3 이 의미하는 것은 지나온 경로가 최소 3개 이상이여야 한다는..
-
[OS] 교착 상태 (Deadlock)Computer Science/운영체제 2021. 1. 11. 12:06
Deadlock(교착 상태) 두 개 이상의 프로세스가 필요한 자원을 기다리면서 무한정 중지된 상태 Resource Allocation Graph(자원 할당 그래프) Node 프로세스 노드(P1, P2), 자원 노드(R1, R2) Edge Rj → Pi : 자원 Rj이 프로세스 Pi에 할당 됨 Pi → Rj : 프로세스 Pi가 자원 Rj을 요청 중(대기 중) 자원 R2가 프로세스 P1에 할당 되었다. 프로세스 P1이 자원 R2를 요청하고 있다. 자원 R1이 프로세스 P2에 할당 되었다. 프로세스 P2가 자원 R1을 요청하고 있다. 그래프를 생성한 후 Cycle이 생기면 Deadlock이 발생한 것! Deadlock Prevention(교착 상태 예방) 4개의 deadlock 발생 필요 조건 중 하나를 제거..
-
[백준/BOJ] 2910번 빈도 정렬 (C++)알고리즘 문제풀이/백준 2021. 1. 11. 03:23
www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫쨰 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 조금 까다로웠던 정렬 문제입니다. (다시 풀기) 빈도 수를 기준으로 내림차순 정렬하고, 빈도 수가 같다면 원래 순서를 유지해야하는 문제입니다. 예를들어, 4 2 2 1 2 1 이 입력값이라면 출력값은 2 2 1 1 이 나와야 합니다. 이를 구현하기 위해서 두 개의 map을 사용했는데, 각각 입력값의 빈도수, 입력값의 순서를 저장합니다. 빈도 수를 저장한 map을 벡터로 값을 옮기고, cmp 함수를 만들어 입력값을 저장한 map을 이용해주었습니다. #in..
-
[백준/BOJ] 10825번 국영수 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 22:02
www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 정렬 유형의 문제입니다. 한 벡터에 많은 입력값을 받아야하는데, 서로 타입도 달라서 따로 Info라는 구조체를 만들어줬습니다. 그 후 입력값을 벡터에 저장하고, cmp함수를 조건에 맞게 구현한 후 정렬해주었습니다. #include #include #include using namespace std; struct Info { string name; int korean, english, mat..
-
[백준/BOJ] 11656번 접미사 배열 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 21:50
www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 정렬 유형의 문제입니다. 문자열을 입력받고 0번부터 문자열 크기의 - 1 까지 인덱스를 시작점으로 문자열을 분리한 값을 string 벡터에 넣어줍니다. 그리고 마지막에 정렬을 해주면 간단하게 풀 수 있는 문제였습니다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); string s; vector v; cin >> s; for(int i = 0..
-
[백준/BOJ] 5648번 역원소 정렬 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 21:41
www.acmicpc.net/problem/5648 5648번: 역원소 정렬 모든 원소가 양의 정수인 집합이 있을 때, 원소를 거꾸로 뒤집고 그 원소를 오름차순으로 정렬하는 프로그램을 작성하세요. 단, 원소를 뒤집었을 때 0이 앞에 선행되는 경우는 0을 생략해야합니 www.acmicpc.net 정렬 유형의 문제입니다. n개의 숫자를 string으로 받고 이를 reverse 함수를 이용해 뒤집어줍니다. 그리고 long long 자료형 벡터에 모두 넣어준 후 sort 라이브러리 함수를 이용해서 오름차순 정렬해주었습니다. #include #include #include using namespace std; typedef long long ll; int main(void) { ios_base::sync_with..
-
[백준/BOJ] 11652번 카드 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 21:16
www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 정렬 유형의 문제였습니다. 입력값을 map으로 받고 그 입력값을 key값으로 나오는 빈도수를 value로 저장합니다. 저장이 끝나고, 벡터를 pair형으로 선언하여 map의 key, value를 한 쌍으로 옮겨줍니다. 마지막으로 cmp 함수를 크기와 빈도 수를 기준으로 정렬할 수 있게끔 구현하였습니다. 문제를 풀면서 주의해야할 점은 입력값의 크기가 최대 2^62 이므로 long long 자료형을 이용해야 ..
-
[백준/BOJ] 1431번 시리얼 번호 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 20:44
www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루 www.acmicpc.net 정렬 유형의 문제입니다. 길이, 숫자 자리수의 합, 사전순대로 비교를 하기 위해서 cmp 함수를 따로 만들어줬습니다. 그리고 숫자 자리수의 합을 기준으로 정렬하기 위해서 자리수의 합을 구하기 위한 함수로 getSum 함수를 만들었습니다. #include #include #include using namespace std; int getSum(string str) { int sum = 0; for(int..