알고리즘 스터디 2주차 결산

0927

#include <iostream>
#include <vector>
using namespace std;

int main() {
    long long min, max;
    cin >> min >> max;

    long long length = max - min + 1;
    vector<bool> isSquareFree(length, true);  

    for (long long i = 2; i * i <= max; i++) {
        long long square = i * i;

        long long start = (min + square - 1) / square * square;

        for (long long j = start; j <= max; j += square) {
            isSquareFree[j - min] = false; 
        }
    }

    int count = 0;
    for (int i = 0; i < length; i++) {
        if (isSquareFree[i]) count++;
    }

    cout << count << '\n';
    return 0;
}

 

0928

 

num = int(input())
d = [0] * (num + 1)

for x in range(2, num + 1):
    d[x] = d[x - 1] + 1         
    if x % 2 == 0:              
        d[x] = min(d[x], d[x // 2] + 1)
    if x % 3 == 0:              
        d[x] = min(d[x], d[x // 3] + 1)

print(d[num])

풀이과정: dp 알고리즘 중 상향식 dp를 사용하였다.

d[x]는 1로 만드는데 필요한 최소 연산 횟수로 설정하ㅗㄱ,

본인이 참고한 자료(블로그, 논문 등)가 있으면 꼭 출처를 남기시기 바랍니다.

참고 블로그: https://velog.io/@jxlhe46/알고리즘-다이나믹-프로그래밍

배운 점: 해당 문제를 풀며 새로 공부한 내용을 간략하게 작성하면 됩니다. (예시 : Gaussian Elimination을 응용해 역행렬을 계산하지 않고 LU분해를 하는 방법을 배웠다.)

 

0929

몸이 안좋아서 그냥 잠........

 

0930

num, caseNum = map(int, input().split())
d = {}

for _ in range(caseNum):
    s = input().strip()
    if s in d:
        del d[s]
    d[s] = True

for x in list(d.keys())[:num]:
    print(x)

풀이과정 : 단순하게 입력받은 당시 이미 해당 값이 존재하면 기존 값을 지운다. 반복문이 끝나면 제시된 수만큼 차례대로 출력한다

배운 점: 문제 자체는 간단하지만 시간 제한이 빡빡한 편이다. 처음에 일반적인 방식으로 in 연산과 remove 연산을 사용했더니 최악의 경우 O(n^2)가 나오기에 시간 초과에 걸렸다.

고치기 위해 dict를 사용했다. 다만 파이썬 버전이 낮으면 일반 dict가 순서를 기억하지 못하기에 주의가 필요하다

 

1001

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

int main(){
	int num(0), height(0), weight(0), score(1);
	vector <tuple<int, int, int>> arr;
	cin >> num;
	
	for(int i = 0; i < num; i++){
		cin >> weight >> height;
		arr.push_back({weight, height, score});
	}
	
	for(int i = 0; i < num; i++){
		for(int j = 0; j < num; j++){
			if(i==j) continue;
			
			 if (get<0>(arr[j]) > get<0>(arr[i]) &&
                get<1>(arr[j]) > get<1>(arr[i])) {
                get<2>(arr[i])++;
		}
		}
	}

	for (int i = 0; i < num; i++) {
	cout << get<2>(arr[i]) << " ";
	}

return 0;
}

풀이과정 : tuple을 통해 벡터에 세 개의 분류를 생성했다.

이후 반복문 연산을 통해 몸무게, 키가 모두 큰 경우에만 덩치가 크다고 판정한다. 이 경우 최악의 상황에서도 시간 복잡도는 O(n^2)이 된다. 문제의 시간 조건이 2초며 제한에 주어진 최대 수가 작은 편이기에 해당 방식을 사용했다

 

1002

num = int(input())
arr = [0]  

for _ in range(num):
    arr.append(int(input()))

d = [0] * (num + 1)

d[1] = arr[1]
if num >= 2:
    d[2] = arr[1] + arr[2]
if num >= 3:
    d[3] = max(arr[1] + arr[3], arr[2] + arr[3])

for i in range(4, num+1):
    d[i] = max(d[i-2] + arr[i], d[i-3] + arr[i-1] + arr[i])

print(d[num])

풀이과정 : d[i]는 i번째 계단까지 올라갔을 때 얻을 수 있는 최대 점수를 저장하는 배열이다

d[i]를 반복문 내에서 돌릴 때, 이전 계단에서 바로 올라오기 or 두 계단 뛰고 올라오기 중 더 큰 값을 골라 값에 집어 넣는다. 마지막에는 d[num]값을 출력한다.

배운 점: dp를 적용시키는 것에 익숙해지려 노력 중이

 

1003

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> grid(N);
    for (int i = 0; i < N; i++) cin >> grid[i];
    
    vector<vector<vector<int>>> visited(N, vector<vector<int>>(M, vector<int>(2, 0)));
    queue<tuple<int,int,int,int>> q;
    q.push({0, 0, 1, 0}); 
    visited[0][0][0] = 1;

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    while (!q.empty()) {
        auto [x, y, dist, broken] = q.front();
        q.pop();

        if (x == N-1 && y == M-1) {
            cout << dist << "\n";
            return 0;
        }

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

            if (grid[nx][ny] == '0' && !visited[nx][ny][broken]) {
                visited[nx][ny][broken] = 1;
                q.push({nx, ny, dist + 1, broken});
            }

            if (grid[nx][ny] == '1' && broken == 0 && !visited[nx][ny][1]) {
                visited[nx][ny][1] = 1;
                q.push({nx, ny, dist + 1, 1});
            }
        }
    }

    cout << -1 << "\n";
    return 0;
}

풀이과정 : 기초 코드는 ppt 그대로

while문을 통해 bfs 탐색을 진행한다. 현재의 위치와 이동 거리, 벽이 부숴졌는지의 여부를 확인할 수 있다.

이후 if문을 통해서는 도착 여부를 확인한다. 만일 목표 지점에 도달하였다면 현재 dist 값을 출력한 다음에 종료한다. bfs를 이용하였기에, 처음 도착한 경우가 최단 거리가 된다

그 아래에 깔린 코드는 빈칸 이동/벽 부수고 이동에 관한 내용이다.

마지막으로 만일 도착점에 도달하지 못했다면 -1을 출력한다

참고 블로그: https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

배운 점: 지난 주 ppt에서 제공해주신 기초 코드를 토대로 풀이했다. bfs 관련 문제는 풀어보지 않았는데, 이번에 풀어보게 되어 좋았다.