anonymous?

📝 제출 코드 #1 #include #include using namespace std; int main(int argc, char** argv) { int N, K; // N: 학생 수, K: 구간 수 vector arr; cin >> N >> K; arr.push_back(0); for(int i=0; i> num; arr.push_back(num); } for(int i=0; i> A >> B; float sum=0; for(int j=A; j> N >> K; sum.push_back(0); for(int i=0; i> num; sum.push_back(sum[i]+num); } for(int i=0; i> A >> B; printf("%.2f\n", (sum[B]-sum[A-1])/(B-A+1))..

PROGRAMMING/Algorithm 2024. 2. 15. 15:38

문제풀이 항상 목적지에 도달하므로, BFS를 이용하여 (0,0)부터 (N,M)까지 최단 경로를 구하고, 각 좌표에 방문할 때마다 인접좌표까지 거리+1을 구한다. vector로 graph 만들었을 때는 제대로 안 구해졌는데 2차원 배열 쓰니까 잘 되었다. 결과는 마지막 좌표에서의 path를 출력해주면 된다. 제출코드 #include #include #include #include using namespace std; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; int main(){ int N,M; //vector graph[N]; int graph[101][101]={0,}; int path[101][101]={0,}; int visited[101][101]..

PROGRAMMING/Algorithm 2023. 9. 8. 21:39

풀이과정 BFS를 이용해서 최단경로 구할 수 있음 처음 (0,0)을 시작하므로 (0,0)에 대한 방문체크와 path를 1로 추가해준다. 이후 현재 좌표에서 상(-1,0), 하(1,0), 좌(0,-1), 우(0,1)가 유효한지 체크한 후, 방문하지 않았고 벽이 아니면 방문체크 후 인접노드에서 1 간 것과 같으므로 1을 더해서 path를 구한다. 탐색이 끝난 후 마지막 좌표(n,m)에 값이 들어있지 않으면 도달할 수 없는 것이므로 -1을 리턴하고, 값이 있으면 도달할 수 있으므로 값을 리턴한다. 제출코드 #include #include #include using namespace std; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; int path[101][1..

PROGRAMMING/Algorithm 2023. 9. 8. 20:51

제출답안 #include #include #include using namespace std; int main(int argc, char** argv) { vector num; bool same=true; for(int i=0; i> n; num.push_back(n); } vector ascending = num; vector descending = num; sort(ascending.begin(), ascending.end()); if(ascending == num) { cout

PROGRAMMING/Algorithm 2023. 9. 6. 21:16

입출력 입력: N(참가자 수), 세 개의 줄에 각 대회의 결과 출력: 각 참가자의 대회별 등수, 각 참가자의 최종 등수 문제풀이 과정 한 대회마다 등수 매기기 이때 max를 구하고 max인 모든 사람은 현재 등수를 주고 현재 등수인 모든 사람 카운팅 현재 등수인 모든 사람 카운팅 후 다음 등수 = 현재등수 + (현재 등수인 사람 수) 현재 max는 -1을 넣어서 다음 max로 고려되지 않게 하기 현재 대회의 모든 값이 -1이면 다음 대회로 넘어가도록 check 변수로 확인 참가자의 3개 대회에서 등수 구하기 3개 대회에서 등수는 (대회1 점수 + 대회2 점수 + 대회3 점수) 큰 순서로 출력 먼저 각 참가자의 각 대회에서의 모든 점수 구한 후 총점에서 max를 구하고 max가 동일한 사람을 동일한 등수 ..

PROGRAMMING/Algorithm 2023. 9. 5. 22:31

입력N: 크기N x N 블록 출력블록 수블록 별 장애물 수 (오름차순) 풀이과정https://koharinn.tistory.com/441 문제와 매우 유사. 이전에 많이 풀이본 유형의 풀이라서 바로 생각해낼 수 있었다. 입력 처리: 숫자가 붙어있어서 일단 string으로 받은 후, string의 각 원소는 char이므로 char-’0’으로 숫자로 변환 후 이 값을 배열에 저장 한 지점을 방문했을 때, 그 지점에서 갈 수 있는 방향은 상(x,y-1), 하(x,y+1), 좌(x-1,y), 우(x+1,y)이다. 이떄 상,하,좌,우가 유효한 지점인지(0보다 작지 않은지, 그리고 n보다 크거나 같지 않은지) 확인하고 방문해야 한다. 이렇게 각 지점에서 상,하,좌,우의 유효한 지점을 방문하면서 DFS를 호출해간다...

PROGRAMMING/Algorithm 2023. 8. 12. 16:24

