yeongminb의 PS 블로그

Floyd Warshall 알고리즘은 다익스트라 알고리즘의 진화(?) 버전으로 가중치가 주어진 그래프에서 모든 정점으로부터 모든 정점으로까지의 최소 거리를 구하는 알고리즘이다. Floyd Warshall 알고리즘은 모든 거쳐가는 정점을 기준으로 DP처럼 동작해 구현이 매우 간단하다. 1) Floyd Warshall 알고리즘의 동작 floyd warshall 알고리즘은 다음과 같이 동작한다.let) $d[i][j] :=$ ($i$부터 $j$까지의 최소거리 배열)let) $graph[i][j] :=$ ($i$와 $j$를 연결한 간선의 가중치) -> 연결이 안될 경우 INF(∞)1) $d[i][j]$ 초기화 $$d[i][j] = \begin{cases}0 & i=j\\graph[i][j] & otherwise..

다익스트라 알고리즘은 양의 가중치만 있는 그래프에서 어떤 정점으로부터 모든 정점까지의 최소 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 최단거리를 구할 때 매우 유용해서 GPS등에서도 사용한다고 한다(정확히는 모르지만,,). 쉽게 설명되어있는 유튜브 영상 : https://www.youtube.com/watch?v=EFg3u_E6eHU  아주 예전에 다익스트라 알고리즘을 처음 알았을 때 아주 똑똑한 친구가 위의 영상을 추천해줘서 봤었다. 이해하기 쉽게 설명되어있어서 다익스트라 알고리즘을 배우려고 하거나 까먹었을 때 보면 좋은 영상이다.  1. 다익스트라 작동 과정다익스트라는 다음과 같이 작동한다.1) pair형태로 {0, 시작정점}을 priority queue에 넣는다.2) priority queu..

MST 는 Minimum Spanning Tree (최소신장트리)의 약자로 가중치가 있는 그래프에서 모든 가중치의 합이 최소가 되도록 하는 어떤 트리(정점이 $V$개일 때 간선이 $V-1$ 인 연결그래프)를 의미한다. 예를 들어서 아래의 그래프에서는 찐하게 칠해진 트리가 가능한 모든 트리 중에서 가중치의 합이 최소이므로 MST 가 된다. 주어진 그래프에서 MST 를 구하는 알고리즘은 대표적으로 $Prim's\space Algorithm$ 과 $Kruskal\space Algorithm$ 이 있다. $Kruskal\space Algorithm$ 에 대해 알아보자. 1) $Kruskal\space Algorithm$  의 동작 Kruskal 알고리즘은 다음과 같이 동작한다.1) 모든 간선을 가중치를 기준하여..

Union-Find 알고리즘은 서로소 집합(Disjoint-Set) 알고리즘 이라고도 한다. 어떤 노드들이 서로 같은 그래프에 속해 있는지(두 노드까지의 경로가 존재하는지) 판별하기 위해서 사용되며 그래프를 다룰 때 중요한 알고리즘 중 하나이다.  Union-Find 알고리즘은 자신의 부모 노드를 불러오는 알고리즘, 두 노드를 이어주는 알고리즘(Union), 두 노드가 같은 그래프에 있는지 확인하는 알고리즘(Find)으로 구성된다. 이 알고리즘들은 각 노드의 부모 노드를 기준으로 구현하고 보통 parent라는 일차원 배열에 부모 노드들을 저장한다. 예시)노드12345부모 노드12345  먼저 초기에 아무 간선도 없을 때에는 각 노드의 부모 노드를 자기 자신으로 지정해둔다. $O(N)$ 알고리즘1. Uni..

