전체 글 (174) 썸네일형 리스트형 [C++] 순열과 조합 DFS로 구현해보기 코딩 테스트를 준비하면서 느낀건데 최종 보스는 DFS와 dp인 것 같다. 생각하기는 어려운데 굉장히 직관적이랄까.. 백준 문제를 풀다가 조합이 꼭 필요한 문제가 있었는데 조합을 구현할 줄 몰라서 이 글을 쓰게 됐다. 조합을 먼저 구현한 뒤에 순열을 구현해 보겠다. 둘 다 재귀를 이용한 DFS로 구현한다. 1. 조합 그냥 직관적으로 생각해보자. 크기가 5인 배열 {4, 2, 1, 3, 5}에서 3개를 뽑는 5_C_3의 경우를 예로 들어보자. 첫번째 숫자부터 차례대로 뽑았다가 3개를 다 뽑으면 다시 되돌아오고 다음 숫자를 뽑을 것이다. 말로 하면 헷갈리니 그림으로 보자. 5가지 경우의 수까지를 살펴보면 아래와 같다. 우선 조합에서는 각 경우의 수 마다 '한 번 뽑으면 다시 쳐다볼 필요가 없다'가 중요.. [C++] Next Permutation, Prev Permutation 파헤치기 1. Next Permutation 알고리즘 문제를 풀다 보면 라이브러리의 next_permutation 함수를 쓸 일이 많다. 문득 이 함수의 원리가 궁금해서 이 글에 정리해보려고 한다. Next permutation의 기본 원리는 오름차순을 내림차순으로 변경하는 것이다. 변경하는 과정에서 모든 가능한 조합이 나오게 된다. 단, 수열은 사전에 오름차순 정렬되어 있어야 한다. Next_permutation의 과정을 살펴보면 아래와 같다. Next Permutation 과정 1. find max(k), a[k] < a[k+1] 2. find max(m), a[k] < a[m] && k < m 3. swap(a[k], a[m]) 4. reverse(a[k+1:]) [1, 2, 3, 4, 5]를 수동으로 한 .. [C++] 최소비용신장트리 - kruskal 알고리즘 최소비용신장트리는 순환하지 않는 최소 비용의 경로를 의미한다. kruskal 알고리즘은 그리디 알고리즘이며 합집합 찾기가 이 알고리즘의 핵심이다. 사실 알고리즘 자체는 굉장히 간단하다. 아래의 세 단계만 거치면 된다. 1. 비용을 기준으로 오름차순 정렬한다. 2. 순환하지 않도록 최소 비용순으로 노드를 선택한다. 이때 Union-Find 알고리즘을 사용한다. 3. 모든 노드를 선택할때까지 2번을 반복한다. 사실 합집합 찾기만 알면 너무 간단한 문제라서 크게 설명할 건 없다. Edge 클래스를 정의해 주고 연산자 오버로딩만 해주면 된다. 그 외에는 위의 세 단계만 코드로 구현하면 된다. 코드가 이해가지 않으면 Union-Find 파트를 다시 읽어보자. 아래 코드는 '프로그래머스 - 섬 연결하기' 문제 .. [C++] 합집합 찾기(Union-Find) 합집합 찾기는 그래프의 연결 유무를 판별할 때 쓰이는 알고리즘이다. 세 가지 함수만 구현하면 된다. 1. getParent - 부모 값 반환 2. unionParent - 부모 노드 합치기 3. findParent - 같은 부모 노드를 가지는지 확인(연결여부 판별) 먼저 노드 사이의 관계를 파악하기 위해 Parent라는 배열을 만든다. 노드의 개수만큼 크기 설정을 해주면 된다. 예를 들어 노드의 개수가 다섯 개면 아래와 같이 초기화해준다. 노드 사이의 연결관계는 Parent의 원소값으로 판단한다. 일반적으로 parent는 원소값이 작은 값을 기준으로 한다. 만약 1과 5를 연결하면 아래와 같다. 이제 Parent[5] = 1로 바뀐 과정을 살펴보자. 가장 기초가 되는 getParent 코드는 아래.. [ 운영체제 ] Dual-Mode Operation(커널 모드, 사용자 모드) 메인 메모리는 커널 영역과 사용자 영역으로 구분된다. 이 둘은 같은 공간을 공유하고 있으므로 자칫하면 사용자 영역이 커널 영역을 침범할 수 있다. 이러한 침범 문제를 방지하기 위해 하드웨어의 도움이 필요하다. CPU에는 Mode bit라는 것이 존재한다. Mode bit 값에 따라 커널 모드와 사용자 모드로 구분되는데, 커널 모드는 모든 메모리에 접근 가능하지만 사용자 모드는 오직 사용자 영역에만 접근 불가능하다. 하드웨어적으로 아예 분리를 시켜놨기 때문에 사용자 영역이 커널 영역을 침범하는 일은 없다. 한편, 사용자 모드에서는 실행 가능한 명령이 매우 한정적이다. 컴퓨터를 할때 대부분이 커널 모드로 동작한다고 봐도 무방하다. 그렇다면 사용자 모드에서 커널 모드로의 전환은 어떻게 이루어질까? 이는 인.. [ 운영체제 ] 프로세스의 개념, 인터럽트 프로세스는 간단하게 '실행 중인 프로그램'으로 정의할 수 있다. '실행중'이라는 것은 해당 프로그램이 메모리 위에 있다는 것을 뜻한다. 프로그램은 컴퓨터 상에 설치된 'exe' 파일이라고 생각하자. exe파일은 실행파일이라고 하는데 이는 단순히 코드일 뿐이다. exe파일을 클릭하면 필요한 메모리 공간을 할당받는데, 이를 프로세스라고 한다. 하나의 프로그램이 여러개 실행되면 프로세스 또한 여러개가 되는 것이다. 그림으로 나타내면 아래와 같다. OS가 프로세스에게 할당하는 메모리는 구역마다 이름이 정해져 있다. 각 구역의 이름은 Text, Data, Stack, Heap이고, 저장되는 데이터 종류는 아래와 같다. - Text : 프로그램의 code 저장 - Data : 전역 변수 저장 - Stack .. 이전 1 ··· 19 20 21 22 다음
