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

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 BFS를 잘 숙지하고 암기하고 있다면 실버 1 티어라는 높은 난이도에도 불구하고 매우 쉽게 해결할 수 있는 문제였습니다. 1은 이동할 수 있는 칸이고 0은 이동할 수 없는 칸입니다. 또한 인접한 칸 즉 상, 하, 좌, 우 의 방향으로 이동하기 때문에 행, 열의 리스트를 각각 만들어서 다음과 같이 정의합니다.

 

dx = [-1, 1, 0, 0]

dy = [0, 0, -1 ,1]

 

위 처럼 정의하면 i = 0인 경우 (-1, 0) 즉 위쪽 방향(상), i = 1인 경우 (1, 0) 즉 아래쪽 방향(하), i = 2인 경우 (0, -1) 즉 좌측 방향(좌), i = 3인 경우 (0, 1) 즉 우측 방향(우)으로 for문을 이용하여 쉽게 해결할 수 있습니다.

 문제 해결을 위한 팁

위 문제의 경우 visited 리스트를 따로 정의하지 않아도 해결할 수 있습니다. 출발지와 도착지를 출발한 개수를 구하라고 하였기 때문에 bfs과정에서 방문하지 않은 그래프를 탐색하는것이 아닌 graph[nx][ny] == 1을 탐색하고 이 경우 이전 좌표의 그래프 값에 1을 더한 값으로 재 정의해줌으로써 방문처리 및 탐색하는 칸의 개수를 한 번에 해결할 수 있습니다.

소스코드

 

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
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
  graph.append(list(map(int, input())))
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def bfs(start):
  xPos = start[0]
  yPos = start[1]
  q = deque()
  q.append((xPos, yPos))
  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 < m:
        if graph[nx][ny] == 1:
          graph[nx][ny] = graph[x][y] + 1
          q.append((nx, ny))
 
bfs((0, 0))
print(graph[n-1][m-1])
 cs

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

백준 알고리즘 2606: 바이러스(Python)  (0) 2021.01.25
백준 알고리즘 2667: 단지번호붙이기 (Python)  (0) 2021.01.25
백준 알고리즘 1260: DFS와 BFS (Python)  (0) 2021.01.19
백준 알고리즘 2810: 컵홀더 (Python)  (0) 2021.01.19
백준 알고리즘 13305: 주유소(Python)  (0) 2021.01.19

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

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 제가 전에 포스팅했던 DFS https://bgspro.tistory.com/14?category=981927,                                 BFS https://bgspro.tistory.com/15?category=981927를 정확하게 숙지 및 암기하고 있다면 실버 2 티어와 정답률 33프로의 문제임에도 불구하고 굉장히 쉽게 해결할 수 있는 문제입니다. 먼저 문제를 보겠습니다. 문제에서 그래프가 주어지고 이를 DFS로 탐색하는 경우 그리고 BFS로 탐색하는 경우를 출력하면 정답 판정을 받을 수 있습니다.

dfs와 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
28
29
30
31
32
33
34
35
36
37
38
39
from collections import deque
 
n, m, v = map(int, input().split())
graph = [[] for _ in range(1+n)]
visited = [0] * (1+n)
 
for i in range(m):
  a, b = map(int, input().split())
  # 양방향 연결
  graph[a].append(b)
  graph[b].append(a)
 
for i in range(n+1):
  graph[i].sort() # 연결된 노드가 여러곳일 경우 낮은 숫자를 가진 노드부터 탐색하기 위해 오름차순으로 
 
def dfs(graph, visited, v):
  print(v, end=" ")
  visited[v] = 1
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, visited, i)
 
def bfs(graph, visited, start):
  q = deque()
  q.append(start)
  visited[start] = 1
  while q:
    v = q.popleft()
    print(v, end= " ")
    for i in graph[v]:
      if not visited[i]:
        q.append(i)
        visited[i] = 1
 
dfs(graph, visited, v)
visited = [0] * (1+n)
print()
bfs(graph, visited, v)
 
 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
#include <bits/stdc++.h>
#define MAX 1001
using namespace std;
 
vector<int> graph[MAX];
bool visited[MAX]; // false 초기화
bool visited2[MAX];
 
void dfs(int x) {
    visited[x] = true;
    printf("%d ", x);
 
    for (int i = 0; i < graph[x].size(); i++) {
        int y = graph[x][i];
        if (!visited[y]) {
            dfs(y);
        }
    }
}
 
void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited2[start] = true;
 
    while (!q.empty()) {
        int x = q.front();
        printf("%d ", x);
        q.pop();
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited2[y]) {
                q.push(y);
                visited2[y] = true;
            }
        }
    }
}
 
