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

 

15903번: 카드 합체 놀이

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1,

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 그리디 알고리즘으로 해결할 수 있는 문제였습니다. 먼저 문제를 잘 보시면 리스트에서 가장 작은 값 2개를 빼온 후 그 둘의 합을 구합니다. 그 후 합들을 리스트에 넣어줍니다.

문제 해결을 위한 팁

이때 가장 작은 값을 두 개 빼오는 과정은 sort()를 이용하여 구할 수도 있고 우선순위 큐를 이용할 수 있습니다. 파이썬의 우선순위 큐는 최소합으로 구현이 되어있기 때문에 단순히 우선순위 큐에서 빼내기만 하면 가장 작은 값을 빼올 수 있습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import heapq
n, m = map(int, input().split())
data = list(map(int, input().split()))
q = []
for i in range(n):
  heapq.heappush(q, data[i])
 
for i in range(m):
  x = heapq.heappop(q)
  y = heapq.heappop(q)
  heapq.heappush(q, x+y)
  heapq.heappush(q, x+y)
 
print(sum(q))
  
 
 cs

 

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

백준 알고리즘 2439: 별 찍기 - 2(Python)  (2) 2021.02.02
백준 알고리즘 2438: 별 찍기 -1 (Python)  (0) 2021.02.02
백준 알고리즘 2606: 바이러스(Python)  (0) 2021.01.25
백준 알고리즘 2667: 단지번호붙이기 (Python)  (0) 2021.01.25
백준 알고리즘 2178: 미로 탐색 (Python)  (0) 2021.01.19

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

 

2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 제가 예전에 포스팅한 BFS의 코드를 암기하고 숙지하고 있다면 쉽게 해결할 수 있는 문제였습니다. (https://bgspro.tistory.com/15?category=981927) 먼저 문제에서 입력으로 주어진 그래프를 생성합니다. 그 후 1번 노드에 대해서 BFS를 수행합니다. 이렇게 BFS를 수행하면서 방문하는 노드마다의 개수를 하나씩 센 후 그 결과를 출력하면 됩니다. 

소스코드
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
from collections import deque
 
n = int(input())
m = int(input())
graph = [[] for _ in range(1 + n)]
visited = [False] * (1 + n)
 
for i in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
 
def bfs(graph, visited, start):
  global count
  q = deque([start])
  visited[start] = True
  while q:
    v = q.popleft()
    for i in graph[v]:
      if not visited[i]:
        q.append(i)
        visited[i] = True
        count += 1
 
count = 0
bfs(graph, visited, 1)
print(count)
 cs

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

백준 알고리즘 2438: 별 찍기 -1 (Python)  (0) 2021.02.02
백준 알고리즘 15903: 카드 합체 놀이(Python)  (0) 2021.01.25
백준 알고리즘 2667: 단지번호붙이기 (Python)  (0) 2021.01.25
백준 알고리즘 2178: 미로 탐색 (Python)  (0) 2021.01.19
백준 알고리즘 1260: DFS와 BFS (Python)  (0) 2021.01.19

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

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 난이도는 실버 1티어 이지만 DFS, BFS의 개념만 정확하게 알고 있으면 쉽게 해결할 수 있는 문제였습니다. 상, 하, 좌, 우 4가지 방향으로 움직일 수 있기 때문에 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1]로 방향 리스트를 생성합니다. 그 후 bfs함수를 구현합니다. 

소스코드 - python

 

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
from collections import deque
n = int(input())
graph = []
for i in range(n):
  graph.append(list(map(int, input())))
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ans = []
cnt = 0
 
def bfs(xPos, yPos):
  count = 1
  q = deque()
  q.append((xPos, yPos))
  graph[xPos][yPos] = 0
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < n:
        if graph[nx][ny] == 1:
          graph[nx][ny] = 0
          q.append((nx, ny))
          count += 1
  ans.append(count)
 
for i in range(n):
  for j in range(n):
    if graph[i][j] == 1:
      bfs(i, j)
      cnt += 1
 
ans.sort()
 
print(cnt)
for i in ans:
  print(i)
 
 cs
소스코드 - c++
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
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define MAX 26
 
using namespace std;
 
int graph[MAX][MAX];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
bool visited[MAX][MAX];
vector<int> vec;
 
void bfs(int xPos, int yPos, int n) {
    queue<pair<int, int>> q;
    q.push({ xPos, yPos });
    int count = 1;
    visited[xPos][yPos] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n or ny >= n)
                continue;
            if (graph[nx][ny] != 0 && visited[nx][ny] == false) {
                q.push({ nx, ny });
                count += 1;
                visited[nx][ny] = true;
            }
        }
    }
    vec.push_back(count);
}
 
int main(void) {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &graph[i][j]);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (graph[i][j] != 0 && visited[i][j] == false) {
                bfs(i, j, n);
            }
        }
    }
 
    sort(vec.begin(), vec.end());
 
    printf("%d\n", vec.size());
    for (int i = 0; i < vec.size(); i++) {
        printf("%d\n", vec[i]);
    }
    return 0;
}
 cs

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

