[자율스터디] 코테스터디 Team4 5월 보고서

코테 스터디 5월 결과 보고서 성준희 민서연 유정선 이누리 팀원들이 이번 달에 풀이한 문제 중 기억에 남는 문제를 하나씩 선정하여 정리하였습니다

 

문제 1

"회의실 배정" (백준 문제 1931) (https://www.acmicpc.net/problem/1931)

가능한 모든 조합 생성: 먼저 입력으로 받은 회의들 중에서 시작 시간과 종료 시간을 각각 저장. 각 조합의 면적 계산: 각 회의가 끝나는 시간을 기준으로 정렬하여 최대한 많은 회의를 배정. 최대 면적 조합 선택: 정렬된 회의들 중 가장 많은 회의를 배정할 수 있는 조합을 선택. 선택된 조합 출력: 선택된 회의의 개수를 출력. 코드 구성: 입력 → 회의들을 끝나는 시간을 기준으로 정렬 → 최대한 많은 회의를 배정할 수 있는 조 합 선택 → 선택된 회의의 개수 출력

 

파이썬 코드:

# 입력 받기
import sys
input = sys.stdin.read
data = input().split()
N = int(data[0])
meetings = []

for i in range(1, len(data), 2):
    start, end = int(data[i]), int(data[i+1])
    meetings.append((start, end))

# 끝나는 시간을 기준으로 정렬, 끝나는 시간이 같으면 시작 시간을 기준으로 정렬
meetings.sort(key=lambda x: (x[1], x[0]))

# 회의 배정
count = 0
end_time = 0

for meeting in meetings:
    if meeting[0] >= end_time:
        end_time = meeting[1]
        count += 1

# 결과 출력
print(count)

• 입력받은 회의들의 시작 시간과 끝나는 시간을 리스트에 저장.
• 끝나는 시간을 기준으로 회의들을 정렬.
• 정렬된 회의들 중에서 겹치지 않게 최대한 많은 회의를 선택하여 개수 계산.
• 최종적으로 선택된 회의의 개수를 출력.

백준 1로 만들기 연산할 수 있는 방법은 3가지가 있는데 특정 숫자를 3으로 나누거나 2로 나누거나 1을 빼는 방법으로 1을 만들어야 하는 문제이다. 10을 2로 다섯 번 나눌 수도 있지만 10에서 1을 빼고 9을 3으로 두 번 나누면 연산 횟수가 3회가 되 므로 3회가 답이 된다. 즉 그냥 나누는 것만으로는 문제에서 요구하는 정확한 답을 찾을 수 없다. 당면한 문제를 작은 문제 서브 프라블럼으로 나누어서 점화식을 찾는 동적프로그래밍 방식으로 풀이

#include<iostream>
#include<algorithm>
using namespace std;
int main(){    
    int N;    
    cin >> N;
    int dp[10000001];
  dp[0] = 0;    
  dp[1] = 0;    
  dp[2] = 1;    
  dp[3] = 1;
  for(int i=4; i<=N; i++){        
      dp[i] = dp[i-1] + 1;        
      if(i%2==0) dp[i] = min(dp[i], dp[i/2]+1);        
      if(i%3==0) dp[i] = min(dp[i],dp[i/3]+1);      
    }    
    cout << dp[N];    
    return 0;
}

 

문제 2

"문자열 폭발" (백준 9935) https://www.acmicpc.net/problem/9935

첫째줄에 문자열, 둘째줄에 폭발 문자열을 입력하면 문자열의 모든 폭발 문자열을 제거하고 남은 문자열을 출력한다.

문자열에서 폭발 문자열의 마지막 문자를 발견하면 이전 문자열을 하나씩 확인하면서 폭발 문자열과 몇 개가 같은지 확인한다. 동일한 문자열의 크기가 폭발 문자열 크기와 같으면 제거한다.

코드의 구성은 다음과 같다

두 문자열 a, b를 비교하여 b가 a의 끝부분에 얼마나 일치하는지 확인하고 일치하는 문자 수를 반환하는 함수를 작성한다.

문자열이 폭발 문자열보다 크면: 문자열과 폭발 문자열이 동일한지 확인한다.

문자열과 폭발 문자열이 동일하면: 문자열에서 폭발 문자열을 제거한다.

 

 

#include <iostream>
using namespace std;

int match(string a, string b) {
   int count = 0;
   for (int i = a.size() - 1, j = b.size() - 1; j >= 0; i--, j--) {
      if (a[i] == b[j]) count++;
   }
   return count;
}

int main() {
   string s;
   cin >> s;

   string bomb;
   cin >> bomb;

   string answer;

   for (int i = 0; i < s.size();i++) {
      answer += s[i];
      if (answer[answer.size()-1] == bomb[bomb.size() - 1]) {          if (answer.size() >= bomb.size())
            if (match(answer,bomb) == bomb.size()) {
               for (int j = 0; j < bomb.size(); j++)
                  answer.pop_back();

            }
      }
   }

   if (!answer.empty()) cout << answer << endl;
   else  cout << "FRULA" << endl;

   return 0;
}

 

나이트의 이동 - 7562번

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <string.h>
using namespace std;

int t, l, sy, sx, ey, ex, ny, nx;
int dy[]={-2, -1, 1, 2, 2, 1, -1, -2};
int dx[]={1, 2, 2, 1, -1, -2, -2, -1};
int visited[303][303];

void bfs(int y, int x){
    visited[y][x]=1;

    queue<pair<int, int>> q;
    q.push({y,x});

    while(q.size()){
        tie(y, x) = q.front(); q.pop();

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

            if(ny<0 || ny>=l || nx<0 || nx>=l) continue;
            if(!visited[ny][nx]){
                visited[ny][nx] = visited[y][x]+1;
                q.push({ny, nx});
            }
        }
    }
}

int main(){

    cin >> t;

    while(t >0){

        cin >> l;
        cin >> sy >> sx;
        cin >> ey >> ex;

        //visited 초기화
        memset(visited, 0, sizeof(visited));

        bfs(sy, sx);

        cout << visited[ey][ex]-1 << "\n";    //1부터 시작하니까

        t--;
    }

    return 0;
}

 

최단거리의 문제이므로 bfs로 푸는 것이 바람직하다. dy, dx를 재설정해야 한다. (방향 8개) 그럼 for 문에서 i=0부터 i<8일 때까지로 범위 잡기