int main(void) {
    int n, m, v;
    scanf("%d %d %d", &n, &m, &v);
 
    for (int i = 1; i < m + 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    for (int i = 1; i < n + 1; i++) { // 정렬
        sort(graph[i].begin(), graph[i].end());
    }
 
    dfs(v);
    printf("\n");
    bfs(v);
    return 0;
}
 cs

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

백준 알고리즘 2667: 단지번호붙이기 (Python)  (0) 2021.01.25
백준 알고리즘 2178: 미로 탐색 (Python)  (0) 2021.01.19
백준 알고리즘 2810: 컵홀더 (Python)  (0) 2021.01.19
백준 알고리즘 13305: 주유소(Python)  (0) 2021.01.19
백준 알고리즘 1715: 카드 정렬하기 (Python)  (0) 2021.01.11

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

 

2810번: 컵홀더

첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 그리디 알고리즘으로 쉽게 해결할 수 있는 문제였습니다. 먼저 그림과 함께 예시를 보도록 하겠습니다.

1) 일반적인 경우

예시를 그림으로 표현하면 위의 그림과 같은데 먼저 좌측부터 채워나간다고 하겠습니다. 이렇게 하면 마지막 커플석의 경우 좌측 우측 컵홀더를 이용할 수 있고 사용하지 못하는 사람은 2번째 커플석에서 1명, 3번째 커플석에서 1명

총 2명이 됩니다. 이를 확장하면 존재하는 커플석 -1 의 사람 수만큼 컵홀더를 사용할 수 없습니다. 따라서 입력받은 컵홀더의 수 - 1이 정답이 됩니다.

 

2) 예외의 경우

예외의 경우가 한가지 존재하는데 바로 전체다 S인 경우입니다. 이 경우는 커플석이 존재하지 않으므로 위의 

커플석 - 1로는 해결 할 수 없습니다. 이 경우는 일반 좌석의 개수보다 컵홀더가 하나 더 많기 때문에 일반석 모두 컵홀더를 사용할 수 있습니다. 따라서 이 경우 입력받은 S의 수를 그대로 출력합니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
data = input()
count = 0
for i in range(len(data)):
  if data[i] == 'L':  
    count += 1
 
if count == 0: # 커플석이 없는 경우
  print(n)
else:
  print(n-(count//2-1))
 
 cs

 

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

백준 알고리즘 2178: 미로 탐색 (Python)  (0) 2021.01.19
백준 알고리즘 1260: DFS와 BFS (Python)  (0) 2021.01.19
백준 알고리즘 13305: 주유소(Python)  (0) 2021.01.19
백준 알고리즘 1715: 카드 정렬하기 (Python)  (0) 2021.01.11
백준 알고리즘 2437: 저울 (Python)  (0) 2021.01.03

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

 

13305번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 그리디 알고리즘으로 해결할 수 있는 문제입니다. 그리디 알고리즘의 개념만 정확히 알고 있다면 쉽게 풀 수 있는 문제입니다. 가장 최선의 경우를 선택하는 경우 이기 때문입니다. 먼저 문제를 예를 들어봅시다. 

 

맨 처음 비용을 5로 잡았을때 다음 비용은 2 이므로 (5 < 2) 이 구간의 거리 즉 2만큼은 5라는 비용으로 이동합니다. 그 후 비용을 2로 갱신해줍니다.

5 * 2 = 10

 

비용을 2로 잡은 후 다음 비용은 4 이므로 (2 < 4) 이므로 다음 비용까지 비용 2를 유지합니다. 다음 비용은 1 이므로 갱신해 줍니다. 즉 3 + 1의 구간은 2라는 비용으로 이동합니다. 

2 * (3 + 1) = 8

 

비용은 1 이지만 마지막 구간이므로 종결합니다.

따라서 답은 10 + 8로 최소는 18입니다

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n = int(input())
route = list(map(int, input().split()))
amount = list(map(int, input().split()))
 
price = amount[0]
ans = 0
i = 1
ro = route[0]
while True:
  if i == n-1:
    ans += price * ro
    break
  if price < amount[i]:
    ro += route[i]
  else:
    ans += price * ro
    price = amount[i]
    ro = route[i]
  i += 1
 
print(ans)
 cs

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

백준 알고리즘 1260: DFS와 BFS (Python)  (0) 2021.01.19
백준 알고리즘 2810: 컵홀더 (Python)  (0) 2021.01.19
백준 알고리즘 1715: 카드 정렬하기 (Python)  (0) 2021.01.11
백준 알고리즘 2437: 저울 (Python)  (0) 2021.01.03
백준 알고리즘 18353: 병사 배치하기(Python)  (0) 2020.12.21

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 인 것을 확인할 수 있습니다. 크루스컬 알고리즘은 가능한 신장 트리 중 가장 최소의 비용으로 신장 트리를 연결하는 알고리즘입니다. 과정은 다음과 같습니다.

1. 모든 간선 정보를 따로 리스트에 저장한다. 

2. 리스트에 저장된 간선 정보를 cost가 작은순으로 정렬한 후 사이클의 존재 유무를 파악한다.

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
34
35
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
 
result = 0
edges = []
 
for i in range(e):
  a, b, cost = map(int, input().split())
  edges.append((cost, a, b))
 
edges.sort()
 
for edge in edges:
  cost, a, b = edge
  if find_parent(parent, a) != find_parent(parent, b):
    union_parent(parent, a, b)
    result += cost
 
print(result)
 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

+ Recent posts

티스토리툴바