SW

0. 제목 백준 11650 좌표 정렬하기 BOJ 11650 좌표 정렬하기 C++ 11650 좌표 정렬하기 1. 문제 https://www.acmicpc.net/problem/11650 2. 풀이 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표로 증가하는 순서로 정렬하는 것이다. 비교기준인 compare함수를 보면 pair로 인자들을 받는다. compare함수는 위 조건에 만족하면 true를 반환하고 아니면 false를 반환한다. 그리고 vectorv(N); 이렇게 2차원 벡터를 선언해주었는데, (N)을 빼먹으면 안된다. vectorv; 후 v.resize(N); 을 해주어도된다. resize함수는 내부용량을 딱 정해놓고 사용하는 것이다. 만약 사이즈를 10으로 해놨을 경우 무조건 사이즈는 10이..

0. 제목 백준 2751 수 정렬하기 2 BOJ 2751 수 정렬하기 2 C++ 2751 수 정렬하기 2 1. 문제 https://www.acmicpc.net/problem/2751 2. 풀이 O(N^2)인 정렬을 사용하면 안된다. 왜냐하면 수의 개수의 범위가 1,000,000까지이기 때문이다. sort는 최대 O(NlogN)이기 때문에 시간내에 정렬이 가능하다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include #include using namespace std; int main(int argc, const char * argv[]) { int N; int num; vector arr; cin..

0. 제목 백준 2667 단지번호붙이기 BOJ 2667 단지번호붙이기 C++ 2667 단지번호붙이기 1. 문제 https://www.acmicpc.net/problem/2667 2. 풀이 미로찾기와 비슷한 문제이다. 먼저 dx, dy는 좌,우,상,하 순으로 움직일 수 있도록 좌표설정을 한 배열이다. 이 문제에서 주의할 점이 입력을 받을 때 문자열로 받아야 한다는 것이다. 문자열로 받은 후 한글자마다 숫자로 만들어주었다. dfs함수를 보면 탐색을 할 때마다 cnt를 1씩 증가시켜준다. 그 후 visited의 원소를 true로 바꿔주고 반복문을 실시하게 된다. 이 반복문은 좌,우,상,하로 탐색을 실시하게 해주며 만약 좌표가 0보다 작아지거나 N보다 같거나 커지면 즉, 범위를 벗어나게 되면 건너뛰게 된다. 범..

0. 제목 백준 9466 텀 프로젝트 BOJ 9466 텀 프로젝트 C++ 9466 텀 프로젝트 1. 문제 https://www.acmicpc.net/problem/9466 2. 풀이 문제에서 프로젝트를 함께 하고 싶은 학생을 단 한 명만 선택할 수 있다고 하였다. 그렇기 때문에 vector를 이용할 필요가 없고 connect라는 배열을 선언해서 해결이 가능하다. connect[2] = 3; 의 의미는 2번 학생이 3번 학생을 가리키고 있다는 것이다. done은 이미 방문하였고 더 이상 볼 필요가 없는 점들을 표시하는 배열이다. visited는 방문 여부를 체크하는 배열이다. 먼저 여기서 dfs 함수는 사이클을 체크하는 함수로 쓰인다. 이 함수에 대해 설명해보면 다음과 같다. 처음에 방문하므로 visite..

0. 제목 백준 2579 계단 오르기 BOJ 2579 계단 오르기 C++ 2579 계단 오르기 1. 문제 https://www.acmicpc.net/problem/2579 2. 풀이 DP 방식을 이용하였다. [백준 2156] 포도주 시식 문제와 비슷하다. 먼저 초기값인 dp[1], dp[2], dp[3] 을 먼저 설정해준다. 문제에서 계단을 오를때 항상 마지막 계단을 밟아야 한다고 나와있다. 마지막 계단을 i번째 계단이라고 놓으면 i-1 번째 계단과 i-2 번째 계단을 밟는 경우를 생각해봐야 한다. i-1 번째 계단을 밟을 경우 3개 연속으로 밟으면 안되므로 i-2번째는 밟을 수 없다. 따라서 dp[i-3] + arr[i-1] + arr[i] 가 된다 i-2 번째 계단을 밟을 경우는 그대로 dp[i-2]..

