굥굥

문제의 포인트는 CBD 가 스킬트리라면 C, CB, CBD는 가능하지만 B , D, DC, BC 등은 불가능 하단 것이다. 쉽게 문제를 풀기위해서 스킬트리에 있는 스킬들만 순서대로 저장하는 벡터를 만들었다. 스킬트리에 있는 스킬들만 저장하므로 저장된 스킬들이 주어진 스킬트리와 같은 순서를 띄는지만 보면된다. ["BACDE", "CBADF", "AECB", "BDA"] 가 있을 때 스킬트리의 스킬들만 저장하면 ["BCD", "CBD", "CB", "BD"] 가 될 것이다. 저장한 스킬 트리의 길이에 맞춰 CBD를 비교하여 동일하면 answer값을 올리면 된다. #include #include #include using namespace std; int solution(..

works 벡터에 들어있는 값을 최대한 균등하게 만들어 주는 것이 포인트인 문제이다. 어제 푼 문제와 비슷하게 n이 works.size() 보다 더 클 경우에 벡터의 모든 요소에 n/size 한 몫만큼을 빼주었는데 문제가 생긴다. 질문하기에 있는 반례는 다음과 같다. 위의 상황에서는 내가 생각한 접근법이 맞지 않는다... 무조건 가장 큰 원소에 접근해서 값을 빼주고 싶은데 말이다. 그래서 생각해 낸 방식이 우선순위 큐를 이용한 방식이다. 무식하게 우선순위 큐를 만들고 큐의 top에 접근해서 하나씩 빼주고 0이 아니면 다시 넣어주었다. 이렇게 하면 문제를 쉽게 풀 수 있다. n이 1,000,000 이 최대 값이라 걱정을 했으나,, 어짜피 n은 한번만 돌면 되므로 그냥 써도 시간문제는 생기지 않..

