https://www.acmicpc.net/problem/1080

 

1080번: 행렬

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

www.acmicpc.net

 

문제 해결을 위한 과정

이 문제의 경우 규칙을 찾으려 노력하다가 규칙이 도저히 발견이 되지 않아서 단순하게 3*3 행렬을 뒤집는 함수를 만든 후 문제를 풀 수 있었습니다. N, M의 범위가 50 이하인 자연수이므로 O(N^2)로 조회하며 모든 좌표에 대해 3*3 행렬을 뒤집는다면 (다만 마지막에서 두 번째 세 번째 열까지 가능합니다.) 50 * 47 * 3* 3 이므로 대략 21150번의 연산을 수행해야 합니다. 파이썬의 경우 1초에 약 2천만 번의 연산을 할 수 있다고 알려져 있으므로 제한시간이 2초인 이 문제에서는 충분히 해결할 수 있는 방법입니다. 따라서 모든 경우의 수를 따져가며 브루트 포스의 방식으로 해결합니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def sumGraph(x, y):
  result = 0
  for i in range(x):
    for j in range(y):
      result += graph3[i][j]
  return result
 
def switch(x, y):
  for i in range(x, x+3):
    for j in range(y, y+3):
      if graph[i][j] == 0:
        graph[i][j] = 1
      else:
        graph[i][j] = 0
 
n, m = map(int, input().split())
graph = []
graph2 = []
graph3 = [[0] * m for _ in range(n)]
count = 0
 
for i in range(n):
  graph.append(list(map(int, input())))
  
for i in range(n):
  graph2.append(list(map(int, input())))
 
if n < 3 and m < 3:
  for i in range(n):
    for j in range(m):
      if graph[i][j] == graph2[i][j]:
        graph3[i][j] = 0
      else:
        graph3[i][j] = 1
  if(sumGraph(n,m))==0:
    print(0)
  else:
    print(-1)
else:
  for i in range(n-2):
    for j in range(m-2):
      if graph[i][j] != graph2[i][j]:
        switch(i, j)
        count += 1
  for i in range(n):
    for j in range(m):
      if graph[i][j] == graph2[i][j]:
        graph3[i][j] = 0
      else:
        graph3[i][j] = 1
  if sumGraph(n, m) != 0:
    print(-1)
  else:
    print(count)
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 2941번: 크로아티아 알파벳(Python)  (0) 2022.01.07
백준 알고리즘 14659번: 한조서열정리하고옴ㅋㅋ(Python)  (0) 2022.01.06
백준 알고리즘 1946번: 신입 사원(Python)  (0) 2022.01.06
백준 알고리즘 11866번: 요세푸스 문(Python)  (0) 2022.01.06
백준 알고리즘 1789번: 수들의 합 (Python)  (0) 2022.01.03

https://www.acmicpc.net/problem/1946

 

1946번: 신입 사원

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 정렬을 이용해서 풀 수 있었던 그리디 알고리즘 문제입니다. 문제를 잘 읽어보면 어떤 사람을 탈락시켜야 하는지 어떤 사람을 선발할 수 있을지에 대해서 알 수 있습니다. 예를 들어 다음의 경우가 있다고 생각해봅시다.

(3, 4)

(2, 1)

(1, 3)

(4, 2)

이 경우 서류심사 성적을 기준으로 오름차순을 취하면 다음과  같이 정렬됩니다.

(1, 3)

(2, 1)

(3, 4)

(4, 2)

문제에서 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠으므로 (3, 4), (4, 2)인 사람은 서류심사 성적, 면접시험 성적 모두 (2, 1)에 비해서 떨어집니다. 따라서 이 둘을 탈락시키면 합격시킬 수 있는 사람은 (1, 3), (2,1)로 두 명입니다. 

문제 해결을 위한 팁

