anonymous?

📄 문제풀이 과정 단순히 정렬하는 문제인줄 알고 qsort를 사용하려고 했으나, 메모리초과가 발생했다. 메모리 사용은 최대 8MB까지로, 메모리 사용에 유의해야 한다. 일반적으론 배열에 모든 입력을 저장해서 sorting을 진행하지만, 이 문제에선 메모리 문제를 해결하기 위해서는 배열에 입력 값을 저장하면 안 된다. 따라서 입력받을 때마다 해당 수를 인덱스로 해당 수에 대한 카운팅을 하도록 했다. 그럼 각 인덱스마다 수가 몇 번 나타나는지 알 수 있으므로 출력 시 인덱스에 대한 값만큼 반복하여 인덱스 값을 출력하도록 했다. 해당 sorting 방법은 카운팅 정렬 알고리즘이다. 또 주의할 점은, 배열 크기는 입력받는 값인 N이지만, 배열 크기를 N으로 잡거나 출력 시 N만큼 반복문을 돌리면 메모리초과 에러..

PROGRAMMING/Algorithm 2021. 8. 6. 19:06

📄 문제풀이 과정 오름차순 정렬 후 K번째 위치한 수를 출력하는 문제이다. 간단하게 qsort로 정렬 후 0번째부터 시작하므로 K-1 인덱스의 숫자를 출력하면 되겠다고 생각했는데, 런타임 에러가 발생해서 찾아보니 Quick Selection Sort를 이용하여 좀더 효율적인 알고리즘을 사용해야 해결할 수 있음을 알 수 있었다. Quick Selection 알고리즘은 임의의 숫자 배열에서 K번째로 작거나 큰 값을 찾을 때 사용하는 알고리즘으로, 모든 배열을 정렬하는 것이 아니라 partition 함수의 리턴 값과 K를 비교하여 partition을 나눌지 결정하는 방식으로 K번째 수를 찾는다. Quick Sort의 경우 평균 O(nlogn), worst case에 O(n^2)이지만, Quick Selecti..

PROGRAMMING/Algorithm 2021. 8. 4. 17:33

#include #include #include #include using namespace std; class solution{ public: string name; int korean; int english; int math; solution(string a, int b, int c, int d){ name=a; korean=b; english=c; math=d; } }; bool compare(solution x, solution y){ if(x.korean == y.korean){ if(x.english == y.english){ if(x.math == y.math) return x.name y.math; } else return x.engl..

PROGRAMMING/Algorithm 2021. 3. 10. 11:20

#include #include #include #include // std::stable_sort using namespace std; bool compare(pair a, pair b){ //if(a.first == b.first) return a.second > b.second; // 나이 같을 경우, 먼저 가입한 a가 앞에 return a.first > N; vector v; for(int i=0; i> x >> y; v.push_back({x,y}); } stable_sort(v.begin(), v.end()..

PROGRAMMING/Algorithm 2021. 3. 10. 11:19

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

PROGRAMMING/Algorithm 2021. 3. 10. 11:17

#include #include #include using namespace std; class solution{ public: int x; int y; solution(int a, int b){ x=a; y=b; } }; bool compare(solution a, solution b){ if(a.y == b.y) return a.x < b.x; // y 좌표가 같으면 x 좌표가 증가하는 순으로 정렬 else return a.y < b.y; // default: y 좌표가 증가하는 순으로 정렬 } int main(){ int N; scanf("%d", &N); vector v; for(int i=0; i

PROGRAMMING/Algorithm 2021. 3. 10. 11:17

#include using namespace std; int main(){ cin.tie(NULL); ios::sync_with_stdio(false); int T; cin >> T; for(int i=0; i> A >> B; cout

PROGRAMMING/Algorithm 2021. 3. 10. 11:16

#include #include #include using namespace std; int main(){ int N; scanf("%d", &N); vector v; for(int i=0; i

PROGRAMMING/Algorithm 2021. 3. 10. 11:14

📝 문제풀이 과정 #include #include #include using namespace std; void BFS(int start, vector *graph, bool *visited){ queue q; visited[start] = true; q.push(start); printf("%d visited.\n", start); while(!q.empty()){ int current = q.front(); q.pop(); for(int next: graph[current]){ if(visited[next] == false){ visited[next] = true; q.push(next); printf("%d visited.\n", next); } } } } int solution(int n, vec..

PROGRAMMING/Algorithm 2021. 3. 2. 22:06

📝 문제풀이 과정 이번 문제도 BOJ:2667(단지번호붙이기) 문제와 유사하다. 각 병사 graph[x][y]를 기준으로 상, 하, 좌, 우의 4가지 경우에만 인접한 것으로 간주한다. x-1 y x y-1 x y+1 x+1 y 따라서 graph[x][y] 기준 위의 4가지 경우에 대해 해당 정점이 방문하지 않았고, graph[x][y]와 값이 같으면 방문한다. 그리고 인접한 것으로 cnt를 증가시킨다. 이때 다음 방문하는 graph[nx][ny]에서 nx와 ny는 전쟁터 M x N 크기 범위 내에 있는 것을 대상으로 탐색한다. 만약 초기 graph[x][y]에 대한 함수 호출이 끝나고 main 함수로 리턴하면 graph[x][y] 기준 모든 인접한 정점들에 대해 방문한 것으로, cnt에 대한 값의 제곱을..

PROGRAMMING/Algorithm 2021. 3. 2. 18:09

📝 문제풀이 과정 BOJ:2667 (단지번호붙이기) 문제를 풀어보면, 조금만 응용해서 쉽게 풀 수 있다. 이 문제에서는, 섬이 있으면 1로 표시하는데, graph[x][y] 기준으로 다음의 8가지 경우를 걸어서 갈 수 있는 경로로 간주한다. x-1 y-1 x-1 y x-1 y+1 x y-1 x y+1 x+1 y-1 x+1 y x+1 y+1 따라서 아래와 같이 위의 8가지 경우의 graph[x][y]에서 x좌표와 y좌표가 가질 수 있는 수를 나타낼 수 있다. int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; 8가지의 경우가 있으므로 DFS 함수에서 nx = x + dx[i], ny = y + dy[i]로 다음 방문..

PROGRAMMING/Algorithm 2021. 3. 2. 16:51

📝 문제풀이 과정 N x N 크기의 지도에서 집은 1로 표시된다. 대각선은 같은 단지로 취급하지 않는다. 상, 하, 좌, 우의 경우만 같은 단지이다. 출력: 단지 수, 각 단지별 집의 수를 한 줄 씩 출력한다. current 좌표 기준 상, 하, 좌, 우를 방문하지 않았고, 좌표가 0보다 크고 N보다 작으며 (좌표에서 벗어나지 않음) 1의 값을 가지고 있으면 count++을 하고, 재귀가 끝나고 처음 호출했던 함수로 리턴하면 해당 count를 deque에 추가한다. 완료 후, result에 있는 걸 sort로 오름차순 정렬 후 출력한다. 💻 C++ 제출코드 #include #include #include using namespace std; int cnt; int graph[25][25]; bool vi..

PROGRAMMING/Algorithm 2021. 2. 27. 00:06