전체 글 (146) 썸네일형 리스트형 Reference(참조) vs. Pointer(포인터) in C++ C++로 dp관련 알고리즘 문제를 풀 때, 아래와 같이 참조(reference)를 종종 이용하곤 했다. void sol(int i,int j){ int& ref=s[i][j]; ... } 포인터와 유사한 듯한 이 참조는 포인터와 비교하여 어떤 차이가 있는지 궁금하여 알아보았다. Pointer 우선, 포인터는 다른 변수의 메모리 주소를 가지고 있는 변수로, 아래와 같이 사용한다. int a = 10; int *p = &a; 포인터가 가리키는 메모리 위치에 접근하기 위해서는 * 연산자(operator)를 사용하여 디레퍼런스(dereference)하는 과정이 필요하다. Reference 반면에, 참조 변수는 이미 존재하는 변수의 별칭(alias)이다. 내부적으로는 포인터와 같이 객체의 주소를 저장하도록 구현되.. Imperative(명령형) vs. Declarative(선언형) Programming Combine을 공부하려는데 두 개의 용어가 빈번하게 등장하니 간단히 개념을 잡고 넘어가자. Imperative Programming Wikipedia 에 따르면, imperative programming를 다음과 같이 정의한다. In computer science, imperative programming is a programming paradigm that uses statements that change a program's state. In much the same way that the imperative mood in natural languages expresses commands, an imperative program consists of commands for the computer .. [ 프로그래머스 - 동굴 탐험 ] 해설 및 코드 https://programmers.co.kr/learn/courses/30/lessons/67260 목적 두 방의 경로(path)와 순서(order)가 주어질 때, n개의 방을 모두 방문할 수 있는지 구하자. 접근법 트리 형태로 구성된 동굴을 0번 방 부터 dfs 방식으로 방문한다. 도중에 순서(order)로 인해 계속해서 아래로 갈 수 없는 방은 매달아 둔다. 그리고 가능한 시점에 방문을 계속한다. (아래 코드 참조) #include using namespace std; const int MAXN=2e5; bool vis[MAXN]; int prior[MAXN],hang[MAXN]; vector edge[MAXN]; void visit(int v){ if(vis[v])return; if(!vis[pr.. [ BOJ 백준 1126번 - 같은 탑] 해설 및 코드 https://www.acmicpc.net/problem/1126 목적 N개의 블록을 이용해 두 탑의 높이를 같도록 쌓는 여러가지 방법 중, 최대 높이를 구하자. 접근법 1. 두 탑의 높이 차를 이용한 DP를 사용하자. 2. s[i][j]를 i번째 블럭을 이용해 높이차가 j인 두개의 탑을 쌓았을 때의 최대 높이라고 정의한다. 예를 들어, i번째 블럭을 이용해 높이 차가 5이 두 탑을 쌓았다고 가정하겠다. 그러면 왼쪽 탑이 높든 오른쪽 탑이 높든 높이 차 j라는 하나의 경우로 처리할 수 있다. 또한, 탑의 높이를 [L, R]와 같이 표현하면, [10, 15]나 [25, 20]를 s[i][5]=25 라는 값으로 처리할 수 있다. 3. i+1번째 블럭을 이용하는 경우는 어떻게 처리하나? 각 j의 값에 따라 세.. [ BOJ 백준 2473번 - 세 용액 ] 해설 및 코드 https://www.acmicpc.net/problem/2473 목적 용액의 특성값들이 N개 주어질 때, 3가지의 특성값을 더해 절대값이 0에 가장 가까운 용액의 특성값들을 구하자. 접근법 첫 번째 용액이 정해진 상태라면, 나머지 두 개의 용액을 선택하여 절대값이 0에 가깝도록 하는 것은 투 포인터 알고리즘으로 구할 수 있다. (투포인터 알고리즘에 대한 설명은 다음 글 참조 [백준 2470 - 두 용액]) 첫 번째 용액으로 선택할 수 있는 용액의 수는 총 N-2개이며, 이 용액의 특성값을 더하여 절대값이 0에 가까운 값을 만들기 위한 나머지 두 개의 용액만 구하면 된다. #include #define f(i,l,r) for(int i=l;i=r;--i) using namespace std; typede.. [ BOJ 백준 2470번 - 두 용액 ] 해설 및 코드 https://www.acmicpc.net/problem/2470 목적 용액의 특성값들이 N개 주어질 때, 특성값을 2개를 더해 절대값이 0에 가장 가까운 용액의 특성값들을 구하자. 접근법 투 포인터 알고리즘으로 구현이 가능하다.(완전 탐색이나 이분 탐색보다 빠르고 간단하다.) 투 포인터 알고리즘은 다음과 같이 정렬된 배열이 있다면, 배열의 처음과 끝을 가리키는 L과 R을 서로가 가까워지도록 이동하는 방식으로 동작한다. 초기 상황을 제외하고 최대 N-2번의 포인터 이동이 있는데, 각 턴마다 두 포인터가 가리키는 수의 합이 0에 수렴하도록 한 개의 포인터를 이동해야 한다. 즉, 수의 합이 양수일 때는 R을 이동하여 합을 줄여주고, 음수일 때는 L을 이동하여 합을 늘려준다. 동시에 절대값의 최소값을 갱신해주.. Priority Inversion Priority Inversion은 선점형 우선 스케쥴링(preemptive priority scheduling) 방식에서 발생하는 작업의 우선 순위가 역전되는 현상이다. 예를 들어, 우선 순위가 높고 낮은 작업인 H와 L이 있다. 각각은 배타적으로 접근해야 하는 공유 자원 R을 사용하고 있다. 만약, H가 R에 대한 접근을 L의 접근 이후에 한다면, H의 작업은 L이 R의 소유권을 놓을 때까지 지연된다. 우선 순위가 높은 H가 낮은 L을 기다리는 상황이 되는 것이다. 이러한 상황을 피하기 위해 L이 R의 소유권을 즉시 양도(relinquish)하도록 시스템을 설계하기도 한다. 하지만, 도중에 중간 우선 순위를 가지며 R을 사용하지 않는 작업 M이 작업 큐에 들어온다면, L보다 우선 순위가 높으므로 M이.. [ BOJ 백준 17780번 - 새로운 게임 ] 해설 및 코드 https://www.acmicpc.net/problem/17780 목적 다음과 같은 체스판에서 말들을 규칙에 따라 이동하여 게임을 진행할 때, 게임이 끝나는 턴의 번호를 출력하자. 접근법 이 프로그램의 동작은 다음과 같은 일련의 과정이 종료조건(4개의 말이 쌓이는 경우 or 턴 번호가 1000을 넘어가는 경우)을 만족할 때까지 반복된다. 1. 말의 이동 가능 여부 확인 말은 번호 순으로 이동 하는데, 만약 이동시킬 차례의 말이 다른 말 위에 올라가 있는 상태라면 이동할 수 없으며, 차례를 건너 뛰게 된다. (해당 상태는 말의 이동을 처리하는 함수에서 설정하자.) 그리고 이동하려는 위치를 검사해야 한다. 만약 체스판의 범위를 벗어나거나, 칸이 파란색이라면 진행 방향을 반대로 하여 이동하게 된다. 2. 말.. 이전 1 2 3 4 ··· 19 다음
