목록전체 글 (123)
풀이 보관함
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 코드 - 이 함수는 들어오는 문자열..
🔗 문제 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번이 이해가 안 갈 수 있다. 아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어..