풀이 보관함

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를 심어주었다..

🔗 문제 12851번: 숨바꼭질 2 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이 문제는 전에 풀었던 숨바꼭질, 이모티콘이랑 유사하다. 다른 점이 있다면 최소 연산 횟수 뿐만 아니라 이 조건을 만족하는 ‘경우의 수’도 포함하여 출력해야 한다. ✏️ 풀이 기본접근법은 소개했던 문제들은 특정 알고리즘을 떠올려야 하는게 키 포인트였다면, 이 문제는 더 나아가 경우의 수를 어떻게 포함할지 고민하는게 포인트다. ((스포)) 이 문제는 BFS로 풀어야 하며, queue에 있던 원..

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,..

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

🔗 문제 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..

🔗 문제 23290번: 마법사 상어와 복제 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net ✏️ 풀이 일단 이 문제는 내가 무려 밍기적 거리는 시간 포함해서 2주 동안 못 풀고 있던 것입니다. 이유는 예제 4, 5, 8에서 오답이 나와서, 다음은 예제 5번이 안 나와서. 총 2번의 대수정을 거쳐서 메모리 2028KB, 0ms로 문제로 맞았습니다!! 를 보게 됐다. 풀이 안 쓰려고 했는데 나한테도 도움될 것 같아서 오랜만에 자세히 써보고자 한다.. 문제를 읽으면 알겠지만, 간단하..