Priceless

list와 map 라이브러리를 불러온 후 작성한다 list의 동적 할당을 위해 크기를 미리 선언하지 않는다 미리 선언하면 end 접근할 때 0으로 모두 초기화되어 원하지 않은 출력 값이 나타날 수 있다 우선 학번을 입력 받기 위한 list인 student를 선언한다 그리고 student의 iterator를 매핑하는 map인 student_map을 선언한다 반복문에서 학번을 한 명씩 입력 받은 후 반복자 iter를 초기화한다 map을 통해 입력 받은 학번이 이미 수강신청을 했는지 확인한 후 이미 수강신청을 했다면 기존 수강신청 정보를 지운다 이후 입력 받은 수강신청 정보를 list 와 map 뒤에 추가한다 이후 정렬된 코드를 수강신청 제한 인원에 맞게 list를 자른 후 출력 형식을 조절하여 출력한다 in..

위의 문제에 포함되어 있는 예시로 설명한다 처음에는 for문을 두 개를 작성한 후 탐색하는 날짜에 필요한 상담 일 수 만큼 sum 변수를 추가로 설정하여 합하는 식으로 작성했다 물론 그렇게도 풀릴 것 같았지만 예외 처리가 많이 필요했다 그래서 다른 방법을 찾았다 내가 문제를 보고 답을 직접 구할 때도 뒤에서부터 구했던 것 같다 막상 코드로 작성하니 머리 속으로 풀었던 것 그대로 녹여내면 되는데 아직까지 쉽지 않은 듯하다 뒤에서 부터 역순으로 찾는다 날짜가 넘어가면 그 전 인덱스를 탐색하고 dp에 저장한다 이후 기존의 dp와 이전 날의 새로운 값을 더했을 때를 비교하여 더 큰 값을 dp에 저장한다 이후 dp를 모두 구했을 때 나오는 dp[1]을 출력한다 // baekjoon 15486 #include #i..

입력 받은 코인의 금액으로 코인 여러 개를 사용하여 목표 코인 금액을 맞출 수 있는 경우를 찾는 문제 물론 브루트 포스로도 풀 수 있겠지만 이 문제는 제한 시간이 0.5초로 다이나믹 프로그래밍으로 풀어야한다 dp[0]은 모든 코인이 0개가 사용되므로 dp[0] = 1로 설정한다 새로 갱신되는 dp 값은 새로운 코인 단위를 사용하기 전의 dp 값과 새로운 코인 단위의 dp 값을 합하면 새롭게 dp가 갱신된다 문제의 예시 경우를 살펴본다 1원, 2원, 5원을 사용하여 10원을 구성하는 예시이다 1원을 사용하는 경우 1원부터 10원까지 구성할 수 있는 경우는 모두 1가지 2원을 사용하는 경우 1원 1가지, 2원 2가지(1+1, 2), 3원의 경우 1원만 사용해서 3원을 구성하는 경우와 2원을 1원과 2원을 사..

이제는 dp를 푸는 대략적인 방법?을 알게 되었다 기본 배열, dp 배열, max or min 을 통해 구할 수 있다 물론 max 와 min 함수를 쓰기 위해서는 입력 값으로부터 어떻게 출력하는 과정까지 그 과정을 분석해야 함수를 쓸 수 있을 것이다 이 문제는 테스트 케이스 당 두 줄의 입력 값을 받는다 dp 배열의 초기 부분은 미리 초기화한다 배열의 길이가 1이더라도 동작한다 변이 이웃하지 않으니까 대각선이거나 두 칸 뒤의 값 중에서 최대 값을 고른다 이후 배열의 마지막에서 더 큰 값을 출력한다 // baekjoon 9465 #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); cout.tie(0); i..