자연수 집합의 합이 s 인 값중 곱이 최대인 집합을 찾는것이 포인트이다. 최대의 집합은 집합끼리의 차가 크지 않을때 이다! 따지면 다음과 같다. s 가 2 일때 8은 4,4 9는 4,5 10은 5,5 같은 식이 된다. 만약 s가 3이라면 9는 3,3,3 10은 3,3,4 11은 3,4,4, 12는 4,4,4 ... 가 된다. 이렇게 나열하면 규칙이 보이게 된다! s를 n으로 나눈 몫을 s의 개수만큼 벡터에 넣는다. 그리고 s%n 이 0이 아닐때는 나머지를 1씩 쪼개서 벡터의 끝부분에서부터 넣어주면 된다. s 가 3이고 n이 11 일 때는 { 3, 3+1, 3+1 } 이 되는 것! 규칙을 찾으면 쉬운 풀이를 찾을 수 있다. 자연수 n 개로 이루어진 중복 집합(multi set, 편..

스마트 포인터는 효율적인 자원관리를 하기 위함이다. C++ 이후의 많은 언어들이 가비지 컬렉터가 내장된 상태로 나왔지만 C++은 그렇지 않기 때문에 자원관리를 위한 장치가 필요하다. C++에서의 자원관리는 RAII 디자인 패턴을 따른다. RAII (Resource Acquisition Is Initialization) 는 자원의 획득은 초기화와 동일하다는 의미이다. 메모리 관리에는 2가지의 문제가있다. memory leak : 사용한 메모리를 해제하지 않음 double free : 이미 해제한 메모리를 다시 해제하려고 함. 모든 메모리 문제는 이 두 가지로 나뉘게 된다. 그렇다면 메모리 관리를 용이하게 해주는 스마트 포인터에 대해 자세히 알아보자. Unique_ptr 특정 객체에 유일한 소유권을 부여하는..

C++ 공부를 하면서 템플릿을 한두번씩은 사용해 봤을 것이다. 템플릿은 편리한 도구중 하나이다. 그런데 템플릿 메타 프로그래밍이란 무엇일까? 그리고 왜 쓰는 것일까? 템플릿 메타 프로그래밍의 사용 이유 먼저 템플릿 메타 프로그래밍의 사용 이유는 빠르기 때문이다. 무조건적으로 빠른게 아니라 템플릿은 컴파일 타임에 코드가 생성되기 때문에 컴파일 시점에 모든 연산이 끝나버린다. 컴파일 시점에 연산을 끝내기 때문에 실행 전의 시간(컴파일 시간)은 길어진다. 하지만 실행 속도 자체는 빨라지게 되는 것이다. 모든 템플릿의 문제는 여기 컴파일 시점에서 연산이 끝나는 상황에서 온다. 디버깅이 안될 뿐더러 프로세스 실행순서 4단계를 거치던 코드만 작성하던 사용자들에게 여러가지 어려움을 준다. 잠깐만 생각해봐도 링커를 사..

bfs로 해결한 문제이다. 이렇게 2X2 배열로 탐색해야 하는 문제는 BFS로 풀게되는것 같다. bool 로 2*2 배열을 두었다. 그리고 2중 for문을 돌면서 배열을 모두 탐색하되 처음으로 true를 만나면 BFS를 바로 돈다. 그렇게 BFS 를 돌고 나오면 근접 위치들은 전부다 false가 된 상태일 테니 말이다. 이렇게 2중 for문으로 배열을 한번 탐색하면 답이 나온다. 내가 풀은 답안에 대해 좀더 설명하자면 BFS 진입 시에 answer 벡터에 push_back 으로 시작지점의 값을 넣어준다. 그리고 파라미터로 인접 인덱스들의 값을 저장시킬 벡터의 index도 넘겼다. 이러면 BFS 내부에서는 벡터의 인덱스에 접근해서 값을 + 해주기만 하면 되니까 굉장히 편리하다. 메..

bfs로 풀면되겠구나~ 라고 생각이 들지만 잘 풀리지 않았던 문제.. 코너마다 cost가 다르기 때문에 경로에 대해 cost의 값을 비교해줘야해서 어렵게 느껴진다. 아래의 문제로 인해 3차원 배열을 선택해서 문제를 풀었다. 그림을 보자. -1은 이동하지 못하는 곳이다. 좌측 상단을 보면 600의 값에서 코너를 하나 만들고 아래로 내려오는 값이 1200 이다. 그런데 1200 옆에 있는 1100을 보면 1200은 1100에서 직진해서 만들어지는 값이기도 하다. 이 때에는 600에서 1200으로 코너를 하나 만들고 그 뒤 아래로 계속 직진할 수 있으므로 600->1200 이 되어야 한다. 1100 -> 1200 인 파란색 경로대로 만들면 1200 아래의 값이 1200 + 600 이 되어버려 최소..

보자마자 간단히 for문으로 풀면 당연히 시간초과가 나겠군. 이라고 생각이 든 문제였다. 보통 이런문제는 누적합으로 문제를 풀기 때문에 누적합으로 접근을 해야하는 문제임을 확신하고 질문하기 들어가보니까 역시 누적합으로 접근해야 하는 문제였다. 누적합은 많은 연산을 딱 한번만 진행하는 것. 건물을 부수고 수리하는 많은 skill 배열을 한번만 돌아서 연산해야할 수를 정해준다. 각 skill 마다 최대 1000*1000 행렬을 돌지 않아도 되는것. 가로세로의 누적합을 각각 계산해야해서 인덱스를 조절해주는게 좀 까다로웠다. 예를들어 [ 0, -2, -2, -2 ] 이렇게 데미지가 들어간다면 실제 배열은 [ 0, -2, 0, 0, 2 ] 와 같이 처리해주어야 하니 말이다. 이게 가로 누적합은 쉬운데..

그래프가 사실 너비/깊이 탐색이랑 관련이 아예 없다고 할 순 없는데 그냥 보자마자 너비 우선 탐색으로 하면 되겠다 싶어서 그냥 그렇게 풀었다.. 노드는 무조건 1번에서 시작하므로 크루스칼이나 프림을 사용하지 않아도 된다고 생각했음.. 또 거리에 cost 가 없으니까 최소 신장 트리를 굳이 사용하지 않았다. 그래서 많이 풀어서 자신있는 BFS로 문제를 해결했다. 각 노드가 어느 노드와 연결되어있는지 정리해 준 뒤, 1 번 노드부터 시작하여 연결된 노드를 방문체크 해주며 모든 노드를 탐색해보면 된다. 그럼 진행순서가 다음과 같아진다. 1번 노드는 3,2 번 노드와 연결되어 잇으므로 3,2 탐색 3번 노드는 6,4 번과 연결되어있으니 6,4 탐색 6번은 더 갈 곳이 없음 4번 노드는 2번과 연결되..

어제에 이어 오늘도 이분탐색 문제다! 일단 문제를 보고 for문으로 한명씩 보내면서 탐색하는 방법을 사용해봤다. for문으로 풀면서 뭐야 레벨3 이렇게 쉬워도 돼? 라고 생각했는데 역시나 for문으로는 풀리지 않는 문제이다. 배열의 크기가 200,000 일수도 있기때문. 어제까진 이분탐색을 언제 사용해야하는지 감이 좀 잡히지 않았는데 오늘 문제를 풀고나니 좀 감이 잡힌다. 풀이 방법은 mid 값을 정해준 뒤 mid 값의 니니즈 친구들을 전부 보내보는 방법이다. 그러다 건널 수 없게되면 mid 값을 하나 낮춰서 진행하면 된다. 그러면 mid 값은 어떻게 구하는지 궁금할 수 있게된다. 일단 left는 무조건 1로 둔다. 그리고 right 값은 징검다리 돌중에 가장 큰 원소값을 가져온다. 징검다리..