뺙이 개발자

20055번: 컨베이어 벨트 위의 로봇 문제 이해하는 데 너무 오래걸린 문제(왜이렇게 말을 어렵게 써놓은 건지......)문제 해석이 너무 힘들어서 별로 추천하고 싶지 않은 문제다 .., (나만 어려웠을 수도..) 우선 문제를 이해하기 위해서는 컨베이어 벨트, 벨트, 로봇 이렇게 3개가 각각 있음을 알아야 된다.컨베이어 벨트는 고정이고 그 위에 벨트가 내구도를 가지고 한 칸씩 이동을 하는 것이다. 처음에 내구도는 그대로 있는 줄 알았는데, 칸의 내구도는 벨트의 내구도를 의미하는 것이었다. 따라서 다음의 순서로 동작하게 된다. 1. 벨트와 로봇을 모두 한 칸씩 이동2. 로봇만 이동가능하다면 이동3. 올리는 칸이 0이 아니라면 올리기4. 내구도가 0인 칸의 개수가 K개 이상이라면 종료, 아니라면 1번으로 ..

ADsP 일주일도 안되게 바짝 공부했는데 합격해서 공부방법 공유해볼까 합니다!하루에 5시간정도는 썼던 것 같고, 시험과 가까워졌을 때는 더 많이 쓴 것 같아요. 참고로 저는 컴퓨터학부 전공입니다.그리고 ADsP 내용 중에선 대학교 AI 수업에서 회귀정도 깔짝 공부했고 + 1단원에 DB 정도가 원래 알고 있던 내용이었어요.나머지는 웬만하면 다 초면인 개념들이었어요. 0. 자료 수집너무 당황했던 게 정보처리기사나 SQLD는 인터넷에 기출이 많았는데,,인터넷에 기출이 없어서 놀랐던 거 같아요그래서 다들 공부방법은 공유를 해주시는데 기출은 공유해주시는 분이 거의 없드라고요?!아주 잘 찾아야 있다고 하더라고요근데 저는 못찾아서 그냥 책을 구매했습니다! 참고로 같이 시험 치뤘던 지인은 인터넷에서 아주 쥐잡듯이 뒤..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 풀이방법1) recursive함수의 인자로 r,c를 넘겨 검사한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; impor..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net '좌표압축'이라는 것을 해줘야하는 문제이다. 좌표압축은 이분탐색을 이용한 STL함수인 lower_bound를 이용하게 된다. 알고리즘의 아이디어는 위와 같다. 일단 배열을 입력받아 정렬을 해준다. 그리고 중복 원소를 제거해준다. 이 후, lower_bound를 이용하여 현재 값을 넣어도 정렬이 유지되는 곳 중에서 가장 왼쪽 위치를 찾는다. 이 위치..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net dp문제이므로 테이블 설정을 잘 해주어야 한다. d[a][b]=k : a부터 b 팰린드롬이라면 k=1, 아니라면 k=0 우선, a부터 a는 항상 팰린드롬이다. 추가로 길이가 1 차이나는 a와 a-1는 서로 값이 같다면 팰린드롬이 된다. 그리고 길이가 2 차이부터 n-1 까지 나는 숫자가 팰린드롬인지 검사해주면 된다. 시작점이 s 이고 끝점이 e라면 두 숫자가 같으면서, 시작점과 끝점을 제외한 가운데 숫자가 팰린드롬이면 s부터 e는 팰린..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net dp문제이므로 테이블 설정을 잘해줘야 한다. d[a][b]=k : (a,b)까지 만들 수 있는 가장 큰 정사각형의 한 변의 길이는 k이다. 그러기 위해선 지금 좌표를 기준으로 위쪽, 왼쪽, 대각선왼쪽을 볼 필요가 있다. (a,b)를 기준으로 위의 세 군데 중에서 1이 아닌 0을 갖게 되면 지금 나의 좌표에서 만들 수 있는 정사각형의 크기가 다시 1로 초기화된다. 그러니깐 현재 좌표를 기준으로 위,왼,대각선왼쪽에 영향을 받게 되는 것이다. 그래서 나머지 두 좌표가 아무..

https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net dp문제이다. dp문제이므로 테이블 설정을 잘 해줘야 한다. d[a] = b : a원을 만들 수 있는 방법의 수가 b개 라고 정의해주었다. 먼저, 3원을 만들어야하고 우리에겐 1,2,3원이 있다고 가정해보자. 여기서 포인트는 "가장 마지막에 해당 동전을 사용하여 금액을 완성시키는 과정" 이다. 1) 1원을 가장 마지막에 사용하여 금액을 완성시키기 위해서는 1원을 채우는 경우, 2원..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 1 = 1*1 2 = 1*1 + 1*1 3 = 1*1 + 1*1 + 1*1 4 = 2*2 5 = 2*2 + 1*1 6 = 2*2 + 1*1 + 1*1 7 = 2*2 + 1*1 + 1*1 + 1*1 8 = 2*2 + 2*2 9 = 3*3 이렇게 나타낼 수 있다. 그래서 d[1] = 1 d[2] = d[2-1]+1 = 2 d[3] = d[3-1]+1 = 3 d[..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 아주 유명한 dp문제이다. 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중에서 가장 긴 것을 찾아야한다. 부분 수열이 되어야하므로 공통되는 부분이 연속할 필요는 없다. 가능한 수열을 전부 각각 만들어 비교하게 되면 시간복잡도가 O(2^n*2^m) 으로 너무 느려서 dp를 이용해야한다. dp를 사용하게 되면 문자열의 길이가 n,m 일 때, 시간..

https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net dp문제이다. dp문제이므로 테이블 설정을 잘 해주어야 하고, 현재 무슨 값을 저장할 필요가 있는지 생각해야한다. 먼저, 몇 초가 지나갔는지를 저장해줘야 하고 현재까지 몇 번의 움직임이 있었는지를 저장해줘야한다. 그래서 d[a][b]=k : a초일 때, b번 움직인 경우 얻을 수 있는 자두의 최대개수는 k개 라고 설정해주었다. b번 움직였다는 사실을 통해 현재 몇번 나무에 위치해 있는지 알 수 있다. 1번..