0. 제목 백준 10610 30 BOJ 10610 30 C++ 10610 30 1. 문제 https://www.acmicpc.net/problem/10610 2. 풀이 30의 배수가 되려면 3의 배수이면서 10의 배수여야한다. 10의 배수이려면 마지막에 0이 반드시 나와야 하고 3의 배수이려면 각 자리 수의 합이 3으로 나누어 떨어져야 한다. 그리고 문제에서 N이 최대 100000개의 숫자로 구성되어 있다고 하여 문자열로 입력을 받았다. 먼저 입력값에 0이 포함되어 있는지 확인하고 포함되어 있는 것들의 자리수 합을 구한다. 자리수가 3으로 나누어 떨어지면 내림차순을 하고 정답을 출력한다. 조건에 맞지 않으면 -1을 출력한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..

0. 제목 백준 2875 대회 or 인턴 BOJ 2875 대회 or 인턴 C++ 2875 대회 or 인턴 1. 문제 https://www.acmicpc.net/problem/2875 2. 풀이 그리디 알고리즘을 사용하였다. 2명의 여학생과 1명의 남학생이 팀을 만들어야 하고 K명이 인턴쉽에 참여해야 한다. K명이 빠져야 하므로 여학생, 남학생에서 합하여 K명 만큼 모든 경우의 수대로 뺀다. 여학생 2명과 남학생 1명이므로 위에서 뺀 값을 각각 2와 1로 나눈다. 두 값중 작은 값이 만들어질 수 있는 팀의 수가 된다. 최대의 팀 수를 구해야 하므로 최대값과 만들어진 팀을 비교하면서 최대값을 갱신하고 최종 결과가 답이 된다. 다음과 같은 방식으로도 답을 구할 수 있다. min(N/2, M, (N+M-K)/3..

0. 제목 백준 2331 반복수열 BOJ 2331 반복수열 C++ 2331 반복수열 1. 문제 https://www.acmicpc.net/problem/2331 2. 풀이 DFS를 사용하였다. visited는 방문횟수를 저장하는 배열이다. 인덱스의 최댓값은 300000을 넘지 못하므로 visited[300001] 으로 크기를 설정하였다. dfs함수를 구현할 때 방문할때마다 visited[x]의 값을 1씩 증가시켜주었다. 그리고 if(visited[x]==3) retun; 에서 3일때 return 해야 하는 이유는 문제에서 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하라고 하였기 때문이다. 만약 2에서 return을 해버리면 반복되는 수들까지 개수에 포함이 된다. 그래서 3일때 ret..

0. 제목 백준 11047 동전 0 BOJ 11047 동전 0 C++ 11047 동전 0 1. 문제 https://www.acmicpc.net/problem/11047 2. 풀이 그리디 알고리즘을 사용하였다. 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 동전의 가치가 오름차순으로 주어지기 때문에 가치가 큰 동전부터 차례대로 나눈다. 몫만큼 cnt에 더해주고 K를 나머지로 갱신해준다. 그렇게 모든 동전에 대해서 K/value[i]의 값이 0이 아닌동안 반복하면 누적된 cnt가 정답이다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

0. 제목 백준 10451 순열 사이클 BOJ 10451 순열 사이클 C++ 10451 순열 사이클 1. 문제 https://www.acmicpc.net/problem/10451 2. 풀이 DFS, BFS 두가지 방법으로 풀 수 있다. Directed Graph 이므로 방향성을 가지고 있다. 각 정점에 연결된 점들을 graph vector에 push_back 함으로써 연결성을 가지게 한다. 그 후 DFS, BFS 중 하나를 이용하여 탐색을하고 모든 점을 시작점으로 하여 count 값을 구한다. count 값이 순열 사이클의 개수이다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..