위의 문제 해결을 위한 과정에서 보였듯이 먼저 서류심사 성적을 기준으로 정렬을 취합니다. 이렇게 뒤면 무조건 뒤에 정렬된 사람이 앞에 정렬된 사람보다 서류심사 성적이 낮기 때문에 면접 성적을 기준으로 이 사람을 합격시킬지 탈락시킬지 정할 수 있습니다. 즉 서류심사 등수를 기준으로 정렬을 수행하면 앞사람들 중 면접 등수가 높은 사람이 있다면 합격, 면접 등수가 낮은 사람이 있다면 탈락하면 되는 것입니다. 따라서 min값을 잡은 후 그 min값보다 낮은 등수의 사람은 탈락, min값보다 높은 등수의 사람은 합격을 시키면 됩니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
  n = int(input())
  data = []
  for _ in range(n):
    a, b = map(int, input().split())
    data.append((a, b))
  data.sort(key = lambda x: x[1])
  min = data[0][0]
  
  count = 1
  for i in range(1, n):
    if data[i][0] < min:
      min = data[i][0]
      count += 1
  print(count)
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 14659번: 한조서열정리하고옴ㅋㅋ(Python)  (0) 2022.01.06
백준 알고리즘 1080번: 행렬(Python)  (0) 2022.01.06
백준 알고리즘 11866번: 요세푸스 문(Python)  (0) 2022.01.06
백준 알고리즘 1789번: 수들의 합 (Python)  (0) 2022.01.03
백준 알고리즘 10610번: 30(Python)  (0) 2022.01.03

https://www.acmicpc.net/problem/11866

 

11866번: 요세푸스 문제 0

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 구현 유형의 문제로서 어려운 문제는 아니었지만 문제를 해결하는 데 있어서 생각하는 방식이 중요한 문제였습니다. 문제에서 주어진 예시를 해결해보겠습니다.

다음의 그림은 예시를 푸는 과정입니다. 이 예시에는 N은 7, K는 3입니다.

그림1. 3번째 3 출력
그림2. 3번째 6 출력
그림3. 3번째 2 출력
그림4. 3번째 7 출력
그림5. 3번째 5 출력
그림6. 3번째 1 출력&amp;nbsp;
그림7. 3번째 4 출력

문제 해결을 위한 팁

이 문제는 위의 그림을 자세히 살펴보면 알 수 있듯이 k번째 원소가 아닌 것들은 다시 뒤에 붙여서 해결한다는 점입니다. 따라서 관찰을 통해 큐를 구현하면 해결할 수 있음을 알 수 있습니다. 파이썬에서 큐 보다 효율적인 deque를 이용해 popleft(), append()를 이용해 해결할 수 있습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import deque
 
n, k = map(int, input().split())
q = deque()
 
for i in range(1, n+1):
  q.append(i)
 
print("<", end="")
i = 0
while True:
  i += 1
  if i != k:
    v = q.popleft()
    q.append(v)
  else:
    v = q.popleft()
    if (q):
      print(v, end=", ")
      i = 0
    else:
      print(v, end=">")
      break
 
 
 cs

 

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1080번: 행렬(Python)  (0) 2022.01.06
백준 알고리즘 1946번: 신입 사원(Python)  (0) 2022.01.06
백준 알고리즘 1789번: 수들의 합 (Python)  (0) 2022.01.03
백준 알고리즘 10610번: 30(Python)  (0) 2022.01.03
백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03

https://www.acmicpc.net/problem/1789

 

1789번: 수들의 합

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 난이도에 비해 생각을 하기가 조금 어려웠던 문제였습니다. 1부터 하나씩 더해가면서 만든 합이 S를 초과하는 순간 1부터 하니씩 더한 숫자들의 개수 - 1이 자연수 N의 최댓값 입니다.

이를 적용하면 다음과 같습니다. 

1 + 2 + 3 + 4 .... + 17 + 18 + 19 + 20 = 210 

즉 20을 더했을때 S를 초과하므로 20까지의 숫자들의 개수(20개) - 1 즉 19 입니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
 
count = 0
ans = 0
for i in range(1, n):
  ans += i
  count += 1
  if ans > n:
    count -= 1
    break
 
print(count)
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1946번: 신입 사원(Python)  (0) 2022.01.06
백준 알고리즘 11866번: 요세푸스 문(Python)  (0) 2022.01.06
백준 알고리즘 10610번: 30(Python)  (0) 2022.01.03
백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27

https://www.acmicpc.net/problem/10610

 

10610번: 30

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 그리디 알고리즘으로 그다지 어렵지 않은 문제였습니다. 30의 배수가 되려면 10의 배수이면서 3의 배수여야 합니다. 따라서 내림차순으로 정렬을 하였을 때 일의 자릿수가 0이면서 3의 배수이어야 합니다. 

문제 해결을 위한 팁

저의 경우 내림차순으로 정렬을 하기 위해 각각의 숫자를 str로 입력받은 후 내림차순으로 정렬한 후 int로 변경하였습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
s = list(map(str, input()))
s.sort(reverse = True)
 