가장 긴 증가하는 부분 수열을 구하는 문제 문제 설명만 듣고는 도무지 이해가 되지 않았다 그냥 숫자가 커질 때 count하면 되지 않을까 라는 식으로 처음은 배열을 사용하지 않고 이전 값과의 비교 만으로 코드를 구성했다 int N; cin >> N; if(N == 1){ return 0; } int ascent = 1; int input; int temp = 0; for(int i = 0; i > input; if(i == 0){ temp = input; } if(i > 0){ if(temp N; int count = 0; int arr[MAX]; int dp[MAX]; for(int i = ..

원하는 상대를 저장하는 arr 방문 여부를 나타내는 visited 그룹이 확정된 상태를 나타내는 done 총 세 가지 배열을 사용하여 구현하였다 방문 여부를 먼저 탐색한 후 방문 했다면 짝이 이루어져있는지 확인한다 이후 과정을 dfs로 반복한다 이후 배열의 크기에서 조가 짜여진 사람 수를 뺀 값을 출력한다 자잘한 과정의 흔적(?)을 보면 void reset()을 구현하는 대신 memset을 통해 초기화할 수 있다 for 문이 꼭 하나씩 커지도록 선언하지 않더라도 동작한다 또한 select의 s를 소문자로 사용했을 때 pc의 컴파일러에서는 잘 작동했지만 백준에 제출했을 때는 중복된 함수 이름으로 컴파일 에러가 발생했다 백준에서 select 라는 이름의 변수를 선언할 때는 유의해야한다 // baekjoon ..

이번에도 BFS를 활용한 문제 실생활에서 BFS를 많이 사용하는 것일까 BFS가 많이 쓰이는 것 같다 빙산 문제는 다음 상태의 배열까지 고려해야 하므로 두 개의 배열을 사용한다 이후 접한 면의 수를 탐색한 후 그만큼 빼고 다음 상태에 덮어쓰기한다 처음보는 함수를 많이 사용했기 때문에 조금 더 익숙해져야 할 것 같다 // baekjoon 2573 #include #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); } int arr[301][301]; int next_arr[301][301]; bool visited[301]..

BFS로 해결할 수 있는 문제 그리디 알고리즘과 유사하게 풀 수 있는 문제다 0초 동안은 2배로 이동할 수 있으므로 먼저 2배 이동이 가능한지 여부를 판단한다 이후 한 칸 전진할지 후진할지를 판단한다 이후 min_ 값을 통해 최소 시간을 구한다 함수가 많이 쓰이진 않지만 꽤 복잡하게 구성되어 있는 문제인 듯하다 // baekjoon 13549 #include #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); } int arr[100001]; //bool visited[101][101][101] ; //int dir[6]..

3차원으로 접근하는 BFS 문제 3차원으로 접근해야 하므로 움직이는 방향 또한 x축, y축, z축에 맞게 설정한다 BFS를 진행한 후 모든 토마토를 검사했을 때 0이 있다면 -1을 출력하고 즉시 종료한다 테스트 케이스는 1회이므로 별도의 방문 여부 기록과 reset함수를 구현하지 않았다 크기의 제한이 있어서 그런가 생각보다 시간을 많이 소요되진 않았다 // baekjoon 7569 #include #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); } int arr[101][101][101]; //bool visited[..

그래프 탐색은 너무 가혹합니다.. 어제는 DFS를 통해서 문제를 풀었다면 오늘 문제는 BFS를 사용하여 푸는 문제다 BFS는 큐를 사용해야 하기 때문에 나이트의 이동이 저장된 배열, 방문 여부 배열, 방문할 큐, 방문 가능한 방향을 가진 배열 총 4가지 구조체를 사용하여 문제를 풀어야 한다 나이트의 이동이 저장된 배열에는 나이트가 가능한 방향 만큼 한 번씩 이동하고 이동한 자리에는 이동한 횟수가 저장된다 과정을 반복하여 목표 자리에 도착했을 때 도착할 때까지 이동한 횟수를 출력한다 큐에는 방문할 좌표가 저장되어 있으며 저장한 후에는 pop을 통해 빼는 방식이다 // baekjoon 7562 #include #include #include #include using namespace std; // code..