개발새발 로그

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 효율성 문제이다. 투포인터를 이용해서 조건에 맞는 수열의 부분합을 찾는 것이다. 📋풀이방법 1. lt와 rt를 사용해야하므로 선언한다. - lt는 0으로 초기화해주고, rt는 for문을 이용해 N까지 증가하면서 순회한다. 2. 0 ~ N까지 순회하면서 result 변수 안에 주어진 수열 arr에서 arr[rt]를 하나씩 누적해본다. 3. 만약 result가 S보다 크거나 같다면 wh..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS 참고 https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Comm..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이전에 토마토문제에서 3차원배열을 추가한 것이다. 📋풀이방법 1. 처음에 익은토마토의 위치를 저장한다(well배열) -> 이때 좌표에 0을 추가해서 저장한다(며칠이 걸렸는지를 위해) -처음에 안익은 토마토의 갯수를 세놓는다.(none_well) -visited도 3차원 배열로 선언해줘야한다. 2. [시간초과 주의] well배열의 idx가 well의 length만큼 되었을 때..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 📋풀이방법 1. 상하좌우 검사 L명이상 R명이하인지 2. DFS를 통해 연합배열에 삽입, visited활성화로 중복 탐색 방지 3. 연합배열안에 든 좌표끼리 연합공식으로 인구수를 나눠서 넣음 4. 다시 처음([0,0]) 나라부터 검사 -인구수가 바뀌었으니까 🤟내 제출 const fs = require("fs"); const filePath = process.platform === "..

https://www.acmicpc.net/problem/14500 📋풀이방법 1. 먼저 우리가 사용하는 DFS가 4까지 뻗어나간다고 했을 때 4가지의 테르미노는 회전과 대칭인 경우를 모두 탐색가능하다. 2.하지만 아래의 도형같은 경우는 DFS로 탐색이 안되므로 따로 탐색해야한다. 3. 위 도형같은 경우는 한 점을 중점으로 사방탐색을 하면된다. 사방 탐색을 하면서 3가지의 경우가 생기는데 아래와 같다. 📝코드 풀이 방식 1.모든 좌표를 순회한다 (i,j) 2. 좌표를 순회하면서 방문표시를해야한다(사방탐색시 왔던 곳은 다시 탐색할 수 없도록) 3. 좌표 하나씩 순회하면서 DFS(4가지 도형)와 otherFind(ㅓㅏㅜㅗ)를 수행한다 4. DFS -DFS는 좌표를 4개 탐색했을 때 종료한다(깊이가 4) -방..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 📋풀이방법 1. 현재 칸이 청소되지않은 경우 청소한다. 2-1. 90도 회전하고, 그 앞의 구역이 청소되지않은 구역이면 전진한다. - 체크는 0번으로 초기화해준다 2-2. 90도 회전하고, 그 앞의 구역이 청소가능한 구역이 아니면 체크 후 90도 회전한다 3. 체크가 4번이 되었다면 바라보고 있는 방향에서 뒤쪽의 구역을 확인한다 4-1. 만약 뒤쪽..

연구소 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 82941 47677 26485 54.809% 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 2 0..