[목차]310 [운영체제 1편] 프로세스란 무엇인가 자! 운영체제에 대해서 공부해봅시다! :) 코딩 문제 풀이에서는 항상 반말로 했지만 CS전공 관련 내용들은 존댓말로 할까 합니다! (조금 어색ㅎ) 평소 살아가면서 학교 수업 외에는 프로세스와 스레드에 관련된 내용은 들어보지 못했을 겁니다. 저 또한 그래요.. 누가 친구들한테 프로세스는 메모리에 할당 되는 건데 그건 각각의 스레드로 .. 뭐 이런말 하면 어쩌라고? 하겠죠? ㅎㅎ 일상에서 쓰이지 않는 이 단어들은 저희는 알아야 해요~ 왜냐하면 컴퓨터를 배우니깐요! 서론이 조금 길었네요! 한번 차근차근 알아봅시다! 먼저, 프로세스에 대해서 한번 얘기해볼테니까 천천히 읽어봐요~ 여러분들이 노트북을 펼쳐서 전원 버튼을 누르게 되면 제일 먼저 뜨는게 뭐죠??? 그쵸 바탕화면이죠?? 바탕화면에 여러파일들이 있을겁니다.. 남이 읽는 CS/운영체제 2022. 3. 4. [백준 1717번 / C++ / find-union] 집합의 표현 [백준 1197번 / C++ / 크루스칼] 최소 스패닝 트리 MST 그래프를 구하기 위해서는 크루스칼과 프림 알고리즘이 존재하는데 이번 문제에서는 크루스칼을 이용해서 구현하였다. 해당 문제를 글로 설명하기에는 개념적인 부분이 많이 필요하기 때문 baebalja.tistory.com 크루스칼 알고리즘이랑 99.9 % 동일하다고 보면 된다. #접근방법 먼저 parent 배열을 인덱스 번호로 초기 세팅 해준다. 입력값 b와 c 가 주어진다면 현재 b와 c를 인덱스로 가지는 parent 배열을 확인한다. 각자의 부모의 번호가 다르면 uion 해준다. (부모 번호 동일하게 세팅) 같은 집합체인지를 묻는다면 b와 c를 인덱스로 가지는 parent 배열에서 부모의 번호가 같다면 "YES" , 부모의 번호가 다르다면 .. 백준/그래프 2022. 3. 4. [백준 1197번 / C++ / 크루스칼] 최소 스패닝 트리 "운영체제 CS 전공" 준비하시는 분께 도움을 드리고자 포스팅 하고 있습니다! 관심 있으신 분들은 아래 링크 클릭! '남이 읽는 CS/운영체제' 카테고리의 글 목록 baebalja.tistory.com 최소 스패닝 트리(MST)는 최소한의 간선으로 모든 정점이 연결되어 있는 구조이다. MST 그래프를 구하기 위해서는 크루스칼과 프림 알고리즘이 존재하는데 이번 문제에서는 크루스칼을 이용해서 구현하였다. 먼저 모든 간선을 가중치 기준으로 오름차순으로 정렬한다 그리고 이 간선들을 순서대로 모든 정점이 연결될 때까지 연결하면 된다. 단! 사이클이 형성 되지 않도록! Union-Find 알고리즘을 활용해보자. 처음 들어보신 분들도 분명히 계실거고 헷갈려 하시는 분들이 계실텐데 어떻게 하는 것인지 간단하게 알아보고.. 백준/그래프 2022. 3. 4. [프로그래머스 Level_3 / C++] 최고의 집합 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합 원소의 합이 S가 되는 수 중에 제일 곱이 최대가 될 때가 언제인지 짐작이 오면 된다. S를 N으로 나누었을 때 생성되는 평균값에 가까울수록 곱이 최대가 된다. 예를 들어, S = 86 이고 N = 9 이고, 이 의미는 숫자 9개를 가지고 합을 86을 만들면 된다. N으로 S를 일단 나눠보자. 몫은 9 (평균값)이고 나머지는 5이다. 평균값 9를 N개 만큼 나열 해보자. "9 9 9 9 9 9 9 9 9" 여기에 나머지 값인 5를 가지고 1씩 공평하게 나눠주자. "9 9 9 9 10 10 10 10 10" 이 값들을 곱했을 때 최대가 나온다. #include #include #include using namesp.. 프로그래머스/Level_3 2022. 3. 4. [프로그래머스 Level_3 / C++ ] 야근 지수 이 문제를 처음 봤을 때 우선순위 큐가 떠올라야 한다. 야근 피로도를 최소화 하는 그리디한 방법은 눈에 보이는대로 제곱한 수를 최소화 시켜야 한다. 즉, 숫자 간에 오차가 최대한 작게 만들어야한다. 예를 들어 " 3, 3, 5 " 가 주어졌을 때, 2시간의 시간이 주어지면 "3, 3, 3" 으로 만들어야 제곱의 합이 제일 작고 "1, 3, 5" 로 만들면 제곱의 합이 크다는 것을 알 수 있다. 그러므로, 우선순위 큐를 활용해서 존재하는 작업 중 가장 큰 값이 top인 max heap 으로 구성하여 N시간 동안 top에 위치한 작업량을 잠깐 꺼집어내서 한시간씩 빼주고 다시 push 해준다. #include #include #include using namespace std; long long solutio.. 프로그래머스/Level_3 2022. 3. 4. [프로그래머스 Level_3 / C++ ] 순위 플로이드 와샬 알고리즘을 활용해서 풀어보자. 해당 알고리즘을 모른다면 맨 아래에 링크에 들어가서 보고 오기를 권한다. 어떤 마을에 A, B, C, D라는 친구들이 있는데, 가끔 친구들과 누가 더 싸움을 잘하는지 장난 삼아 얘기 해볼 때가 있다. 그러다가 A가 B의 눈빛이 마음에 들지 않아서 싸움을 걸었고 이후 주어진 정보에 따라 1대 1로 맞붙기로 한다. A는 B와 싸워서 이겼다. B는 D와 싸워서 이겼다. C는 A와 싸워서 이겼다. A : " D야~ 너는 B와 싸워서 졌으니까 넌 나한테도 져 ㅋㅋㅋㅋ " 즉, A는 D와 실제로 싸워본 적이 없지만 이길 수 있다는 것이다. 실제로 컨디션 좋은놈이 이길테지만 문제에선 그렇게 주어지진 않았다. 그렇다면 우리가 세팅해야할 것은 A가 D를 이겼다고 표시를 해줘야.. 프로그래머스/Level_3 2022. 3. 3. [프로그래머스 Level_3 / C++] 멀리뛰기 Level_3인데 너무 쉬운 문제여서 풀이는 생략한다. 아래 코드에서 dp배열이 왜 저렇게 만들어지는 생각해보고 n이 5일때 경우의 수를 펜으로 써보자. 그러면 이해될 것이라고 판단된다. #include #include using namespace std; int dp[2001]; long long solution(int n) { long long answer = 0; dp[1]=1; dp[2]=2; for(int i=3; i 프로그래머스/Level_3 2022. 3. 3. [프로그래머스 Level_3 / C++ / 카카오] 불량 사용자 dfs와 비트연산자를 사용해서 풀면된다. #접근방법 user_id 의 사이즈만큼 반복문을 돌리면서 banned_id를 차례대로 비교해가면서 문자열이 성립될 때 dfs를 호출한다. 이때, 방문을 표현하는 v 라는 변수에 v|(1 프로그래머스/Level_3 2022. 3. 3. [백준 2252번 / C++] 줄 세우기 (위상 정렬) 위상 정렬 알고리즘 우리가 일상생활에서 하는 모든 행동은 순서가 정해져있다. 외출을 하려고 신발을 신기 위해선 먼저 양말 먼저 신어야 한다. 신발부터 신고 양말을 신을 수는 없다. 라면, 떡볶이 등 음식을 만들 terms.naver.com 위상 정렬 알고리즘을 활용해서 푸는 문제이다. 위의 링크에서 설명이 잘되어 있으니 해당 알고리즘을 모를 경우 참조하는 것을 권한다. #접근방법 a정점에서 b정점으로 가는 경로를 이차원 벡터에 v[a].push_back(b) 로 저장을 한다. b 정점의 진입차수를 증가 시켜준다. ( indegree[b]가 2 라면 앞에 두명이 서있어야한다.) 진입차수가 0인 것부터 차례대로 출력해준다. (queue 활용) 진입차수가 0인 a정점에서 연결되어있는 b정점이 존재한다면 b정점.. 백준/그래프 2022. 3. 3. [백준 1715번 / C++] 카드 정렬하기 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이 문제를 보고 딱 떠올려야 하는 것은 그리디하게 접근해야 한다는 것이다. 예를 들어보자 . 카드의 수가 "2, 3, 4, 10, 100"의 묶음이 존재한다. 여기서 직관적으로 어떻게 해야 두 묶음을 합친 것이 최솟값이 되는지 보여야한다. 즉, 작은 수 부터 골라서 그 값을 합쳐야 한다. (2+3), 4, 10, 100 -> (4+5), 10, 100 -> (9+10) , 100 -> (19 + 100) priority_queue 를 최소힙으로 생성하여 최상단에 위치한 두개의 데이터 값을 합해서 다시 push 해준다. 자료구조 Priority_Queue는 Queue 의 한 종류인데 말 그대.. 백준/그리디 2022. 3. 2. 이전 1 ··· 15 16 17 18 19 20 21 ··· 31 다음 반응형