2742번: 기찍 N
자연수 N이 주어졌을 때, N부터 1까지 한 줄에 하나씩 출력하는 프로그램을 작성하시오.
www.acmicpc.net
문제 해결을 위한 과정
앞선 2741번을 거꾸로 출력을 해주면 되는 문제입니다. 따라서 2741번 소스코드에 n을 빼주는 식으로 해결을 하면 됩니다.
소스코드
1 2 3 4 | n = int(input()) for i in range(n): print(n-i) | cs |
| 백준 알고리즘 1152: 단어의 개수(Python) (0) | 2021.02.02 |
|---|---|
| 백준 알고리즘 2739: 구구단(Python) (0) | 2021.02.02 |
| 백준 알고리즘 2741: N 찍기(Python) (0) | 2021.02.02 |
| 백준 알고리즘 2439: 별 찍기 - 2(Python) (2) | 2021.02.02 |
| 백준 알고리즘 2438: 별 찍기 -1 (Python) (0) | 2021.02.02 |
2741번: N 찍기
자연수 N이 주어졌을 때, 1부터 N까지 한 줄에 하나씩 출력하는 프로그램을 작성하시오.
www.acmicpc.net
문제 해결을 위한 과정
이 문제는 하나의 for문을 이용하여 쉽게 해결할 수 있습니다. Python의 경우 print()에 기본적으로 개행이 들어있다는 것을 알면 쉽게 해결할 수 있습니다.
소스코드
|
1
2
3
4
|
n = int(input())
for i in range(1, n+1):
print(i)
|
cs |
| 백준 알고리즘 2739: 구구단(Python) (0) | 2021.02.02 |
|---|---|
| 백준 알고리즘 2742: 기찍 N(Python) (0) | 2021.02.02 |
| 백준 알고리즘 2439: 별 찍기 - 2(Python) (2) | 2021.02.02 |
| 백준 알고리즘 2438: 별 찍기 -1 (Python) (0) | 2021.02.02 |
| 백준 알고리즘 15903: 카드 합체 놀이(Python) (0) | 2021.01.25 |
2439번: 별 찍기 - 2
첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제 하지만, 오른쪽을 기준으로 정렬한 별(예제 참고)을 출력하시오.
www.acmicpc.net
문제 해결을 위한 과정
앞선 2438번 문제와 동일하지만 각 행마다 n-1개만큼의 공백이 들어감을 주의하며 해결한다.
소스코드
|
1
2
3
4
5
6
7
8
|
n = int(input())
for i in range(1, n+1):
for j in range(n-i):
print(" ",end="")
for j in range(i):
print("*", end="")
print()
|
cs |
| 백준 알고리즘 2742: 기찍 N(Python) (0) | 2021.02.02 |
|---|---|
| 백준 알고리즘 2741: N 찍기(Python) (0) | 2021.02.02 |
| 백준 알고리즘 2438: 별 찍기 -1 (Python) (0) | 2021.02.02 |
| 백준 알고리즘 15903: 카드 합체 놀이(Python) (0) | 2021.01.25 |
| 백준 알고리즘 2606: 바이러스(Python) (0) | 2021.01.25 |
2438번: 별 찍기 - 1
첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제
www.acmicpc.net
문제 해결을 위한 과정
입력받은 n만큼 행과 열이 출력되므로 이차원 리스트를 이용하여 해결한다.
소스코드
|
1
2
3
4
5
6
|
n = int(input())
for i in range(1, n + 1):
for j in range(i):
print("*", end="")
print()
|
cs |
| 백준 알고리즘 2741: N 찍기(Python) (0) | 2021.02.02 |
|---|---|
| 백준 알고리즘 2439: 별 찍기 - 2(Python) (2) | 2021.02.02 |
| 백준 알고리즘 15903: 카드 합체 놀이(Python) (0) | 2021.01.25 |
| 백준 알고리즘 2606: 바이러스(Python) (0) | 2021.01.25 |
| 백준 알고리즘 2667: 단지번호붙이기 (Python) (0) | 2021.01.25 |
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/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 |