CS 요모조모

Binary Search (이분 탐색 / 이진 탐색) 정렬된 배열에서 특정 값을 찾는 알고리즘 시간복잡도 O(logN) 알고리즘 이분 탐색은 내가 찾고자 하는 값(key)과 배열의 중간 값을 비교한다. 이 때, key가 더 크다면, 중간 값 이후의 값들만이 탐색 대상이 된다. 반대로, key가 더 작다면, 배열의 중간값 이전의 범위가 다음 탐색의 범위가 되는 것이다. 이렇게 탐색의 범위를 1/2씩 줄여 나간다. (-> 시간복잡도가 logN이 되는 이유) lo 와 hi의 초기 값은 각각 0, arr.size()-1 이다. 중간 인덱스 구하기 mid = (lo + hi) / 2 내가 찾는 값과 중간 값(중간 인덱스에 위치한 값) 비교하기 arr[mid] vs key 비교 결과에 따라 다음 탐색 범위 정하기 ..

2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 접근 방식 접근 1 ≤ N ≤ 30 이므로, 3x1부터 3x30 타일에 대한 경우의 수를 arr 배열에 저장하고, arr[N] 값을 출력한다. 부분 문제를 해결하기 위하여 점화식을 세워보자. 우선, arr[0]=1 이고, 홀수인 i에 대해서는 경우의 수가 모두 0이다. 1. i=2 3x2 타일에 대하여 3가지 경우의 수가 존재한다. 2. i=4 a. 3x4 는 3x2 옆에 3x2 타일을 붙인다고 ..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직..

본 글은 건국대학교 알고리즘 동아리 AlKon 스터디 5조에서 진행된 발표 내용입니다. 11060 점프 점프 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 시간 제한 입력 범위 1초 N, A(N개의 수) 1 ≤ N ≤ 1000 // 1 ≤ A ≤ 100 1xN 크기의 배열에서, i 번째 칸에 적힌 수를 Ai 라고 할 때, 해당 칸에서 오른쪽으로 Ai칸 이하만큼 점프할 수 있다. 가장 왼쪽 끝에서 오른쪽 끝으로 갈 때, 점프 횟수의 최솟값을 구하여라. 접근법 점프 횟수의 최솟값을 구해야 하므로, dp..

1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 라이트모드에서 봐주세요! 다크모드에 이상하게 표시되는 문제가 있어 글자색을 검정으로 설정해두었습니다 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 원숭이는 좀 특이한 원숭이였다. 어떤 것도 꿰뚫어 볼 수 있는 날카로운 눈을 가진 기이한 원숭이였따. 부드러운 눈을 가진 멍멍이는 언제나 날카로운 눈을 가진 원숭이를 부러워했지만 한편으로는 매우 질투했다. 어느 날 멍멍이는 원숭이의 날가로운..

내가 기억하려고 적는 코드 블럭 배경 변경 방법 hELLO 스킨 아래 링크에 다운로드 방법 및 여러 이슈들에 대한 내용이 있다. 댓글에 질문 남기면 친절하게 답변도 해주시지만, GitHub issue 먼저 살펴보는 것이 좋다. hELLO 티스토리 스킨을 소개합니다. hELLO 스킨은 본래 기능의 많이 없었다가, 티스토리 블로거 여러분의 호응에 힘입어 기능의 추가와 함께 업데이트를 여러 번 하게 되었습니다. hELLO 1.0 때와 비교하면 비교할 수도 없을 만큼의 기 pronist.dev 코드 하이라이팅 테마 적용하기 다 좋은데,, 코드 블럭의 배경이 하얗다. 보기 불편하니 바꿔보겠다. 사실은.. 2023.07.07 update hELLO 스킨은 코드 하이라이팅 기능을 제공하며 하이라이팅 테마 또한 포함하..

24041번: 성싶당 밀키트 첫 번째 줄에 $N, G, K$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번째 재료에 대한 정보인 부패 속도 $S_i$, 유통기한 $L_i$와 중요한 재료인지를 나타내는 www.acmicpc.net 문제 인스타 빵타쿠들의 꾸준한 사랑을 받는 베이커리 은 수현이가 그동안 쌓아온 노하우를 바탕으로 밀키트 사업에도 진출했다! 이제 성싶당의 맛을 집에서도 즐길 수 있다! 이 소식을 놓칠 리 없는 빵타쿠 한별이는 바로 성싶당에 달려가 밀키트를 사 왔다. 그러나 문제를 푸느라 바쁜 한별이는 깜빡 잊고 유통기한 안에 밀키트를 먹지 못했다. 눈물을 머금고 밀키트를 버리려고 포장을 뜯은 순간 한별이는 재료마다 유통기한이 다르다는 것을 발견했..

황당하다.. 코드 두 줄 수정하고 푸쉬했는데 갑자기 오류가 떴다. 문제 처음 보는 에러 메시지여서 여기저기 검색해보니, GitHub 서버 문제라고 한다.. 아래 링크에서도 실시간으로 몇십분째 동일한 문제에 대하여 호소하고 있다..! 앞으로 같은 문제가 발생하면 들어가보면 좋을 것 같다. `remote: fatal error in commit_refs` does not explain what's wrong · community · Discussion #15823 Story I'm debugging a number of flows involving GitHub. Actual Results remote: fatal error in commit_refs Expected results A human readabl..