LRU 알고리즘이 어디에 쓰이는 무엇인지 그리고 어떻게 구현하는지 개괄 정리해보겠습니다. background 운영체제라는 강의나 관련 서적을 읽었으면 절대 빠지지 않고 나오는 이 알고리즘은 자주 나오는 만큼 중요한 알고리즘이다. 어떤 공간에 여러 요소들이 꽉 차있다고 생각해보자. 근데 더 이상 자리가 없는데 그 공간에 새로운 것을 넣어야 한다면? 공간을 차지하는 무엇인가를 빼서 자리를 만든 후 넣어야 되지 않겠어요? 한정된 공간에 빼야할 요소를 정하는 알고리즘을 replace algorithm이라고 하며, 컴퓨터에서는 한정된 공간이 {메모리, 캐시, 저장공간}이 되며 요소들이 {스레드, 프로세스, 자원}이 될 수 있다. 운영체제에서는 저 한정된 공간을 알뜰하게 쓰는게 바로 효율성이기 때문에 굉장히 이 r..

https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 문제는 별 것 없다.. 문자열 중 가장 많이 포함된 문자 하나를 출력하면 된다. 일단 내 코드는 40ms.. 최적화? 그런거 신경 안 쓰고 쉬운 문제는 쉽게 푸는게 답이라고 생각하는 사람이라 넘겼다.. 그런데 채점 현황에서 c++17로 12ms대로 풀어버린 것을 봤다. 참을 수 없었다.. 그래서 리팩토링을 했지만 오히려 4ms나 더 늘어버려서 글을 남긴다. 왤까... 정말 왤까?.... 40ms 코드 - 이 함수는 들어오는 문자열..

🔗 문제 1034번: 램프 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net ✏️ 풀이 불을 하나 켤 때마다 모든 열을 돌면서 켜야 할 생각에 아주아주 막막했다. 발상을 못 해내서 도움을 받았다... 그래서 이해하기 위해서 풀이를 쓴다!!!!! ✔️ 단계1 정답은 열에 있지 않고, 행이다. 행에 위치한 램프가 모두 켜졌는지 (행 완성) 아닌지가 정답을 좌우한다. 만약에 여러 행이 주어졌을 때 중복되는 행이 있다고 생각해보자. 어딜 켜든 똑같이 생긴 행들은 함께 상태가 바뀐다. 만약 똑같이 생긴 행1,2,..

🔗 문제 17472번: 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 제한 1 ≤ N, M ≤ 10 3 ≤ N×M ≤ 100 2 ≤ 섬의 개수 ≤ 6 ✏️ 풀이 ✍️ 문제 정리 다리를 설치해서 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자. [변수] NxM 맵 바다 0 땅 1 [다리 설치 조건] 다리는 바다에만 건설할 수 있다. 다리의 방향은 한 방향이다 다리의 길이는 2 이상이다. 다리의 양끝은 인접한 바다 위에 있어야 한다. (섬과 닿는 부분은 길이로 치지 않는다)..

🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com ✏️ 풀이 실수한게 많아서 시간을 들여 풀이를 써보고자 한다. 문제 내용 도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M, 도시의 정보가 주어진다. 이때, 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾고, 그 때의 홈방범 서비스를 제공 받는 집들의 수를 출력하는 프로그램을 작성하라 비용(cost ) : (i*i) + (i-1) * (i-1) // i가 범위일 때 수익(profit) : 범위 내의 집의 수(cnt) * M 손해를 보지 않으려면 아래 조건을 만족해야 한다. cost -..

🔗 문제 17069번: 파이프 옮기기 2 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net ✏️ 풀이 맨 처음 맵에 파이프가 가로로 있다. 끝점이 (0, 1) 파이프가 있을 수 있는 상태 : type {가로, 세로, 대각선} 각 타입에 따라 옮길 수 있는 조건이 있다. 문제를 잘 읽고 예제도 잘 보자. 문제를 잘 안 읽으면 예제 5번이 이해가 안 갈 수 있다. 아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어..

🔗 문제 15683번: 감시 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 입력 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. CCTV의 최대 개수는 8개를 넘지 않는다. 출력 첫째 줄에 사각 지대의 최소 크기를 출력한다. ✏️ 풀이 먼저 문제 정리 부터 한다. [맵이 가질 수 있는 상태] EMPTY : ..

🔗 문제 2636번: 치즈 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net N, M ≤ 100 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게..

🔗 문제 2467번: 용액 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net ✏️ 풀이 문제에서 보아야 할 것은 이미 용액이 "정렬된 상태 "인 것이다. 더 해야 할 용액도 2개다 싶어서 투포인터를 떠올렸다. 양 끝을 start, end라는 변수로 가리키며 그 합을 sum에 저장해 주었다. 이때 값은 오름차순 정렬이므로 start는 가장 작은 값(0 위치), end는 가장 큰 값 (N-1 위치)을 가리킨다. 만약 sum이 0이라면 더 이상 진행할 필요가 없다. 만약 sum < 0 이라면 작은 값을 가리키는..

🔗 문제 21609번: 상어 중학교 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 🖍 풀이 6달전에 푼거보다 개선되어서 다시 올리는 풀이 ✌🏻 문제를 읽고 코드 흐름을 간단하게 정리해보자. while(flag) { //1. 블럭 그룹들 찾기 //2. 조건에 맞는 블럭 제거하고 점수 얻기 // => 블럭 없으면 종료 flag = false //3. 아래로 중력 작용 //4. 반 시계 방향으로 회전 //4. 아래로 중력 작용 } 조건 정리 ✔️ 맵의 상태는 3가지의 블럭 종류와 빈 칸으로 이루어진다. enum..