컴공과고씨

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 정리 컨베이어 벨트가 있음 벨트 구성은 이런식으로 벨트는 회전합니다. 올리는 위치에서 로봇을 올리고 내리는 위치에 로봇이 도착하면 로봇을 즉시 내립니다. 또한 벨트마다 내구도가 주어짐. 벨트 작동 순서 1. 벨트가 각 칸 위에 있는 로봇과 한 칸 움직임 2. 벨트에 먼저 올라간 로봇 부터 벨트가 움직이는 방향으로 로봇을 한 칸 움직임 2-1) 움직이는 조건은 다음 칸의 ..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 간단 정리 한 행렬이 있을 때 한 행으로 쭉 갈거나 한 열로 쭉 갈 수 있다면 그것은 길이다. 길의 개수를 세야함. 근데 각 좌표에는 높이가 있음. 높이가 다르면 경사로를 설치해서 지나갈 수 있음. 경사로 설치 조건 1. 높이 차는 1이여야함. 2. L이 주어지는데 높이가 낮은 쪽에 L개수 만큼 같은 높이로 좌표가 있어야 설치가 가능함. 3. 경사로는 곂쳐지면 안됨. 문제 해결 방법 일단 행렬이 있을 때 가로 길을..

https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 정리 강의를 녹화해야함. 강의 수 N개, M개의 블루레이에 저장. 이때 강의마다 시간이 주어지는데 강의는 순서대로 녹화해야함. 또한 강의 중간에 끊겨서 녹화하면 안됨. -> 한 강의는 한 블루레이에 끊어지지 않고 있어야함. 이때 블루레이의 크기를 구하는데 최소 크기를 구해야함. 문제 해결 방법 하나하나 크기를 정해서 비교하면 시간이 굉장히 오래 걸리게 됩니다. 그러므로 이분탐색을 이용하여서 시간 단..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제를 먼저 이해하면 탑이 서있을 때 오른쪽 탑부터 왼쪽으로 레이저를 쏴서 자신보다 높이가 같거나 높은쪽에 부딪치면 수신하는 탑이 되고 없다면 0을 출력하는 것이다. 내가 생각한 문제 접근 방식을 소개하면 일단 처음 입력 받은 탑들을 스택에 넣어준다. 스택에 넣어주는 이유는 오른쪽 탑부터 레이저를 쏘기 때문이다. 이 때 스택에 저장하는 값은 pair를 이용해서 첫번째는 탑의 높이 두번째는 순서를..

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 이 문제를 보고 일단 어떤 수를 제곱수로 나타내야 하니 어떤 수가 주어졌을 때 주어진 수보다 작거나 같은 제곱수 까지 구해서 배열에 저장해놓고 그 배열안에 수를 이용해서 합이 n이 되도록 찾는 식으로 풀어 주었다. 배열에 저장하지 않고 연산을 계속하면서 찾을 경우 당연히 연산 시간이 오래걸려 시간초과가 난다. 합이 n이 되도록 할 때 최소 개수의 수로 만들어야 ..

https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 떠올린 방법은 정렬하지 않고 일단 unique 함수를 사용해서 연속되는 수를 제거한다. (unique, erase를 잘 모른다면 https://hagisilecoding.tistory.com/53 여기서 공부하고 오면 편함) aabbbccb가있다면 unique함수를 정렬을 하고 써주면 연속되는 값이 쓰레기 값으로 가고 이것을 erase를 통해 지워주면 abcb가된다..

1주차 (03.27~04.02) 문제 문제명 난이도 참조 소요 시간 후기 23876 일곱 난쟁이 하 x 8 min x 35490 블랙잭 하 x 9min x 48439 셀프 넘버 하 x 11min x 48164 한수 중하 x 16min x 20086 N-Queen 중 백트래킹을 이용하여 푸는 문제라는 힌트 참조 힌트 보기전(1h) 본 후(1h) 총 2h 처음 백트래킹 알고리즘을 떠올리지 못하고 포문으로만 접근하려 함. 백트래킹 유형 문제임을 인지하고 다시 풀었음 10435 리모컨 중 x 1.5h 푸는 아이디어는 빠르게 생각해 냈지만 구현부분에서 채널 탐색 범위를 잘못잡아서 시간을 많이 씀. 2주차 (04.03~04.10) 문제 문제명 난이도 참조 소요 시간 후기 11720 숫자의 합 하 x 5min x 1..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 이해 이 문제는 숫자가 나열되어있을 때 자신보다 작은 숫자의 개수로 그 숫자를 바꾸어 주는 것이다. 예를 들면 1 -9 -7 4 4 8 -10 -10 -10 2 3 3 1 이렇게 숫자가 있을 때 정렬을 해주면 -10 -10 -10 -9 -7 1 1 2 3 3 4 4 8 이므로 -7보다 작은 수는 3개이므로 -7 -> 3으로 변하는 것이다. 문..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 이 문제의 경우 시간초과를 잘 통과해야하는 문제이다. 그러기 위해서는 해시맵을 사용해야하며 문제를 보면 번호를 주면 포켓몬 이름을 포켓몬 이름을 주면 도감 번호를 답해야한다. 하지만 해시맵은 Key, value가 있고 key값으로 value를 찾는건 빠르지만(포켓몬 이름(key)을 주었을 때 도감 번호(value)를 찾는) value(도감번호)로 key(포켓몬 이름) ..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제를 정리하면 땅 높이를 맞추어 주는 것인데 이제 땅을 쌓는건 1초, 깎는건 2초 걸리고 쌓을 때는 블록이 있어야 쌓을 수 있다. 최대높이가 256이기 때문에 땅을 0으로 고르는, 1로 고르는 ...... 256으로 고르는 시간을 각각 계산해서 비교해주는 식으로 풀었다. 위 방법을 brute force (브루트포스) 무차별 대입이라고 한다. 먼저 높이의 개수를 저장하는 hight 배열을 만들었..