1. BFS와 DFS의 개념 1) BFS먼저 BFS는 영어로 풀어쓰면 Breath-First-Search로 너비 우선 탐색을 의미한다.  다음과 같은 그래프가 주어졌을 때 BFS의 방식으로 그래프 탐색을 어떻게 하는지 알아보자. 먼저 기준 노드를 잡아야한다. 기준 노드는 쉽게 말하면 탐색을 시작하는 노드을 의미한다. 편의상 1번 노드를 기준으로 탐색을 시작하자. BFS 로 탐색하면 아래와 같은 결과가 나온다.1 - 2 - 4 - 5 - 3 - 6 - 7 BFS는 기준노드와 거리가 가까운 노드들부터 탐색을 한다고 봐도 무방하다.   2) DFS다음으로 DFS는 Depth-First-Search로 깊이 우선 탐색을 의미한다.아까와 같은 그래프가 주어져있고 1번 정점부터 탐색을 시작한다고 할 때 탐색 결과는 ..

문제 링크 문제 풀이 이 문제는 Knapsack Problem과 문제 유형은 비슷하지만 고려해야할 게 4개나 되서 조금 더 까다로운 문제이다. 배낭 문제 처럼 DP를 하려고 하면 적어도 변수가 5개인 5차 점화식이 필요해서 막막할 수 있다. 근데 $N ≤ 15$ 로 상당히 작기 때문에 백트랙킹 $O(2^N)$으로 노가다해도 시간 초과가 나지 않을 것으로 보인다. 그래서 걍 백트랙킹만 조건에 맞춰서 잘 구현해주면 끝난다.  백트랙킹을 할 때 모든 재료에 대해서 포함할지, 포함하지 않을 지 두 가지 경우만 신경써주면 되서 크게 어렵진 않지만 종료조건은 조금 까다로울 수 있다. 문제의 출력 조건을 보면 같은 비용의 집합이 하나 이상일 때 사전 순으로 가장 빠른 것을 출력해야한다라고 되어있다.  이것 때문에 틀..

