성장하는 서버 개발자 도라프의 블로그 성장하는 서버 개발자 도라프의 블로그

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net [BOJ] 2467 용액 어떤 근을 찾는 문제가 아니라 비교값의 최소를 구하는 문제였기 때문에 투포인터를 사용하려고 했다. 그런데 하나 하나 다 비교한다면 시간 복잡도가 커지기 때문에 대소 비교하고 값 조정하는 이분 탐색의 틀을 사용하려는 시도를 했다. 대소를 어떻게 비교하고 어떻게 변수를 변화시켜줘야하는지 아이디어를 갖는 과정에서 이해가 안되는 부분이 많았다. 절대값을 비교하는 작업을 했는..

문제 입력 첫 번째 줄에 자연수 N(1 ≤ N ≤ 200,000)이 주어진다. 두 번째 줄에 자연수 k와 p(1 ≤ k, p ≤ N)가 공백으로 구분되어 주어진다. 출력 자연수 k가 heap 배열의 p번째에 위치하도록 하는 삽입 순서가 존재한다면 i번째 줄에 i번째로 삽입할 수를 출력한다. 가능한 삽입 순서가 여러 가지라면 그중 아무거나 하나를 출력해도 된다. 만약 그렇게 만드는 삽입 순서가 존재하지 않는다면 첫 번째 줄에 -1을 출력한다. 풀이 방법 자료 구조 문제에 나와있는 것 처럼 1based의 1차원 배열을 통해 구현하면 된다. heap[p] = k 임을 출력해야하므로 heap[p] = k를 넣고 다음 단계로 나아가면 된다. 그 다음 단계를 살펴 보자. 1. k의 부모(조상)은 k보다 작은 수여야..

문제 문제 접근 우선 색상환의 개수를 dp에 사용할 수 있겠다는 생각을 했다. 그래서 dp 2차원 배열에서 dp[N][k]라고 생각해서 설계했다. 조합을 사용하는 풀이처럼 느껴져서 배낭문제와 비슷하게 풀이를 해야겠다고 생각을 했고, 경우를 두가지로 나눠서 생각했다., 1) N번째 색을 택하는 경우 N번째 색을 택하면 N-1번째 색은 택할 수가 없다. 따라서 N-2개 색 중 K-1개 색을 택하는 경우와 같다. = dp[N-2][k-1] 2) N번째 색을 택하지 않는 경우 이 방법은 N-1개의 색에서 k개의 색을 택하는 경우와 같다. = dp[N-1][k] 따라서 dp[N][k] = dp[N-2][k-1] + dp[N-1][k] 이다. 정답 코드 #include #define mod 1000000003 us..

Priority Queue(우선순위 큐) 💡기본 Queue의 자료 구조는 FIFO(First in First out, 선입 선출)구조이다. 그에 반헤 Priority Queue는 설정된 우선순위에 따라, Top을 유지하고 먼저 Out(pop)된다. 사용 방법 queue를 import하여 사용한다. [멤버 함수] - queue에선 front를 사용해서 가장 앞에 있는 변수를 확인하는 것에 비해, priority_queue에서는 top을 활용하여 확인한다. - push : priorityqueuq에 값을 삽입한다. - emplace : priority queue에 구조를 삽입한다. push와 emplace의 차이 push의 경우 단순히 queue에 값을 넣어준다. 다시 말하면 오브젝트로 제작후 삽입해야하므로..

문제 문제를 보고 꽤나 당황했다.. 저는 체스 규칙도 모르는데요.... 유명한 문제고 백트레킹의 대표적인 문제이기 때문에 이번 기회에 완전히 정복하고 가자는 마음으로 풀어보겠다! 문제 해석 체스 규칙에서 퀸은 자신을 기준으로 일직선상과 대각선 방향에는 아무것도 놓여있으면 안된다. 퀸이 그곳으로 다 움직일 수 있다. 우선 이 문제에서는 퀸의 특성상 체스판 한 행당 한 개의 퀸만 존재할 수 있다고 생각하는 것이 중요하다.(같은 행에는 퀸이 놓일 수 없음) 풀이 방식 그리고 이 문제는 이차원 배열을 만들 필요 없이, 일차원 배열을 만든 후, 각 행의 몇번째 열에 퀸이 있는지를 저장하는 방식으로 풀 수 있다. 한 행마다 하나의 퀸을 배치해가면서, 총 배치 행수가 N이 되면, 경우의 수를 1개씩 올려주면 된다. ..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 문제 해결 사이클을 이루는 팀원들이 한 팀이 된다. => 사이클이 이루어지고 있는 과정은 dfs를 통해 파악한다. 이 문제에서 포인트는 '사이클을 다 돌았다면?' 에 대한 해답을 찾는 것이다. - 이미 방문한 정점을 다시 방문하면 사이클이 형성된다. - 여기서 시간복잡도가 커질 수 있다.. 이미 사이클이 형성된 학생은 다시 사이클인지 아닌지 체크해줄 필요가 없다. 그래서 이미 사이클이 형성된 학생..

백트래킹이란? 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아가는 기법! 기본적으로 백트래킹은 '가능한 모든 방법을 탐색한다'(완전 탐색 기법) 아이디어를 중심으로 한다. 백트래킹은 완전 탐색 기법 중 하나인 DFS에서 가지치기(Pruning)을 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 탐색 기법이다. BOJ 15649 N과 M(1) 이 문제는 1부터 N가지의 숫자 중 M개를 순서 있게 뽑기와 유사하다. 순열의 특징은 중복된 원소가 있으면 안된다는 것이다. 그러면 만일 중복된 원소를 만나는 순간 다른 경로로 가면 된다. 참고한 사이트이다. https://yabmoons.tistory.com/100 [ 순열과 조합 구현 ] - 재귀를 통한 구현(2..

문제 입력 & 출력 풀이 방법 이 문제를 풀면서 챌린지 요소가 두가지 였는데, 첫번째는 최소 일 수는 어떻게 계산할 것인가였고 두번째는 만일 익지 않은 토마토가 있다면 어떻게 확인할 것인가였다. 두번째에 대한 답안은 그래프 전체 탐색 알고리즘을 돌렸음에도 토마토가 익지 않은게 있다면 바로 -1 을 출력하고 함수를 끝내버리면 됨이다. 최소 일수를 반영하는게 어려웠는데 그 이유는 시작점이 하나가 아니라 첫 날에 익어있는 모든 토마토가 시작점이 되기 때문이다. 어떤 토마토는 4일째에 익었고 어떤 토마토는 5일째에 익을 수도 있다. 그러면 토마토가 익는데 걸리는 최소 일수는 5일이다. 그래서 max 함수를 통해 익는데 가장 오래 걸리는 토마토의 일수를 알아야한다. 여기서 나는 이런 방법을 사용했다. 1. 익는데..