N,M이 최대 100이므로, 구간을 인덱스로 속도 제한을 값으로 넣는 배열을 만든다. 1~100이므로 0은 사용하지 않도록 크기가 101인 배열을 만들었다. 이후 테스트하는 정보를 입력으로 받으면, 테스트하는 속도가 각 구간에서 제한 속도를 넘으면 기존 result 값과 현재 넘는 값을 비교하여 가장 큰 max 값을 저장한다. 처음에는 모든 제한 속도를 넘는 값을 vector에 저장하고, 그 중에서 max_element를 마지막에 구해서 출력하도록 했는데, 2개의 테스트케이스에서 런타임 에러가 발생해서 앞선 방식으로 결과를 구했다.#include #include #include using namespace std; int main(int argc, char** argv) { ios_base::sync_w..

PROGRAMMING/Algorithm 2023. 8. 12. 15:45

입력 BOJ 유저의 수 친구 관계 출력 케빈 베이컨의 수가 가장 작은 사람, 중복이 있는 경우 번호가 가장 작은 사람 출력 케빈 베이컨 수 = 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합 예제 5 5 1 3 1 4 2 3 3 4 4 5 1: 2(2단계), 3(1단계), 4(1단계), 5(2단계) ⇒ 2 + 1 + 1 + 2 = 6 2: 1(2단계), 3(1단계), 4(2단계), 5(3단계) ⇒ 2 + 1 + 2 + 3 = 8 3: 1(1단계), 2(1단계), 4(1단계), 5(2단계) ⇒ 1 + 1 + 1 + 2 = 5 4: 1(1단계), 2(2단계), 3(1단계), 5(1단계) ⇒ 1 + 2 + 1 + 1 = 5 5: 1(2단계), 2(3단계), 3(2단계), 4(1단계) ⇒ 2 + 3..

PROGRAMMING/Algorithm 2023. 7. 29. 17:20

입력 첫째줄: 테스트케이스 수 둘째줄: 한 줄에 있는 스티커 수 셋째줄: 스티커 별 점수 출력 각 테스트케이스에서 두 변을 공유하지 않는 스티커 점수의 최댓값 조건 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 됨 항상 S[0][0] 또는 S[1][0]부터 스티커를 떼기 시작함 -> S[0][0]을 뗄 때, S[1][0]을 뗄 때를 나누어서 점화식을 구현 항상 2 x n 배열로 스티커가 구성 풀이과정 예시를 통해 점화식을 생각해볼 수 있다. 스티커가 구성된 배열을 DP[2][5+1]라 하자. 편의 상 DP[0][0]과 DP[1][0]은 0으로 비워둔다. 그렇다면 DP[0][0] = DP[1][0] = 0으로 초기화를 하고, 나머지는 스티커 점수로 값을 채워야 한다. 0 50 10..

PROGRAMMING/Algorithm 2023. 7. 17. 00:00

배낭문제와 다이나믹 프로그래밍(DP)으로 생각하고 코드를 구현했다. 처음에 인사할 때 잃는 체력과 얻는 기쁨을 pair로 vector에 저장하고 남은 체력마다의 최대 기쁨도 vector에 저장했는데, 이때 vector에서 가져오고 저장하고 이런 처리하는 속도가 배열과 비교했을 때 상대적으로 너무 오래 걸리는 것 같았다. 그래서 잃는 체력과 얻는 기쁨은 1차원 배열에, 사람마다 남은 체력이 있을 때의 값을 최대 기쁨으로 저장하는 2차원 배열 DP를 이용해서 배낭 문제의 개념으로 문제를 풀었다. 인사하는 사람마다 남은 체력이 1~100일 때 인사했을 때 남은 체력이 0보다 크고 얻는 기쁨이 최대이면 이를 취하고, 그렇지 않으면 이전 사람에서의 해당 체력일 때를 취하였다. 처음에는 2차원 배열로 최대 기쁨을 ..

PROGRAMMING/Algorithm 2023. 7. 16. 15:50

Knapsack 알고리즘 DP[물건 번호][무게] = 최대 가치 -> 해당 물건에서 최대 무게를 가질 때 가질 수 있는 최대 가치에 해당 첫 번째 물건부터 무게 1부터 최대 무게 K까지 무게를 담았을 때 가질 수 있는 최대 가치를 DP에 저장한다. 이 정보는 다음 물건에서 최대 무게-다음 물건 무게가 이전에서 담을 수 있는 최대 무게에서 최대 가치를 가질 것이므로 이때의 가치와 다음 물건의 가치를 더했을 때와 이전 물건에서 최대 가치 중 최댓값을 취할 때 사용한다. 만약 i번째 물건의 무게가 최대 무게 j보다 작은 경우엔 담을 수 없으므로 i-1번째의 최대 무게 j에서의 최대 가치를 취한다. 최종적으로 마지막 물건에서 가질 수 있는 최대 무게에서의 최대 가치가 배낭에 넣을 수 있는 물건들의 가치합의 최댓..

PROGRAMMING/Algorithm 2023. 4. 14. 00:10

#include #include using namespace std; int main(){ int N,K; scanf("%d %d", &N, &K); vector sum(N+1,0); for(int m=0; m

PROGRAMMING/Algorithm 2023. 4. 11. 02:05