문제 링크 문제 풀이 이 문제는 $N\times M$ 칸에 숫자들이 적혀 있을 때, 테트로미노 타일을 이용해 타일이 포함하는 수들의 합의 최댓값을 구하는 문제이다.  여기서 테트로미노는 폴리노미노의 한 종류로 네 개의 정사각형이 변끼리 인접하여 만들어지는 도형을 의미한다.    $N,M ≤ 500$ 이라서 그냥 브루트포스로 모든 점들에 대해서 백트랙킹으로 탐색해줘도 충분하다. 이때 시간복잡도는 $O(MN)$인데, 정확히는 백트랙킹 할 때 최대 $4^4$ 개의 가짓수가 있어서 $256MN$만큼의 연산이 필요하다.  먼저 Back Tracking 함수를 먼저 구현해보자. 초기 좌표와 깊이, 그리고 현재까지 숫자의 합을 매개변수로 하였다.void BT(int x, int y, int depth, int k){..

파이썬에서 tkinter 모듈을 이용해서 암호화 복호화 프로그램을 만들어보았다. 그러려면 tkinter 창의 간단한 디자인과 암호화 복호화 방법을 정해야한다.디자인 먼저 디자인은 크게 중요하지 않으므로 간단하게 하였다. 암호화 시킬 텍스트를 집어넣는 엔트리와 암호화된 결과를 보여줄 엔트리, 또 암호화 시킬 버튼이 필요하고, 복호화도 마찬가지로 복호화 시킬 암호를 넣는 엔트리와 복호화된 결과를 보여주는 엔트리, 또 복호화 버튼이 필요하다. 추가적으로 무슨 엔트리인지를 보여주는 텍스트와 모든 내용을 지우는 지우기 버튼도 추가하였다.코드from tkinter import *win = Tk()win.title('Encryption & Decryption')win.geometry('400x400')entry1 =..

예전에 LIS알고리즘을 DP로 $O(N^2)$만에 구현하는 포스팅을 올린 적이 있다. 하지만 이 알고리즘을 쓰기엔 시간복잡도가 크다보니 시간초과가 나는 문제가 많다.LIS $O(N^2)$  이번 포스팅에서는 이분탐색을 활용한 $O(NlogN)$ LIS 알고리즘을 올려보려고 한다. 이분탐색을 써서 푸는 백준 문제는 아래 세 개가 있다.가장 긴 증가하는 부분 수열 2가장 긴 증가하는 부분 수열 3 가장 긴 증가하는 부분 수열 5  LIS 길이 구현 방법 외부 배열이나 벡터에서 각각의 숫자들의 lower bound를 구해 그 인덱스로 넣어주는 방식이다. 아래 그림은 LIS 이분탐색 과정이다. 이렇게 이분탐색으로 배열을 만들고 나면 크기 순서대로 숫자들이 정렬이 되어있다. 여기서 이 배열의 길이는 LIS의 길이..

solved.ac 사이트에 들어가봤는데 그랜드 아레나 파티 퍼즐 힌트라는 것을 하고 있길래 궁금해서 들어가봤다. 문제가 첫 번째부터 열 번째까지 있는데 한 문제 한 문제가 다 쉽지 않다. 여기에는 하나씩 문제들을 풀면서 풀이를 적어보겠다. 높은 수준의 지능이 요구되니 오랫동안 고민해보면 지능 상승(?)에 도움이 될 수도 있을 것 같다. 1. 첫 번째 이야기 - 카드더보기 첫 번째 문제는 주어진 게 "cards.pdf"라는 파일만 주고 답을 입력하라고 한다. 파일을 열어보면 이상한 문자들밖에 없다. 처음에는 뭘 해야할지 다 막막하다. 오래 고민하다 보니 문자들이 알파벳의 일부라는 사실을 알게 되었다. 그래서 이 문자들을 조합해서 의미있는 문자를 만들어야겠다고 생각했다. 문자들을 회전도 해보고 계속 조합해서..

문제 링크 문제 풀이 이 문제는 그래프가 주어질 때 서로 연결되어있는 정점이 없도록 최대한 많은 정점을 선택하는 문제이다. 처음 보자마자 이색 염색이 떠오르긴 했지만 홀수사이클이 존재하는 경우에는 이색 염색이 안되므로 다른 방법으로 해야한다.  Case 1) 쪽방이 아예 존재하지 않는 경우(∀$C_{i} = 0$)N = 1 → 1마리N = 2k or N = 2k+1→ k마리 Case 2) 쪽방이 존재하는 경우 먼저 당연하게 쪽방의 개수가 1개 이상인 칸에 경우 쪽방에만 개미를 배치하는 것이 유리하다. 그럼 쪽방에 있는 방을 기준으로 구간을 나누어볼 수가 있다. 문제의 예시에서는 쪽방이 존재하는 방은 1, 4, 6으로 3개이다. 이 3개를 기준으로 구간이 3개로 나뉘게 된다. 이때 1,4,6에는 쪽방에만 ..

내신 공부를 위해 과학 공부를 하고 있던 중 친한 친구가  떨어진 거리나 비열에 따라서 복사 평형에 도달하는 시간이 어떻게 되냐라고 물어봐서 탐구해보게 되었다. 복사 평형은 물체가 흡수하는 에너지의 양과 물체의 온도에 의한 복사에너지의 양이 같아질 때 온도가 일정하게 유지되는 상태를 말한다. 이를 그래프로 나타내어 보면 아래와 같이 표현된다.    물체는 (흡수하는 에너지량) - (방출하는 에너지량) 만큼의 에너지로 자신의 온도를 변화시킨다. 이 점을 이용해서 시간을 계산해볼 것이다. 먼저 사용할 공식을 먼저 써보자.여기서 위의 식은 대부분이 알 것이라 생각하고, 밑의 식은 슈테판-볼츠만 법칙으로 M은 단위 시간, 물체의 단위 면적 당 물체가 방출하는 복사에너지를 의미한다. 시그마는 슈테판-볼츠만 상수로..