temp = ""
for i in range(len(s)):
  temp += s[i]
 
temp = int(temp)
 
if temp % 10 != 0 or temp % 3 != 0:
  print(-1)
else:
  print(temp)
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 11866번: 요세푸스 문(Python)  (0) 2022.01.06
백준 알고리즘 1789번: 수들의 합 (Python)  (0) 2022.01.03
백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27

https://www.acmicpc.net/problem/1026

 

1026번: 보물

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 단순한 그리디 알고리즘 문제입니다. 각각의 배열의 원소들을 곱한 후 합을 의미하는 S가 가장 작으려면

a 리스트의 가장 작은 값과 b 리스트의 가장 큰 값을 곱한 후 각각의 배열의 원소들을 곱한 후 합하면 됩니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
 
a.sort()
b.sort(reverse = True)
 
sum = 0
for i in range(n):
  sum += (a[i] * b[i])
 
print(sum)
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1789번: 수들의 합 (Python)  (0) 2022.01.03
백준 알고리즘 10610번: 30(Python)  (0) 2022.01.03
백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27
백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25

https://www.acmicpc.net/problem/1010

 

1010번: 다리 놓기

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 순서를 중요하게 생각하지 않는 '조합'의 방식으로 해결할 수 있는 문제였습니다. 동시에 팩토리얼 연산을 해야 하므로 Dynamic Programming의 방식 역시 문제 풀이의 한 요소였습니다.

팩토리얼을 우리가 흔히 아는 방식 즉 재귀적으로 구현하게 되면 한번 구한 연산을 지속적으로 반복하기 때문에 필요 없는 수많은 연산을 하게 되어 많은 컴퓨팅 리소스를 잡아먹게 됩니다. 또한 당연하게도 시간제한에 걸리게 됩니다. 따라서 이를 시간 내에 구현할 수 있게 하기 위해 피보나치수열 혹은 팩토리얼의 경우 탑다운 또는 보텀업 방식을 이용하여 해결합니다. 

문제에서 N <= M이라는 조건으로 생각해보면 결국 M개의 사이트 중에서 순서에 상관없이 N개를 뽑는 경우입니다. 가령 N이 2개이고 M이 3개일 시, 3개의 M 중에서 2개를 순서에 상관없이 뽑는 경우입니다. (예를 들면 AB, AC, BA, BC, CA, CB) 이를 염두에 두고 소스코드를 작성하면 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
dp = [0] * 31
dp[0] = 1
dp[1] = 1
 
for i in range(2, 31):
  dp[i] = dp[i-1] * i
 
T = int(input())
for i in range(T):
  n, m = map(int, input().split())
  a = dp[m-n]
  b = dp[m]
  c = dp[n]
 
  print((b//a)//c)
 cs

위 소스코드에서 b//a는 mPn이고 이 결과를 c로 나눠야 mCn입니다.

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 10610번: 30(Python)  (0) 2022.01.03
백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27
백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25
백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23

https://www.acmicpc.net/problem/1463

 

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 전형적인 Dynamic programming 방식으로 풀 수 있는 문제입니다. 풀이 역시 정형화되어있기 때문에 쉽게 해결할 수 있습니다. 

문제에서 정수 X에 사용할 수 있는 연산은 다음과 같이 3가지라고 합니다.

 

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

즉 이 문제는 먼저 문제에서 주어진 대로 10^6크기의 dp라는 리스트를 만든 후 INF로 초기화해줍니다. 그 후 dp[0], dp[1]은 0으로 재정의 해줍니다. (1로 만드는 것이므로 1은 이미 1이기 때문에 0번의 연산이 필요하므로) 그 후 반복문으로 차근차근 조회해나가면서 1을 빼는 방법, 2를 나누는 방법, 3을 나누는 방법의 필요한 최솟값을 구해주면 됩니다. 

예시에서 보여준 10의 경우를 살펴보겠습니다. 즉 필요한 식은 다음과 같습니다.

min(dp[i-1]+1, dp[i//2]+1, dp[i//3]+1)

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
INF = int(1e9)
 
dp = [INF] * (1+n)
dp[0] = 0
dp[1] = 0
 
for i in range(2, n+1):
  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)
 
print(dp[n])
 cs

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27
백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25
백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23
백준 알고리즘 1068: 트리(Python)  (0) 2021.02.21

+ Recent posts

티스토리툴바