LRU cache 구현
페이지 교체 알고리즘에 사용되는 LRU 알고리즘을 double linked list 방식으로 구현해보겠다.
2023 삼성 SDS 알고리즘 특강 후기
2023년 1월에 대학생을 대상으로 진행한 알고리즘 특강이 끝났다. 꽤 얻어가는 것이 많았던 것 같아 정리해보려고 한다. 참고로 필자는 군대에서 종만북을 읽고 풀며 공부한 경험이 있다. 그 덕인지 백준에서 플레는 도달했으나, 최근 2년간 플러터와 안드로이드에만 집중했기 때문에 알고...
[Baekjoon, 2568] 전깃줄 - 2
두 전봇대 A와 B에서 A를 기준으로 정렬을 하면 예제는 아래와 같이 된다. A: 1 2 3 4 5 6 7 8 9 10 B: 8 2 9 1 4 6 7 10 여기서 B를 자세히 보면 1 4 6 7으로 연결된 선들을 살려야지 가장 길어지는 것을 볼 수 있다. 조금만 예제를 바...
[Baekjoon, 2143] 두 배열의 합
두 배열에 대한 모든 부분합을 미리 구한 다음, 한 배열을 정렬하고 이분탐색을 이용하여 답의 갯수를 찾으면 되는 문제이다.
[Baekjoon, 9527] 1의 개수 세기
정석적인 풀이인 자리수에 대한 누적합을 비트마스킹하여 풀지 않고 이진수의 1의 개수에 대한 규칙을 찾아 풀었다. 규칙은 노트에 이진수와 합과 숫자를 계속 끄적이다보니 알게되었다.
[C] DFS를 이용한 미로 맵 생성
C언어를 이용하여 랜덤 미로 생성 알고리즘을 구현했습니다. NxN 크기의 맵(N은 홀수)이 있을때 깊이우선탐색을 하며 미로를 생성합니다. 알고리즘은 다음과 같습니다.
[C] stack을 이용한 미로찾기 경로
학교 수업에서 c언어로 미로찾기 알고리즘을 구현했습니다. 스택을 직접 구현하여 이용했습니다.
[Baekjoon,9465] 스티커
먼저 방향을 정해야 한다. 방향은 왼쪽에서 오른쪽으로 진행하자. 만약 진행 중 현재 스티커를 선택한다면 오른쪽과 아래쪽에 붙어있는 스티커는 이용할 수 없다. 그러면 다음 스티커는 대각선 방향 스티커이다. 그런데 이 스티커 대신 이 보다 한 칸 오른쪽에 있는 스티커를 선택하는 것...
[Baekjoon,14891] 톱니바퀴
문제에서 핵심 내용은 아래의 두 가지이다.
[Baekjoon,2011] 암호코드
한 글자씩 복호화를 진행는데 현재 숫자를 가르키는 위치의 숫자가 10~26인 추가적인 경우를 고려하며 탐색해야 한다. 즉 현재 숫자에 대해 아래의 두 가지 경우로 탐색하면 되는데 이는 동적 계획법을 쉽게 적용할 수 있다. 한 개의 숫자를 복호화 숫자가 10~26인 경우 ...
[Baekjoon,5670] 휴대폰 자판
각 단어들을 트라이로 구현하여 해결하면 된다. 이때 타이핑을 해야하는 순간을 잘 생각해야 한다. 그 시점은 아래와 같다.
[Baekjoon,1002] 터렛
각 터렛이 공격할 수 있는 위치를 표시한 원들의 접점의 개수를 찾으면 된다. 이때 원이 외접하는지와 내접하는지를 고려하여 개산해야 한다.
[Baekjoon,13305] 주유소
현재 위치의 리터당 가격보다 낮은 도시가 나올 때까지 충전하여 이동한다. 더 낮은 가격의 도시가 나온다면 이곳에서 이곳보다 더 낮은 가격의 도시가 나올 때까지 이동한다. 이를 반복하여 마지막 도시에 도착하면 종료한다. 아래의 그림을 보면 이해할 수 있다. 비용이 5인 도시에서...
[Baekjoon,14725] 개미굴
무식한 방법
[Baekjoon,10775] 공항
새로운 비행기가 들어올 때마다 비행기의 번호와 같은 게이트에 도킹한다. 그런데 이미 해당 게이트에 다른 비행기가 도킹된 경우 하나 낮은 번호에 도킹을 시도한다. 이 과정을 반복하는데 1번 게이트까지 실패한 경우 더 이상 도킹할 수 없는 것이다.
[Baekjoon,1700] 멀티탭 스케줄링
현재 사용해야 하는 기기를 맞이했을 때 다음과 같은 세 가지로 행동을 분류할 수 있다. 꽂을 자리가 남는 경우 -> 현재 기기를 꼽는다. 이미 현재 기기가 꽂혀 있는 경우 -> 아무것도 하지 않는다. 하나를 뽑아야 하는 경우 a. 현재 꼽혀있는 ...
[Baekjoon,10266] 시계 사진들
시계를 회전하여서 두 시계가 일치 가능한지 찾아야 한다. 이는 시계 바늘 간의 간격이 모두 동일하다면 같다고 생각할 수 있다. 따라서 시계 바늘이 가르키는 방향을 정렬한 후 바늘 간의 간격을 얻어 두 시계의 바늘 간격들이 같은지 확인하면 된다. 이때 시계의 바늘이 가르키는 방향...
[Baekjoon,3109] 빵집
초기에 모든 경로를 DFS를 이용하며 만들었고 다음 두 가지의 경우에 따라 방문 여부를 표시했다.
[Baekjoon,1202] 보석 도둑
초기에는 무식하게 접근하였다. 가방의 용량을 오름차순으로 정렬하고 보석의 무게를 기준으로 오름차순으로 정렬했다. 그 이후 가방에 들어갈 수 있는 모든 보석들을 비교하며 가장 가치가 큰 보석을 가방에 넣었다. 이를 가방의 용량이 작은 것 부터 처리했다. 하지만 이 방법은 $300...
[Baekjoon,4354] 문자열 제곱
주어진 문자열 s가 부분 문자열 a로 최대로 몇 번 반복해서 이을 수 있는지 찾아야 한다. 예를 들어 문자열 $s=abaabaaba$가 있으면 이는 문자열 $a=aba$를 $3$번 이어 만들 수 있다.
[Baekjoon,2437] 저울
처음에는 모든 수의 조합을 만들어 찾으려 했으나 중량의 최대 합이 10억이어서 이는 포기했다. 그래서 어떻게 해결할지 고민하던 중 주어진 수열을 정렬해보니 방법이 떠올랐다.
[Baekjoon,1744] 수 묶기
큰 수를 서로 곱해야 더 큰 결과가 나올 것이다. 그리고 음수끼리 곱하면 양수가 되니 항상 음수는 음수와 곱하는 것이 최선이다. 여기서 0과 1이 중요한데 0은 음수 중 곱하지 않고 남은 하나의 수와 같이 곱하여 처리하면 되고 1은 아무 것도 하지 않고 그냥 더해야 한다.
[Baekjoon,2533] 사회망 서비스(SNS)
트리에서 최소한의 얼리 어답터를 배치하는 문제이다. 종만북의 GALLERY문제와 해결 법이 비슷하다. 손으로 풀다 보면 트리의 잎 노드에는 얼리 어답터를 배치하지 않는것이 결과를 최소화 할 수 있다는 것을 알 수 있다. 이때 문제에서 제시한 아래의 문구가 중요하다.
[Baekjoon,1080] 행렬
문제를 손으로 풀다보면 아래의 두 가지를 깨달을 수 있다.
[Baekjoon,1339] 단어 수학
백트래킹을 하며 모든 경우의 수를 탐색할 수 있다. 탐색 하며 더 큰 값이 나오면 계속해서 갱신해 나가는 것이다. 하지만 이보다 더욱 간단한 방법이 있다. 바로 그리디한 수학적 방법이다.
[Baekjoon,2213] 독립집합
트리의 루트에서 부터 DFS로 탐색하며 현재 정점을 선택하느냐 안 하느냐를 결정하여 최대 독립 집합을 구하는 문제이며 정점의 가중치가 있으니 정점의 개수가 아닌 정점의 가중치가 최대가 되는 독립 집합을 찾아야 한다. 독립 집합에 대한 자세한 설명은 이곳에서 볼 수 있다.
[Baekjoon,15681] 트리와 쿼리
트리 구조에서 DP를 이용하여 해결하는 문제이다. 주어진 정점을 서브트리로 했을 때 서브 트리의 정점의 개수를 반환하여야 한다. 이를 구현하기 위해서 루트에서 부터 DFS를 하였다. 서브트리의 정점 개수만 구하면 되므로 따로 트리구조를 형성하지 않아도 된다. ```cpp #inc...
[Baekjoon,2887] 행성 터널
자칫 잘못 생각하면 모든 행성을 서로 이어 간선을 형성하고 이 간선들로 최소 스패닝 트리를 찾아 해결할 것이다. 하지만 이러한 방법은 간선이 너무 많아 제한 시간 내에 해결할 수 없다. // 너무 많은 간선들로 인해 모든 정점을 탐색하다 시간초과가 난다. int V; int p...
[Baekjoon,1197] 최소 스패닝 트리
간선의 가중치 합이 최소인 스패닝 트리를 만들어야 한다. 이를 위해서 나는 크루스칼의 알고리즘을 이용했다. 크루스칼 알고리즘은 아주 간단하다. 선택 후 사이클이 되지 않는 간선을 선택한다. 이때 간선의 가중치가 작은 것부터 차례로 선택한다. 이를 최소 스패닝 트리가 될 때까지 ...
[Baekjoon,1967] 트리의 지름
트리의 지름을 찾기 위해서는 가장 멀리 떨어져 있는 두 노드를 찾아 두 노드의 거리를 구해야 한다. 이를 해결하는 방법은 먼저 루트에서 가장 멀리 떨어진 지점 $F$를 찾는다. 그 후 $F$를 루트로 두고 가장 멀리 떨어진 지점을 찾아 거리를 구하면 된다. 이에 대한 과정을 주어...
[Baekjoon,2618] 경찰차
경찰차의 위치와 처리해야 할 사건의 번호를 알면 둘 중 하나의 차량을 선택하여 더 작은 결과를 얻어내는 방향으로 선택해 나가며 결과를 얻으면 된다. 이를 초기에는 현재 경찰차 위치와 해결해야 하는 사건의 정보를 기준으로 부분 문제를 정의하여 해결하려 했다. 경찰차 위치와 현재 ...
[Baekjoon,14003] 가장 긴 증가하는 부분 수열 5
DP로 해결하기에는 너무 느리다. 따라서 이분 탐색을 활용한 방법(Baekjoon,12015 가장 긴 증가하는 부분 수열 2)으로 해결해야 한다. 하지만 문제는 $LIS$의 길이 말고도 실제 $LIS$를 출력해야 한다. 이에 대한 해결 방법은 직접 과정을 따라가다 보면 알 수 있...
[Baekjoon,17404] RGB거리 2
원형으로 되어있는 구조에서 집들의 색상을 어떻게 최소 비용으로 조합할지 찾아야 한다. 원형으로 되어있다는 것은 첫 번째 집과 마지막 집이 이어져 있다는 것이다. 이 때문에 첫 번째 집의 색상이 마지막 집의 색상에 영향을 준다. 따라서 첫 번째 색상이 어떻게 되어있냐에 따라 나머지...
[Baekjoon,1086] 박성원
이 문제는 주어진 숫자들로 조합을 하여 주어진 $K$로 나누어 질 수 있는 조합의 개수를 찾아 해결하는 문제이다. 이는 모든 조합을 탐색하며 해당 조합의 숫자가 $K$로 나누어 떨어지는지 찾으면 된다. 이때 주어지는 숫자의 개수가 15개이므로 비트 마스크를 이용하여 해당 숫자에...
[Codeforces] Dijkstra?
영어로 된 문제와 친해지기 위해 codeforces의 문제를 풀어봤다. 1900의 Difficulty를 가진 문제이며 다익스트라의 최단 경로 알고리즘을 이용해 실제 최단 경로를 출력하면 된다.
[Baekjoon,1219] 오민식의 고민
도시를 방문할 때 마다 이익을 얻거나 손해를 본다. 여기서 출발 도시에서 시작하여 도착 도시로 왔을 때 얻을 수 있는 가장 큰 돈의 액수를 구해야 한다. 이 돈은 사이클을 형성하여 무한대로 얻을 수 있다. 여기서 손해를 최소화 하는 경로를 찾아야 한다고 생각할 수 있다. 즉,...
[Baekjoon,1956] 운동
모든 정점을 찾으며 자기 자신으로 돌아오는 경로가 존재하는 정점 중에서 경로의 최소값을 찾아야 한다. 여기서 플로이드 알고리즘을 활용할 수 있다.
[Baekjoon,10217] KCM Travel
이 문제의 그래프는 음수 가중치를 가진 간선이 없는 그래프이다. 그리고 단일 시작점에서 도착 점 까지의 최단거리를 구해야 하므로 다익스트라의 최단거리를 구하는 알고리즘을 이용하면 된다.
[Baekjoon,2749] 피보나치 수 3
이 문제를 해결하기 위한 방법이 두 가지 정도 있는데 하나는 피사노 주기를 이용하는 것이고, 다른 하나는 행렬을 이용하는 것이다. 여기서는 행렬을 이용한 방법만 소개하겠다.
[Baekjoon,10830] 행렬 제곱
일단 행렬의 곱셈을 모른다면 winner blog : 행렬의 연산(곱셈)을 참고하자.
[Baekjoon,10942] 팰린드롬?
무식하게 접근 어떻게 부분 문제로 나누어 동적 계획법을 적용할 수 있을 지 많이 고민했다. 처음 접근은 동적 계획법을 적용하지 않고 무식하게 해결하는 것이었다. 주어진 구간 [s,e]에 대해 수열 perm[]이 팰린드롬인지 한 칸 씩 인덱스를 가운데로 모으며 판단하는 것이다. ...
[Baekjoon,1420] 학교 가지마!
이 문제는 각 위치를 정점으로 하고 시작 위치를 소스, 도착 위치를 싱크라고 했을 때 최소 컷을 구하면 되므로 최대 유량 최소 컷 정리 에 따라 최대 유량을 구하면 된다. 그런데 무작정 칸들에 대해 최대유량을 구하면 벽이 칸들을 잇는 길에 놓일 수 있다. 이때 간선을 막는 것...
[Baekjoon,1520] 내리막 길
첫 시작위치에서 시작하여 상하좌우 방향으로 이동가능한 경우 이동하다가 도착지점에 도착할 수 있는 경로의 개수를 찾아야 한다. 중복되어 계산되는 부분이 많으므로 메모이제이션을 적용하여 해결하면 된다. 이때 부분 문제를 아래와 같이 설정하면 된다. getRouteNum(y,x) = ...
[Baekjoon,11049] 행렬 곱셈 순서
모든 구간 [0,N-1]에 대해 최소 비용을 얻기 위해 문제를 잘게 쪼개야 한다. 이를 위한 방법은 각 구간에 대해 재귀적으로 중간을 나누어 쪼개는 것이다. 이는 아래와 같은 부분 문제를 정의하면 쉽게 구현 할 수 있다. dp(lo,hi) = 구간 [lo,hi] 에서 행렬 곱셈...
[Baekjoon,4195] 친구 네트워크
Union-Find 알고리즘을 이용하여 해결했다. 이는 상호 배타적 집합을 만들어 내는 자료구조이다. 자료구조에 대한 설명은 Heee’s 블로그에서 볼 수 있다.
[Baekjoon,1654] 랜선 자르기
해결 0부터 2^31-1까지 랜선의 길이를 이분 탐색했다. 현재 길이를 통해 n개의 개수를 채울 수 있으면 lo를 mid로, 채울 수 없으면 hi를 mid로 설정하는 방식이다.
[Baekjoon,12015] 가장 긴 증가하는 부분 수열 2
DP로는 안된다. 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. 이 문제는 수열의 길이가 최대 1,000,000 이므로 백준 11053번 문제의 해결 방법이었던 DP로는 해결할 수 없다. // 이 방식은 사용할 수 없다. int len, seq[MAX]...
[Baekjoon,1874]스택 수열
주어진 문제처럼 숫자를 1에서 부터 n까지 스택에 넣는데 이때 주어진 수열의 값이 나온 경우 pop해주면 된다. 만약 n까지의 수를 모두 연산한 후에 스택에 값이 남아있으면 수열을 만들 수 없기 때문에 빈 벡터를 반환하여 예외를 처리했다.
[Baekjoon,10816]숫자 카드 2
해결 시작하기에 앞서 이 문제는 입출력이 많기 때문에 cin, cout 보다 빠른 방식을 택해야 한다. 1. map container 이용 map을 이용하여 각 숫자 카드의 값이 key에 존재하면 증가시키고 없다면 map에 추가하는 방식으로 진행했다. ```cpp #include ...
[Baekjoon,11401]이항 계수 3
해결 첫 접근 이항 계수 정리 처음 드는 생각은 아래와 같은 이항 계수의 정리를 이용하는 것이다. 하지만 나머지 연산을 해야 하는데 분모가 있어 진행할 수 없다.
[Baekjoon,5014]스타트링크
해결 현재 층과 목표 위치까지의 최단 거리로 도달할 수 있는 방법을 찾으면 된다. 그렇기 때문에 BFS를 이용하면 된다. 너비 우선 탐색 시 큐에 현재 층과 몇 번 버튼을 눌렀는 지 같이 저장하며 탐색을 한다. 이를 이용하여 각 정점을 탐색하다 목표하는 위치가 나왔을 때 버튼을...
[Baekjoon,11066]파일 합치기
해결 초기에는 최단거리 알고리즘을 생각했으나 500개의 정점을 하나씩 줄이며 진행하기에는 너무 많은 양이어서 다른 방법을 찾아야 했다. 현재 파일과 다음 파일 중 합치거나 안 합치거나 진행해보려 했으나 진전이 없었다. 그렇게 찾아보던 중 이곳에서 알게 된 방법이 있었다.
[Baekjoon,9252]LCS 2
해결 LCS 길이 구하기 먼저 두 문자열의 최장 공통 부분 수열의 길이를 구하는 것이 우선이다. 구하는 방법은 문자열을 한 글자씩 확인하며 일치하는 경우 두 문자열 모두 다음 문자로 이동하고, 일치하지 않으면 둘 중 하나만 다음 문자로 이동한다. 이를 동적 계획법에 적용하면 반...
[Programmers]블록 게임
해결 여러가지 조건들을 유념하며 구현하면 되는 문제이며 간단한 아이디어로 구현이 깔끔해진다. 그 아이디어는 만들어 질 수 있는 크기 내에서 모든 칸을 계산하는 것이다.
[Programmers]단어 퍼즐
해결 문제에서 유념할 조건은 아래와 같다. 단어 퍼즐을 중복하여 사용할 수 있다. 단어 조각 길이는 5 이하이다.
[Baekjoon,14503]로봇 청소기
해결 주어진 로봇의 작동 방식을 그대로 구현하면 된다. 나는 객체로 구현하여 더욱 직관적으로 코드를 작성했다. 다른 방법으로는 DFS를 이용하여 유셩장 블로그처럼 재귀적으로도 구현할 수 있다.
[Baekjoon,14502]연구소
해결 이 문제는 크게 두 부분으로 나눌 수 있다. 하나는 “주어진 맵에서 벽을 어떻게 세우는가?” 이고, 다른 하나는 “바이러스를 어떻게 퍼뜨릴까?” 이다.
[Baekjoon,14499]주사위 굴리기
해결 너무 복잡하게 생각하면 안되는 문제이다. 우아한 코드를 작성하려고 어렵게 접근하면 더 어려워진다. 초기에는 어렵게 객체로 주사위를 표현하여 해결하려 했으나 실패했다.
[Baekjoon,14501]퇴사
해결 모든 상담에서 적절히 선택해 최고의 조합을 찾아내는 문제이다. 오늘이 day일 일때 day일차의 상담을 하느냐 안하느냐로 선택해 나가면 된다. 단순히 모든 방법의 수를 고려하여 코드를 작성할 수도 있다. 하지만 더욱 효율적인 방법이 있다.
[Baekjoon,14500]테트로미노
해결 초기에는 모든 도형을 상수 배열에 저장시켜서 반복문을 돌려야 하는 줄 알았다. 그러나 방법은 있었다.
[Baekjoon,3190]뱀
해결 이 문제는 위와 같은 이미지의 게임을 구현하면 되는 문제이다. 구현해야 할 부분은 아래와 같다. 뱀을 객체로 표현 변수: 현재 상태 위치 방향 꼬리의 위치 ...
[Baekjoon,12100]2048 (Easy)
해결 이 문제는 현재 상태에서 다음 상태로 4개가 만들어지는데 총 5번을 움직인 뒤에 만들어진 상태들 중 제일 큰 원소를 가진 상태의 원소의 값을 출력하면 된다. 즉, 현재 상태에서 기울였을 때 만들어지는 상태를 구현하는 것과 탐색을 통해 5번 기울이기를 했을 때 최대 값을 구하...
[Baekjoon,13460]구슬 탈출 2
해결 최단거리를 구해야 하므로 너비 우선 탐색을 통해 접근했다. 하지만 일반적인 BFS와는 다르게 다음 상태 정점에 접근하기 어려웠고, 중간에 탈출하게 되었을 때의 처리의 구현이 어려웠다.
[Baekjoon,2570]비숍2
해결 종만북의 BISHOP문제와 거의 동일하며 풀이 또한 비슷하다.
[Algospot]TRAPCARD
해결 교재에 나온 도미노 문제처럼 빈 칸들을 격자 그래프로 표현해보자. 그러면 칠해진 부분과 그렇지 않은 부분으로 나뉘어지는데 두 부분을 서로 매칭시키는 이분 그래프가 된다.
[Algospot]PROJECTS
주의 이 문제는 채점 사이트에 등록되지 않았기 때문에 저의 코드는 틀린 코드일 수 있습니다. 아래에 있는 예제만 통과한 코드입니다.
[Algospot]BLOCKGAME
해결 무작정 시도 현재 차례의 사람이 이기면 1을 반환하고 아니면 0을 반환하는 식으로 코드를 구현하려 했다. 하나라도 이기는 경우가 있으면 이기는 것, 즉 이기는 경우가 없으면 지는것이다.
[Baekjoon,2316]도시 왕복하기 2
해결 다들 visited와 같은 배열을 만들이 이미 경로가 형성된 정점을 처리하여 해결하려고 했을 것이다. 하지만 이러한 방법으로는 flow의 역방향을 통해 증가 경로를 찾지 못하기 때문에 다른 방법을 찾아야 한다.
[Baekjoon,1774]우주신과의 교감
해결 이 문제는 algospot 사이트의 LAN이라는 문제와 해결방법 이 유사하다. 크루스칼의 알고리즘과 프림의 알고리즘 중 나는 프림의 알고리즘으로 해결했다.
[Baekjoon,11726]2×n 타일링
해결 here 만큼 타일이 남았을 때 몇 가지의 방법으로 타일링을 할 수 있는지를 반환하는 count함수를 만들어 해결했다. 기저 사례로는 타일의 범위를 벗어난 경우와 타일이 완성된 경우이다. 메모이제이션을 이용하여 중복되는 계산을 없애는 것이 중요하다.
[Baekjoon,10256]돌연변이
해결 Aho-Corasick 알고리즘을 이용하여 해결했다.
[Algospot]WITHDRAWAL
해결 처음에는 r/c가 큰 것부터 철회하면 해결 할 수 있을 줄 알았으나 이 방법으로는 답을 구할 수 없다.