문제 링크  문제 풀이 이 문제는 문제에 나온 격자칸에서 두 사람이 게임을 진행할 때 각 칸에 따라 선공이 이길지 후공이 이길지 판단하는 문제이다. 이런 유형의 문제는 게임이론에서 winning state와 losing state를 설정하는 것으로 풀 수 있다. 간단히 말하면 winning state는 받았을 때 이기는 게임의 상태를 의미하고 losing state는 받았을 때 지는 게임의 상태로서 재귀적으로 정의된다. 예를 들어서 상대가 마지막에 $(N-1,M)$칸으로 돌을 이동시켰다면,  $(N,M)$으로 칸을 이동시킬 수 있으므로 $(N-1,M)$은 winning state로 정의 된다.winning state : 갈 수 있는 칸 중 losing state가 적어도 하나 존재하는 칸   (선공이 이..

문제 링크  문제 풀이 누가 봐도 위상정렬을 사용하는 문제이지만 처음 보자마자 그냥 dp로 풀 수 있을 것 같아서 dp로 시도해보았다. 일단 유향그래프니까 각 점에서 들어오는 선분에 연결된 점들을 graph에 저장해주었다. 또 time이라는 배열에 각 건물을 짓는데 걸리는 시간을 저장하였다. dp를 아래와 같이 정의하자.$dp[i] :=$ 건물 $i$를 건설완료 하는데 드는 최소 시간 그러면 아래와 같은 점화식을 얻을 수 있다.  시간복잡도는 $O(NK)$이므로 dp로 해도 시간초과는 나지 않을 것이다. 시행 착오 문제에서 여러개의 테스트 케이스가 주어지는데 각 테스트 케이스마다 graph를 초기화하지 않았다. 근데 신기하게도 예제 1번은 통과해서 조금 고민했었다. 그리고 graph를 초기화해야한다는 사..

크기를 무시할 수 있는 질량 $m$인 물체가 질량과 폭을 무시할 수 있는 길이 $l$인 막대 끝에 달려있다고 하자. 이 물체를 오른쪽으로 아주 살짝 밀었을 때 막대가 회전하여 물체가 지면에 닿을 때까지 걸리는 시간은?  1. 첫 번째 접근어짜피 물체는 막대에 매달려서 원 궤도로만 운동하기 때문에 원궤도의 접선 방향의 가속도만 고려해서 직선 운동처럼 접근하려고 했다. 연직선으로부터 기울어진 각도를 $θ$라고 할 때 접선 방향 가속도는 $g \sin\theta$이다. 이 상황에서 원궤도를 직선으로 바꾸어보자.$l\times\theta$만큼 진행했을 때 가속도가 $g \sin\theta$이고 최종적으로 $\frac{\pi\times l}{2}$를 가는 상황과 같다. 여기서 구간을 무한히 쪼갠다음 각각의 구간에..

문제 링크   "물리학" 카테고리에 있는 문제들을 풀어보다가 이 문제가 재미있게 생겨서 풀어보았다. 예전에 이런 충돌수에 관련된 문제를 3Blue1Brown 이라는 굉장히 좋은(?) 채널에서 본 적이 있다.유튜브 영상 이 영상에서는 두번째 물체의 질량이 100의 거듭제곱 꼴일 때 충돌횟수가 π의 앞의 자리수가 되는 이유를 설명해주고 있는데 예전에 흥미롭게 봤던 경험이 있어서 생각이 났다.  1. 문제 풀이 먼저 알아야할 것은 두 번째 물체의 초기속력이 0만 아니라면 충돌수에 영향을 주지 않는다는 것이다. 만약 첫 번째 물체의 초기속력이 있었다면 상관이 있겠지만 첫 번째 물체의 초기속력이 0이므로 두 번째 물체가 어떤 속력을 가지든 속력비율은 항상 일정하기 때문이다. 근데 소수점계산에서 오류가 발생할 수도..

각 $α$만큼 기울어진 빗면에서 $θ$의 각도로 초속 $v_{0}$로 공을 던진다. 공의 출발 위치로부터 공아 밧면 위에 떨어진 지점까지의 거리가 최대가 되기 위한 $θ$와 이때의 최대 도달 거리를 구하여라.  이 문제를 풀기 위해 중력가속도와 초속를 빗면의 수직 성분과 수평 성분으로 분해해보자.1. 빗면에 수직인 성분 빗면에 수직인 성분 관점에서 보면 초속도가 ${v_{0}}\space{\sin\theta}$ 이고 가속도가 ${-g}\space {\cos\alpha}$이다. 따라서 다시 빗면에 착지하기까지 걸리는 시간 $t$는 최고점까지 올라가는 시간의 2배이므로 아래와 같은 식이 성립한다.2. 빗면에 수평인 성분빗면에 수평인 성분 관점에서 보면 초속도가 ${v_{0}}\space{\cos\theta}..

문제 링크   백준에서 대회 문제들을 찾아보다가 이 문제를 발견했는데 실버1이기도 하고, 재미있게 생겨서 시도해보았다.   문제 풀이 문제는 $m\space\times\space n$ 격자칸에 알파벳들이 적혀있을 때 인접한 칸끼리 이어서 만들 수 있는 $YOKOHAMA$의 개수를 묻고 있다. $m$과 $n$이 모두 $10$ 이하여서 알파벳이 최대 $100$개까지 밖에 없다. 이런 문제는 노가다로 풀어도 괜찮아보인다. DFS로 Y부터 출발해 가능한 모든 경우를 탐색해보자.  1. 입력입력 부분에서는 $m$과 $n$을 입력 받고, table 배열에 $m\space\times\space n$ 격자판을 저장하자. 또, vector에 pair형태로 Y의 모든 좌표들을 저장해주자.char table[11][11];..

문제 링크   문제 풀이 이 문제를 처음 도전할 때는 모든 사대에 대해서 잡을 수 있는 동물들을 카운트 해주는 Brute Force 방법을 쓸 수 있다(시간복잡도 $O(MN)$. 그렇게 하면 $M$과 $N$이 $10^{5}$이하이기 때문에 시간초과가 날 것이다. 그래서 다른 방법을 생각해보면 이분탐색이 떠오른다. 모든 동물에 대해서 조건을 만족하는 사대를 이분탐색으로 찾아주면 시간복잡도 $O(MlogN)$으로 시간초과가 나지 않을 것이다. 조건은 사대와 동물 사이 거리가 L보다 작은 것이므로 아래와 같이 정리할 수 있다.$|x - a| + b ≤ L ⇔ |x - a| ≤ L - b$$⇔ b - L ≤ x - a ≤ L - b$$⇔ a + b - L ≤ x ≤ a - b + L$ 각각의 동물의 좌표 $(a..

문제 링크  문제 풀이 이 문제는 원 위에 정$D1$각형부터 정$D2$각형까지 그릴 때 중심에서 다른 점들에 의해 '가려지지 않는' 점들의 개수를 묻는 문제이다.  제한시간이 1초이고 $D2$가 $2000$이하이므로 넉넉하게 $O(n^2)$으로 해도 별 문제가 없을 것 같아보인다. 반지름이 $D1$인 원에서 부터 반지름이 $D2$인 원까지 각각의 원에 대해서 각각의 좌석들에 대해 모두 탐색을 해보자.각 원에서 좌석들에 그에 대응하는 분수를 대응시켜보자. 이러면 분수를 기약분수로 나타내었을 때 값이 같은 좌석들끼리는 서로 같은 직선상에 있다는 것을 알 수 있다. 따라서 이를 이용해서 문제를 접근하면, 구하는 값은 등장한 기약분수의 종류이다. 코드#include #include using namespace ..

이항게수와 관련된 PS를 하다가 범위가 큰 $n$과 범위가 큰 $r$에 대해서 ${n \choose r}$의 일의 자리 수를 구해야하는 일이 생겼다. 일반적인 콤비네이션 계산($O(n)$)을 하고 일의 자리수를 구하면 시간초과가 나서 다른 방법이 필요했다. 이 포스팅에서는 이와 관련된 내용을 적어보려고 한다.1. 조합을 계산하는 일반적인 방법 가장 쉬운 방법으로는 정의식대로 $n!$, $(n-r)!$, $r!$을 모두 계산해주고 연산해주는 것이다. 하지만 $n$과 $r$이 조금만 커져도 계산 시간이 오래걸리고 PS에서는 정수형 범위나 심지어는 long long 범위까지 넘어갈 수 있기 때문에 좋지 않은 방법이다.int factorial(int n){ int output = 1; for(int ..

문제 링크 문제 풀이 이 문제는 초기 위치에서 시작해, 이전 변위와 현재 변위의 차가 1 이하가 되도록 이동하여, 마지막 위치까지 이동했을 때 이동 횟수의 최솟값을 묻는 문제이다. $i$번째 이동에서의 이동거리를 $D(i)$로 정의해보자. 이제 각각의 이동에 대해 $D(i)$를 최대로 할 수 있게 Greedy방법을 써보자. 현재 위치 $current$에 대해 $D(i)$로 이동하려면         (a) 남아있는 거리 $d$는 적어도 $1 + 2 + ... + D[i]-1$보다는 커야한다.조건 (a) 를 만족해야함이 자명하다(변위는 1씩 감소할 수 있는데 마지막에 변위가 1로 끝나야하므로) . 또, $D(i)$는 이전 변위 $D(i-1)$에 의해서 결정되는데, 둘의 차이는 항상 1보다 작거나 같다. 따라..

백준 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net  오늘은 DP를 이용해 최장 증가 부분 수열의 길이를 구하는 코드를 구현해볼 것이다.최장 증가 부분 수열 : 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.$ex)$  $A..

오늘은 크게 어렵진 않지만 그래도 생각해볼 가치가 있는 문제를 가져와보았다. 이 문제는 quant라는 곳에서 인터뷰 문제로 나온 적이 있다고 한다. One hundred people are in line to board a plane which has exactly 100 seats. Each passenger has a ticket assigning them to a specific seat, and the passengers board one at a time. The first person to board is drunk, picks a random seat, and sits in it. The remaining passengers board; if they find their assigned se..

PS를 좋아하는 사람이라면 한 번쯤은 Knapsack Problem에 대해 들어본 적이 있을 것이다. DP를 활용하는 대표적인 문제이기도 하고, 알고리즘을 공부하기에도 좋은 문제이다.Knapsack Problem :  주어진 물건들에 대해 그 가치와 무게가 주어져있을 때,  무게의 합이 담을 수 있는 최대 무게를 넘기지 않고 가치의 합이 최대가 되도록 배낭에 담기 위해서는 어떤 물건을 담아야하는가?자세한 설명  : Knapsack problem - WikipediaFrom Wikipedia, the free encyclopedia Problem in combinatorial optimization Example of a one-dimensional (constraint) knapsack problem: ..

높이가 $h$인 지점에 있는 질량 $m$의 물체를 벽에서부터 막대를 이용해 경사각이 $θ$인 경사까지 굴릴 때 걸리는 최소 시간은? 그리고 그때의 막대의 길이는?   문제만 놓고 보면 굉장히 쉬운 문제 같아보이지만 처음 접근할 땐 생각을 많이 해봐야한다. 이 문제를 풀어보기 전에 조금 더 쉬운 문제를 한 번 보자. 어떤 원에서 지표와 수직한 지름으로 공을 떨어뜨릴 때 걸리는 시간과 다른 호로 공을 떨어뜨릴 때 걸리는 시간이 같을까? 이건 자명하게 같다. 왜냐하면 둘 다 등가속도 운동을 하는데, 가속도의 비는 1 : sinθ이고, 거리비는 sinθ : 1이기 때문에 쉽게 알 수 있다.   그럼 이것을 이용해 이 문제를 풀어보자.$\overline{PA}$를 지름으로 하는 원을 그리고, 그 원과 경사의 교점..

문제 링크  문제 풀이 이 문제는 이분 탐색을 사용하는 전형적인 문제이다. 랜선의 길이를 이용해서 이분 탐색을 하면 된다.  먼저, 왼쪽 포인터를 $L$, 오른쪽 포인터를 $R$라고 했을 때, 초기 값은 $L=1,  R$은 랜선의 길이 중 최대 길이로 지정한다. 이제 이 둘의 평균인 $M$을 보면 두 가지 경우가 있다.1. M의 길이로 랜선들을 나누었을 때 가능한 최대 개수가 N미만인 경우(색칠된 영역에 존재하지 않는 경우)2. M의 길이로 랜선들을 나누었을 때 가능한 최대 개수가 N이상인 경우(색칠된 영역에 존재하는 경우) 먼저 1번 케이스의 경우 $M$이 더 짧아져야하므로 포인터 $R$을 $M$위치로 이동시킨다. 2번 케이스의 경우에는 $M$이 구하는 정답이 될 수도 있지만 조건을 만족시키면서 $M$..

배열을 다루다보면 일정한 기준으로 그 배열을 정렬해야하는 상황이 생긴다. 이럴 때 C++ STL 에서 제공하는 sort()를 이용하면 편하다. sort()는 기본적으로 헤더파일에 속해있다. 그래서 이 함수를 쓰기 전에 먼저 헤더파일을 가져와야한다. #include 1) 배열(array) 배열을 정렬할 때는 sort()를 아래와 같이 사용한다. sort(시작주소, 끝주소 + 1) 시작주소는 (배열의 이름) + (번지수) 로 표기한다. 예를 들어 arr라는 배열의 1번지부터 시작하고 싶으면 arr+1로 나타낸다. 끝주소는 (배열의 이름) + (번지수)+1 로 표기하고, 예를 들어 n-1번지는 arr+n으로 표현한다. 2) 벡터(vector) 벡터를 정렬할 때에도 배열과 비슷한 방식을 사용한다. sort(v...

$n^2$개의 정삼각형으로 이루어진 정삼각형 격자에서 정삼각형의 개수는 어떻게 셀까? 이 포스팅에서는 이에 대한 일반화를 해보려고 한다.  먼저 이러한 문제는 점화식으로 접근하는 것이 쉬울 것 같다. 먼저 사용할 점화식을 정의해주자.$a(n,k) :=$ |한 변의 길이가 $n$인 정삼각형 격자에서 한 변의 길이가 $k$인 정삼각형의 개수| 자명하게 $a(n,1) = n^2, a(n,n) = 1$이다. 이제 $a(n,k)$에 대해서 생각해보자. $a(n,k)$을 계산할 때 위 그림에서도 볼 수 있듯이 $a(n-1,k)$에 새로 추가되는 정삼각형들을 더해주면 된다. 그럼 새로 추가되는 정삼각형의 개수를 구해보자. 1) 큰 정삼각형과 변이 평행한 정삼각형이 경우는 구하는 정삼각형은 보라색 정삼각형이므로, $n..

문제 링크  문제 풀이 이 문제에서는 사진틀의 개수와 추천횟수를 주고, 어떤 학생들을 추천했을 때 사진틀에 있는 사진들이 바뀌어 최종적으로 어떻게 되는지 묻고 있다.  나는 이 문제를 풀 때 여러 함수를 정의해서 풀었다. 먼저 사진틀에 사진들이 다 차있는지를 알아보는 full()과, 삭제할 학생을 찾는 remove(), 매 추천마다 사진틀의 시간을 더해주는 addTime()함수를 정의하였다.  먼저 full()함수는 비어있는 것이 존재할 경우 false를 리턴하고, 아닌 경우 true를 리턴하면 되기 때문에 어렵지 않다. remove()함수는 사진틀에 있는 학생들의 추천횟수를 비교해, 추천횟수가 최소인 학생을 찾아주면 된다. 근데 만약 이전까지의 최소와 같은 추천횟수를 갖는 경우에는 걸려있던 시간이 더 ..