기록장

✏️ 문제 분석https://www.acmicpc.net/problem/1283 각 단어 또는 문장에서 문자를 단축키로 지정한다.첫 문자 혹은 첫 글자를 지외한 문자에서 지정할 때, 지정된 단축키를 출력하라.✏️ 구현 아이디어✏️ 알고리즘✏️ 시간 복잡도✏️ 정답 코드

✏️ 문제 분석https://www.acmicpc.net/problem/11060 N개의 일렬로 놓여진 칸 위에서 점프를 한다.가장 왼쪽 끝에서 가장 오른쪽 끝으로 가려면 최소 몇 번 점프해야 갈 수 있는가?한 번에 점프 가능한 횟수는 현재 있는 칸에 적힌 수이다.✏️ 구현 아이디어현재 칸에 다다르기 위한 최소 점프 횟수 + 1을 현재 칸에서 이동할 수 있는 모든 곳에 저장하는 것을 반복한다.단, 최소값만 저장한다.✏️ 알고리즘dp 동적 계획법✏️ 시간 복잡도모든 칸을 한 번만 방문하므로 탐색의 시간 복잡도는 O(N)탐색할 때마다 비교하는 연산은 O(1)N은 최대 1,000이므로 시간 안에 연산 가능하다.✏️ 코드 설계arr에 입력값을 받는다.최소 몇 번의 점프만에 도달할 수 있는지 저장할 dp배열을 모..

✏️ 문제 분석https://www.acmicpc.net/problem/2564 블록의 가로, 세로 길이, 상점 위치, 동근이의 위치가 주어질 때동근이의 위치와 각 상점 사이의 최단 거리의 합을 출력하라.✏️ 구현 아이디어블록의 경계선을 따라 이동하므로 1차원 거리로 치환하여 처리할 수 있다.시계방향으로 직사각형 경계를 따라 각 위치의 1차원 거리를 계산한다. (북, 동, 남, 서)동근이 위치와 가게 위치 사이의 최단 거리는 '두 거리의 차이' 또는 '전체 둘레-두 거리의 차이' 중 더 작은 값이다.✏️ 알고리즘구현✏️ 시간 복잡도최단 거리 계산하는 과정에서 시간 복잡도는 O(N)이다. N은 최대 100이므로 시간 안에 연산 가능하다.✏️ 코드 설계입력 받기직사각형 전체 둘레 total 계산각 가게 위치..

✏️ 문제 분석https://www.acmicpc.net/problem/13702K명의 사람들에게 N개의 주전자로 막걸리를 최대한 균등하게 나누어줄 때,막걸리를 나눠줄 수 있는 최대용량을 구하는 문제이다.✏️ 구현 아이디어막걸리의 용량이 최대 2^31-1보다 작거나 같은 자연수가 될 수 있기 때문에막걸리의 최대 용량을 찾을 때 이분 탐색을 사용하는 게 적절해보인다. start=1, end=2^31-1로 설정하고N개의 주전자에서 현재 막걸리 용량으로 모든 사람에게 균등하게 나눠줄 수 있다면막걸리 용량 탐색 범위를 큰 쪽으로,균등하게 나눠줄 수 없다면 탐색 범위를 작은 쪽으로 조절한다.✏️ 알고리즘이분 탐색 알고리즘✏️ 시간 복잡도이분 탐색 O(logN)마다 주전자 수 N만큼 방문하며 사람 수를 계산해야 하..

✏️ 문제 탐색https://www.acmicpc.net/problem/25418 정수 A에 1을 더한다.정수 A에 2를 곱한다.두 연산을 이용하여 A를 K로 변경할 때, 최소 연산 횟수를 구하는 문제이다.✏️ 구현 아이디어모든 경우를 완전 탐색으로 찾는 경우 시간 복잡도는 O(2^N)이다.A와 K가 최대 1,000,000이므로 최대 연산은 2^1,000,0002^10=약 1,000이므로 2^1,000,000은 제한 시간(1초) 안에 연산할 수 없다. A가 K가 될 수 있는지 판단하려면 1을 더하고 2를 곱하면서 모든 경우를 찾는 수밖에 없다.하지만 반대로 K에서 1을 빼고 2를 나누면서 A가 될 수 있는지 판단한다면 불필요한 경로를 배제할 수 있다. 예를 들어 7이 77이 될 수 있는지 판단한다면 7에..