백준 알고리즘 15903: 카드 합체 놀이(Python)  (0) 2021.01.25
백준 알고리즘 2606: 바이러스(Python)  (0) 2021.01.25
백준 알고리즘 2178: 미로 탐색 (Python)  (0) 2021.01.19
백준 알고리즘 1260: DFS와 BFS (Python)  (0) 2021.01.19
백준 알고리즘 2810: 컵홀더 (Python)  (0) 2021.01.19

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

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 잘 못 생각하기가 쉬운 문제였던 것 같습니다. 저도 처음에 그냥 문제를 해결하려 하였다가 틀렸었고 백준 사이트에 질문게시판을 보고 접근방식이 잘못되었다는 것을 알게 된 후 해결할 수 있었던 문제였습니다.

먼저 heap을 이용해야 합니다. 파이썬의 경우 최소 힙 형태로 구현이 되어있기 때문에 보다 쉽게 해결할 수 있었습니다. 예시를 그림과 같이 보겠습니다.

(원래 heap은 트리의 형태로 구현되지만 시인성을 위해 큐의 형태로 그림을 표현하였습니다.)

 

1. 각 원소들을 heapq에 넣어준다.

10 20 40

 

2. heapq에서 원소 두개를 빼준후 더한다.

10 + 20 = 30

30

 

3. 합한 값을 heapq에 넣어준다

30 40

 

4. heapq에서 원소 두개를 빼준 후 더한다.

30 + 40 = 70

None

 

5. 2번에서 구한 30 과 4번에서 더한 70을 더해 100을 만든다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
import heapq
q = []
N = int(input())
for i in range(N):
  heapq.heappush(q, (int(input())))
 
sum = 0
while len(q) > 1:
  temp1 = heapq.heappop(q)
  temp2 = heapq.heappop(q)
  heapq.heappush(q, (temp1+temp2))
  sum += temp1+temp2
print(sum)
 cs

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

백준 알고리즘 2810: 컵홀더 (Python)  (0) 2021.01.19
백준 알고리즘 13305: 주유소(Python)  (0) 2021.01.19
백준 알고리즘 2437: 저울 (Python)  (0) 2021.01.03
백준 알고리즘 18353: 병사 배치하기(Python)  (0) 2020.12.21
백준 알고리즘 14501: 퇴사 (Python)  (1) 2020.12.19

https://programmers.co.kr/learn/courses/30/lessons/42889

 

코딩테스트 연습 - 실패율

실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스

programmers.co.kr

문제 해결을 위한 과정

이 문제의 경우 그다지 어렵지 않은 문제였고 파이썬의 내장 함수인 count를 이용하여 쉽게 해결을 할 수 있었습니다. 

for문을 이용해서 단계의 사람의 수를 구하고 리스트에 튜플의 형태로 (단계의 사람 수 /전체 사람 수, 전체 사람 수) 추가합니다. 그 후 전체 사람 수에서 단계의 사람 수를 빼줌으로써 다음 단계에서는 이전 단계에서의 사람의 수를 제외시켜 줍니다. 이렇게 리스트에 추가를 해 준 후 문제에서의 조건처럼 다음과 같이 정렬해줍니다. 

 

1. 실패율의 내림차순대로

2.. 실패율이 같으면 스테이지의 번호를 오름차순으로 

문제 해결을 위한 팁

이 문제의 경우 테스트 케이스중에 만약 5단계라면 3단계에서 모두 실패하고 4단계, 5단계에 도달하지 못하는 경우가 있습니다. 따라서 count를 이용하여 해당 단계에 도전하는 사람이 없는 경우 분모가 0인 divide by zero가 발생하지 않도록 실패율을 0으로 해당 리스트에 추가해줍니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(N, stages):
    user = len(stages)
    result = []
    ans = []
    for i in range(1, N+1):
        people = stages.count(i)
        if people == 0:
            result.append((0, i))
            continue
        fail = people / user
        result.append((fail, i))
        user -= people
    result.sort(key = lambda x: (-x[0], x[1]))
    for i in range(N):
        a, b = result[i]
        ans.append(b)
    return ans
 
N = 5
stages = [1, 2, 2, 1, 3]
print(solution(N, stages))
 cs

'알고리즘 > 프로그래머스' 카테고리의 다른 글

프로그래머스 의상(Python)  (0) 2024.04.06
신고 결과 받기(Python)  (0) 2022.02.20
가사 검색 (Python)  (0) 2020.12.17
블록 이동하기 (Python)  (0) 2020.12.07
괄호 변환 (Python)  (0) 2020.12.05

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

 

2437번: 저울

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 골드 3 티어 문제로 저는 굉장히 어렵게 풀었던 문제입니다. 그리디 알고리즘으로 해결할 수 있는 문제인데 우선 알아야 하는 것이 있습니다. 바로 1부터 X - 1까지 만들 수 있는 금액이라고 가정을 했을 때 X가 새로 들어온 화폐단위인 a[i]보다 크다면 X원은 만들 수 없다는 것입니다. 이 경우는 저는 암기를 하기로 결정하였습니다. 크루스칼 알고리즘도 그리디이긴 하지만 암기가 필요한 부분입니다. 따라서 해당하는 경우도 암기를 바탕으로 해결합시다.

