분류 전체보기

문제 접근 입력을 굳이 2차원 배열로 받을 필요가 없다고 생각했다. 높이 데이터만 갖고, 답을 찾을 수 있기 때문에 입력으로 높이 값만 받았다. 범위를 지정하고, 무조건 성립하는 개념을 찾았다. 우선 가장 낮은 높이와 가장 높은 높이라는 정답이 나올 수 있는 범위를 지정했다. 그 뒤 일단 가장 낮은 높이까지 인벤토리에 넣은 뒤에 한 칸씩 기준을 올렸을 때, 시간 변화량이 양수가 되면 바로 전 높이가 최단 시간, 최대 높이라는 걸 알 수 있었다. 그 이유는 간단하다. 문제의 조건 중 하나가 '집터 아래에 빈 공간이 존재하지 않는다.'이기에, 바로 위 높이의 블록 개수는 지금보다 많을 수 없다. 따라서 현재 높이의 블록 개수만큼 '넣기'를 취소하고, 빈 공간만큼 '꺼내기'를 했을 때의 시간 변화량이 양수라면..

문제 접근 나무들을 정렬한 다음에 가장 높은 나무를 기준으로 자를 높이를 점점 낮춰가자고 생각했다. 나무를 정렬한 뒤, 가장 높은 나무부터 현재 확인하고 있는 나무와 그다음 나무의 높이 차이를 height, 그리고 현재 확인하고 있는 나무가 몇 번째로 높은 나무인지는 width로 두고 M과 비교해 가며 높이를 낮춰갔다. 최악의 케이스를 상정해 봤다. 최대 나무 개수가 100만이고, 하나씩 확인하는 시간 복잡도는 O(n)이니 제한 시간 안에 충분히 동작 가능하다. https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000..

문제 접근 문제 설명에 나온 개념을 정리했다. 문제에서 말하는 생성자란 무엇인지, 분해합이란 무엇인지, 내 나름대로 간단하게 정리했다. 최악의 케이스를 상정해 봤다. 1부터 최대 입력 값인 100만까지 하나하나 확인해 본다고 하면 시간 복잡도는 O(n)이다. 최악의 경우, 입력이 100만이라고 하더라도 제한 시간 안에 가능하다. 그래도 시간을 더 줄일 수 있는 방법이 있나 생각해 봤다. 최대 입력 값은 100만이다. 각 자릿수의 합이 가질 수 있는 최댓값은 N이 999,999일 때 각 자릿수의 합인 54이다. 따라서 N이 55 이상일 때, N-54 미만의 자연수가 만드는 분해합은 절대 N이 될 수 없다고 판단했다. 최종적으로는 N1과 N-54 중에 큰 값부터 N까지만 확인하도록 해서 시간을 조금이나마 아..

문제 접근 소수의 정의와 에라토스테네스의 체라는 개념이 떠올랐다. 소수의 정의는 1과 자기 자신을 약수로 갖는 수. 에라토스테네스의 체란 작은 수부터 하나씩 확인하며 소수가 아닌 수를 소거해 가며 소수를 찾는 방법. 일단은 에라토스테네스의 체를 찾아보지 않고 구현해보려고 함. 최악의 케이스를 상정해봤다. 수 하나하나에 대해서 소수인지 아닌지 판별하려면 O(n^2)이 걸린다. 입력의 최댓값이 100만이기에, 최악의 경우, 1조 번 연산하게 되기에 단순하게는 풀지 못한다. 결국 에라토스테네스의 체처럼 소수를 찾으려 하지 않고, 소수가 아닌 걸 거르는 방식으로 해결하고자 했다. Just do it! https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M..

문제 접근 산술 평균의 경우, 값을 입력받을 때마다 N으로 나눈 것들의 총합을 구해 반올림하자. 총합은 반올림을 위해 실수 자료형을 사용했기에, 모두 더하고 나누면 오버플로우가 발생할 수 있음. 중앙값의 경우, 단순히 입력받은 값 vector를 정렬해서 중앙값을 가져오자. algorithm 헤더의 sort 함수는 O(nlogn)이다. 따라서, N이 최댓값(500,000)이라고 하더라도 대략 3백만으로 충분히 시간 내에 해결 가능함. 최빈 값의 경우, 중복 횟수를 세는 vector를 만들어서 max_element 함수로 최빈값을 찾자. 최빈 값이 여러 개라면 max_element 함수가 가장 첫 번째 max 값의 iterator를 반환하므로, 첫 번째 iterator 다음부터 end까지 중 max 값과 같..

문제 접근 원하는 수열의 확인해야 되는 부분과 스택의 top을 비교한다. 값이 같다면, 스택을 pop 하고 정답에 '-'를 추가한다. 값이 다르다면, 증가하는 정수 값을 스택에 push하고 정답에 '+'를 추가한다. 증가하는 정수 값이 n보다 큰데, 접근 1의 비교 값이 다르다면 수열이 만들어질 수 없으니 "NO"를 출력한다. https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmic..

주의! 본 개발 일지는 제 입장에서 제가 생각하고 느낀 바대로 작성되었습니다. 혹여 껄끄러운 내용이 있더라도 팀의 의견이 아닌 개인의 의견이라는 점 유의해주세요 :) 01월 개발 계획 23년 1월의 개발 목표는 '본격적인 개발'이었다. 22년 12월에 개발을 위한 작업 리스트업을 잘 마쳐놨기에 전체적인 그림을 적당히 마무리하고, 이제는 정말로 '본격적인 개발'을 시작하고자 했다. 프로젝트 진행 타임 라인 01월 05일, 비정규 회의 (대면): 프로젝트 정리, 아이디어 피드백01월 07일, 정규 회의 (대면): 전투 규칙 공유, UI 시안 피드백01월 12일, 비정규 회의 (대면): 전투 규칙 아이디어 피드백, 로비 UX/UI 피드백01월 19일, 비정규 회의 (대면): 대기방 UX/UI 피..

발표 자료    2023년 01월 28일, 게임 제작 연합 동아리 BRIDGE에 제출한 2022-2학기 최종 발표 자료.     발표 당일, 개인적인 이슈로 총회에 참석하지 못하게 되면서, 팀원이 대신 발표를 했다. 그 과정에서 열심히 준비한 발표 자료가 일부 변경되고, 준비했던 내용은 발표하지 못해 아쉬웠다. 따라서 이 글은 평소에 하던 개인적인 기록에 겸해 '당시 준비했던 발표 자료를 발표했다면'이라는 생각으로 재구성해본 글이다.     실제 발표 자료는 여기에서 확인할 수 있다. 대학생연합게임제작동아리 브릿지 : 네이버 카페대학생연합 게임제작동아리 BRIDGEcafe.naver.com    발표 영상    본 영상은 앞서 언급했던대로, 개인적인 기록용이다. 따라서 필요 이상으로 공을 들이기보다는 만..