목록2024/04 (6)
풀이 보관함
https://www.acmicpc.net/problem/10871 10871번: X보다 작은 수첫째 줄에 N과 X가 주어진다. (1 ≤ N, X ≤ 10,000) 둘째 줄에 수열 A를 이루는 정수 N개가 주어진다. 주어지는 정수는 모두 1보다 크거나 같고, 10,000보다 작거나 같은 정수이다.www.acmicpc.net 그냥 러스트 연습용으로 한번 풀어봤다. 러스트 입출력이 너무 힘들어서 사용자의 입력을 받는 용도로 쓰는 건 아닌 것 같다.코드도 길고 알고리즘에서는 C++보다 매력있는 언어는 확실히 아닌 듯 절대로 내가 여러줄에 걸친 입력을 받다가 빡친게 아니고 .. 절대로.. use std::io::{self, Write};fn main() { ..
🔗 문제 16946번: 벽 부수고 이동하기 4 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net ✏️ 풀이 맵에 저장되는 상태는 WALL, EMPTY로 2가지이다. WALL는 부술 수 있는 대상으로 WALL 위치 포함해서 갈 수 있는 주변 EMPTY의 개수가 필요하다. > EMPTY 그룹핑 WALL마다 BFS 돌리면 당연히 시간초과다. 미리 이중포문으로 맵을 돌면서 EMPTY을 그룹핑해주었다. 순회하며 만난 순으로 group_idx를 주었고, 기존 map에다가 -group_idx를 심어주었다..
Function 과 apply() T : input type R : return type background 기본적으로 자바는 타입이 ‘기본형’과 ‘객체형’이 있다. 그냥 기본형이 아닌건 다 객체다. 📌 기본형 (Primitive Type) - 논리 : boolean - 문자 : char - 정수 : byte, short, int, long - 실수 : float, double 함수가 객체라면 다른 객체들처럼 컨테이너에 저장할 수 있어야 하는게 아닐까? 그런데 클래스 안에서 선언하는거 이외에 함수를 객체로써 사용을 하시나요? C++에서는 함수 객체 개념을 위해 std::function, std::find가 있는데 Java는 어떨까?! Function (java.util.function) Function ..
🔗 문제 12851번: 숨바꼭질 2 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이 문제는 전에 풀었던 숨바꼭질, 이모티콘이랑 유사하다. 다른 점이 있다면 최소 연산 횟수 뿐만 아니라 이 조건을 만족하는 ‘경우의 수’도 포함하여 출력해야 한다. ✏️ 풀이 기본접근법은 소개했던 문제들은 특정 알고리즘을 떠올려야 하는게 키 포인트였다면, 이 문제는 더 나아가 경우의 수를 어떻게 포함할지 고민하는게 포인트다. ((스포)) 이 문제는 BFS로 풀어야 하며, queue에 있던 원..
LRU 알고리즘이 어디에 쓰이는 무엇인지 그리고 어떻게 구현하는지 개괄 정리해보겠습니다. background 운영체제라는 강의나 관련 서적을 읽었으면 절대 빠지지 않고 나오는 이 알고리즘은 자주 나오는 만큼 중요한 알고리즘이다. 어떤 공간에 여러 요소들이 꽉 차있다고 생각해보자. 근데 더 이상 자리가 없는데 그 공간에 새로운 것을 넣어야 한다면? 공간을 차지하는 무엇인가를 빼서 자리를 만든 후 넣어야 되지 않겠어요? 한정된 공간에 빼야할 요소를 정하는 알고리즘을 replace algorithm이라고 하며, 컴퓨터에서는 한정된 공간이 {메모리, 캐시, 저장공간}이 되며 요소들이 {스레드, 프로세스, 자원}이 될 수 있다. 운영체제에서는 저 한정된 공간을 알뜰하게 쓰는게 바로 효율성이기 때문에 굉장히 이 r..
https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 문제는 별 것 없다.. 문자열 중 가장 많이 포함된 문자 하나를 출력하면 된다. 일단 내 코드는 40ms.. 최적화? 그런거 신경 안 쓰고 쉬운 문제는 쉽게 푸는게 답이라고 생각하는 사람이라 넘겼다.. 그런데 채점 현황에서 c++17로 12ms대로 풀어버린 것을 봤다. 참을 수 없었다.. 그래서 리팩토링을 했지만 오히려 4ms나 더 늘어버려서 글을 남긴다. 왤까... 정말 왤까?.... 40ms 코드 - 이 함수는 들어오는 문자열..