문제 해결을 위한 팁

팁까지는 아니지만 꼭 짚고 넘어가야할 조건이 있습니다. 바로 리스트가 정렬이 된 상태이어야만 한다는 것입니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
data = list(map(int, input().split()))
data.sort()
 
target = 1
for x in data:
  if target < x:
    break
  target += x
 
print(target)
 cs

 

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

백준 알고리즘 13305: 주유소(Python)  (0) 2021.01.19
백준 알고리즘 1715: 카드 정렬하기 (Python)  (0) 2021.01.11
백준 알고리즘 18353: 병사 배치하기(Python)  (0) 2020.12.21
백준 알고리즘 14501: 퇴사 (Python)  (1) 2020.12.19
백준 알고리즘 1932: 정수 삼각(Python)  (0) 2020.12.18
개념

사이클 판별 알고리즘은 앞선 포스팅인 서로소 집합 알고리즘을 이용한 알고리즘입니다. 그림과 같이 노드 1, 2, 3이 있고 각각의 연결이 서로를 가리키게 되어있다고 가정합시다.

이 경우 앞선 서로소 집합 알고리즘의 find_parent를 이용하면 노드1의 부모는 노드 1, 노드 2의 부모는 노드 1, 노드 3의 부모는 노드 1로 모든 노드의 부모가 각각 노드 1 임을 확인할 수 있습니다. 따라서 사이클이 발생을 했다는 것을 알 수 있습니다. 그러므로 사이클 판별 알고리즘의 경우 두 노드를 확인한 후 부모 노드가 다르다면 union_parent 함수를 수행해주고 부모 노드가 같다면 사이클이 존재한다는 것을 출력한 뒤 함수를 종료하면 되는 것입니다. 소스코드는 다음과 같습니다.

소스코드

 

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
def find_parent(parent, x):
  if parent[x] != x:
    parent[x] = find_parent(parent, parent[x])
  return parent[x]
 
def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b
  
v, e = map(int, input().split())
parent = [0] * (1 + v)
 
for i in range(1, 1 + v):
  parent[i] = i
 
cycle = False
 
for i in range(e):
  a, b = map(int, input().split())
  if find_parent(parent, a) == find_parent(parent, b):
    cycle = True
    break
  else:
    union_parent(parent, a, b)
 
if cycle:
  print("사이클 발생")
else:
  print("사이클 X")
  
 cs

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

벨만 포드 알고리즘  (0) 2021.03.01
크루스컬 알고리즘 (Python)  (0) 2020.12.31
서로소 집합 알고리즘 (Python)  (0) 2020.12.30
다익스트라 알고리즘 (Python)  (0) 2020.12.22
편집거리 알고리즘 (Python)  (0) 2020.12.22
개념

서로소 집합 알고리즘은 말 그대로 어떠한 숫자들의 서로소인지 아닌지의 관계를 나타내는 알고리즘이라고 생각하시면 될 것 같습니다. 먼저 1, 2라는 집합과 3, 4라는 집합이 있다고 가정합시다. 이 두 집합은 교집합이 없기 때문에 서로소 관계라고 할 수 있습니다. 우리가 구현할 서로소 집합 알고리즘의 경우 부모를 확인하는 함수, 합치기 연산을 수행하는 함수로 크게 두 부분으로 나눌 수 있습니다. 단 부모를 확인하는 함수에서 경로 압축 기법을 사용하게 되면 보다 빠른 시간 복잡도로 문제를 해결할 수 있기 때문에 외워주는 것이 좋을 것 같습니다. 

소스코드

본 소스코드는 나동빈님의 이것이 취업을 위한 코딩테스트이다. 를 참조하였습니다.

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
def find_parnet(parent, x):
  # 루트 노드가 아니면, 루트 노드를 찾을때까지 재귀적으로 찾기
  if parent[x] != x:
    parent[x] = find_parnet(parent, parent[x])
  return parent[x]
 
# 두 원소가 속한 집합을 합치기
def union_Parent(parent, a, b):
  a = find_parnet(parent, a)
  b = find_parnet(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b
 
v, e = map(int, input().split())
parent = [0] * (v + 1)
 
for i in range(1, v + 1):
  parent[i] = i
 
for i in range(e):
  a, b = map(int, input().split())
  union_Parent(parent, a, b)
 
print("각 원소가 속한 집합: " , end="")
for i in range(1, v + 1):
  print(find_parnet(parent, i), end=" ")
print()
 
print("부모 테이틀: ",end="")
for i in range(1, v + 1):
  print(parent[i], end=" ")
 cs

 

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

크루스컬 알고리즘 (Python)  (0) 2020.12.31
사이클 판별 알고리즘 (Python  (0) 2020.12.31
다익스트라 알고리즘 (Python)  (0) 2020.12.22
편집거리 알고리즘 (Python)  (0) 2020.12.22
에라토스테네스의 체를 이용한 소수 판별 (Python)  (0) 2020.12.21

+ Recent posts

티스토리툴바