✏️ 문제 탐색https://www.acmicpc.net/problem/2467 산성 용액(1~1,000,000,000 양의 정수)알칼리성 용액(-1~-1,000,000,000 음의 정수) N개의 용액 중 두 개의 서로 다른 용액의 합이 0에 가장 가깝게 만들려고 한다.이때 두 용액을 출력하라.✏️ 구현 아이디어용액이 최대 100,000개일 때 그 중 2개의 용액을 선택하는 경우는 100,000_P_2 = 100,000*99,999이다.모든 연산을 제한 시간(1초) 안에 수행할 수 없다. 따라서 용액 2가지를 찾을 때 이분 탐색을 사용해보자. 각 N개의 용액 마다 자신을 제외한 N-1개의 용액과 짝을 지은 후합해서 0에 가장 가까운 값이 무엇인지 구한다. 예)5-99 -2 -1 4 98 N개의 용액이 이..

✏️ 문제 탐색https://www.acmicpc.net/problem/2805 N개의 나무를 절단해서 윗부분을 가지고 가려고 한다.목재 절단기 높이를 최대 얼마로 정해야적어도 M미터의 나무를 가져갈 수 있는지 구하는 문제이다.✏️ 구현 아이디어나무의 수는 최대 1,000,000개, 나무의 높이는 최대 1,000,000,000이므로 브루트 포스를 사용하면 나무 높이가 K(1시간 복잡도가 적은 이진탐색을 사용하자. 4 720 15 10 17이진 탐색으로 찾는 값은 목재 절단기의 높이 hh는 최소 1, 최대 1,000,000,000이므로start=1, end=1,000,000,000, mid=(1+1,000,000,000)/2 목재 절단기의 높이가 h일 때가져갈 수 있는 나무의 길이 len가 M보다 크다면 ..

✏️ 문제 분석https://www.acmicpc.net/problem/11663 일차원 좌표 상에 점 N개, 선분 M개가 있을 때각각의 선분에 점이 몇 개 있는지 구하는 문제이다.✏️ 구현 아이디어브루트 포스는 시간 초과브루트 포스를 사용하면각 M개의 선분 마다 점이 몇 개 있는지 찾아야 하고점의 개수는 1~N이 될 수 있다.그래서 시간 복잡도가 O(M*N) 만약 점이 10억개가 있고 선분이 1부터 10억까지의 길이라면선분이 한 개만 있어도 10억번의 연산이 필요하다. 이분 탐색으로 풀어보자5 51 3 10 20 301 1020 603 302 154 8처음에는 이분탐색 대상을 뭘로 해야 좋을지 떠오르지 않았다.이전 문제처럼 구해야 할 대상인 '선분 위 점의 개수'로 두고 풀려니 어려웠다. 1. 우리는 ..

✏️ 문제 분석https://www.acmicpc.net/problem/17266 길이가 N인 굴다리에 가로등 M개를 설치한다.가로등 높이가 H이면 왼쪽으로 H, 오른쪽으로 H만큼 주위를 비출 수 있다.최소한의 높이로 굴다리 전체를 밝히고자 할 때, 가로등의 최소 높이를 구하는 문제이다.✏️ 구현 아이디어브루트 포스는 시간 초과우리가 구해야 하는 것은 가로등 높이의 최소값이다.가로등 높이를 h라고 하면, h가 될 수 있는 값은 1~N이다. 브루트 포스로 푼다면h가 1일 때, 2일 때, ..., N일 때 굴다리 전체를 밝힐 수 있는지 가로등 마다 확인해야 한다. 가로등 개수는 M개 이므로 전체 시간 복잡도는 O(N*M)이다. 최악의 경우 100,000*100,000번 연산이 필요하다.따라서 탐색 시간을 더..

✏️ 문제 분석https://www.acmicpc.net/problem/13335트럭 n개가 다리를 건너감트럭 순서 변경 불가 다리 위에 트럭 w대가 동시에 올라갈 수 있음다리 길이 w 트럭은 1 단위 시간에 1 단위 길이 만큼 이동할 수 있음다리 최대 하중은 L 모든 트럭이 다리를 건너는 최단 시간을 구하는 문제✏️ 구현 아이디어4 2 10 //n w L7 4 5 6 //트럭의 무게1. 차례로 트럭 보내기트럭의 순서를 바꿀 수 없으므로앞에서부터 하나씩 트럭을 다리에 보내야 한다. 먼저 무게 7인 트럭을 보낸다. 2. 다리의 하중(L)을 넘지 않는지 확인다리에 최대 2개의 트럭을 올릴 수 있으므로다음 트럭인 무게 4인 트럭을 보낼지 말지 결정해보자. 다리의 하중(L)을 넘으면 못 보낸다.7+4 > 10 ..