https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 1. Logic C++로 풀이할 때는 좌우로 큐를 회전시켜야 할 때 직접 빼고 넣어줘야 하기 때문에 움직여야 할 숫자가 음수인지 양수인지에 따라 경우를 나눠서 풀이했다. 하지만 파이썬으로 풀이할 때는 파이썬 queue에는 rotate라는 함수가 있기 때문에 훨씬 쉽게 구현할 수 있었다. rotate 함수는 안에 들어가는 인자가 양수이면 큐 안의 인자들을 오른쪽으로 절댓값만큼 이동..
알고리즘
https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 1. Logic 기본적인 BFS문제이다. 처음 방문하는게 가장 최단거리기 때문에 vis배열을 통해 queue에 들어가는 갯수를 줄여주면서 BFS를 진행하면 된다. 2. Code c++ #include using namespace std; int n; int arr[1001]; bool vis[1001]; int bfs() { queue q; int ans = 0x3f3f3f3f; q.p..
https://www.acmicpc.net/problem/1270 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n n; while(n--) { unordered_map land; long long cur; cin >> cur; long long landNum; long long maxNum = -1; for(int i = 0; i > num; land[num]++; if(land[num] > maxNum) { maxNum = land[num]; landNum = num; } } if(maxNum > cur/2) cout
https://www.acmicpc.net/problem/2446 2446번: 별 찍기 - 9 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 1. Logic 별찍기는 재밌어! 2. Code #include using namespace std; int main() { int n; cin >> n; for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { cout
https://www.acmicpc.net/problem/1487 1487번: 물건 팔기 첫째 줄에 최대 이익을 만들어주는 가격을 출력한다. 이익이 최대인 가격이 여러개라면, 가장 낮은 가격을 출력한다. 또, 어떤 가격으로 팔아도 이익을 남길 수 없다면 0을 출력한다. www.acmicpc.net 1. Logic n의 범위가 50이기 때문에 완탐을 돌려도 시간복잡도가 안넘는다! 먼저 입력을 받은 후 입력값을 오름차순으로 정렬한다. 그럼 작은 가격부터 기준을 잡고, 기준으로부터 배열끝까지 돌면서 가격을 계산한다. 모든 수를 다 돌게되면 시간복잡도도 넘을 뿐더러, 기준보다 작으면 선택받지 못하기 때문에 무조건 선택받을 수 있게 배열의 가격을 기준으로 잡는것이다. 가격의 기준을 잡는 부분이 첫번째 for문에 ..
https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 1. Logic dp배열에는 해당 숫자를 만들수 있는 최소 갯수를 저장한다. 숫자를 중복해서 골라도 되고 해당 숫자를 고를수도, 안고를 수도 있으니 i*i를 구하는 for문 안에서 숫자를 선택하는 경우 선택하지 않는 경우를 반영해준다. 2. Code #include using namespace std; int n; int dp[50001]; int solve(i..
https://www.acmicpc.net/problem/1996 1996번: 지뢰 찾기 첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 줄에는 지뢰 찾기 map에 대한 정보가 주어지는데 '.' 또는 숫자로 이루어진 문자열이 들어온다. '.'는 지뢰가 없는 것이고 숫자는 지뢰가 있는 경 www.acmicpc.net 1. Logic 단순 파싱 그래프 구현 문제였다. 어렵진 않지만 c++로 파싱하려니 귀찮았다. 2. Code #include using namespace std; int n; int mine[1001][1001]; int sum[1001][1001]; char ans[1001][1001]; int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int dy[..
1. Quick sort 분할 정복 테크닉을 사용한 매우 빠른 시간 복잡도를 가진 정렬 알고리즘이다. 정렬 로직 수행 간 초기 정렬 상태를 보장하지 않는 불안정 정렬이다. 추가 메모리 공간을 필요로 하지 않는다. 시간 복잡도 : O(NlogN) Quick sort의 로직 동작 과정 주어진 배열의 범위 내에서 하나의 값(Pivot)을 기준으로 정하고, pivot 왼쪽에는 pivot보다 작은 값들이 오른쪽에는 pivot보다 큰 값들이 오도록 정렬한다. pivot을 기준으로 나뉜 배열은 정렬된 순서는 보장하지 않기 때문에 각각 배열에서 새로운 pivot을 설정하여 다시 분할해서 재귀 호출 한다. 1,2번의 과정을 배열을 분할할 수 없을 때 까지 반복한다. Quick sort 장/단점 장점 - pivot과 거리..
1. Merge sort 분할 정복기법을 활용하여 정렬시키는 정렬 알고리즘이다. 재귀를 활용하여 큰 문제를 작은 문제로 쪼개서 풀이한 다음 return하면서 값을 합쳐서 도출해낸다. 정렬 로직 수행 간 초기 정렬상태를 보장하는 안정 정렬 방식이다 시간복잡도 : O(NlogN) // 공간복잡도 : O(N) Merge sort의 로직 동작 과정 1. 정렬할 배열의 처음과 끝 인덱스를 함수의 인자로 넘겨준다. 2. 처음과 끝 인덱스를 2로 나눈, 즉 mid = (left + right)/2. mid를 기준으로 재귀함수를 호출하여 범위가 1이 될 때 까지 나눠준다. 3. 정렬한 후 값을 복사해서 return 한다. mid를 기준으로 나눴을 때 왼쪽 부분의 범위 : left~mid mid를 기준으로 나눴을 때 오..
1-1. Bubble sort / 버블 정렬 인접한 두 원소를 비교해서 정렬이 잘못되어 있으면 서로 바꾸는 방식으로 정렬한다. 한번 큰 for문을 돌 때마다 탐색 범위 중에서 가장 큰 값을 가지는 원소가 뒤로 이동한다(오름차순 정렬일 경우) 돌 때마다 큰 숫자 하나는 무조건 정렬되기 때문에 (전체 원소의 갯수 - 큰 for문을 돈 횟수)만큼 돌아주면 된다. 시간복잡도 : O(N^2) 1-2. Code #include using namespace std; int n; vector arr; void Print() { for (int a : arr) { cout
