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

 

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 3차원을 고려해야 한다는 점에서 조금 특이한 문제였습니다. 다만 3차원 리스트라는 점을 제외하면 이전에 풀었던 토마토 문제(https://www.acmicpc.net/problem/7576)와 비슷한 문제 이므로 어렵지 않게 해결할 수 있습니다. 

즉 상자의 위, 아래를 고려해야 하므로 dx, dy 뿐만 아니라 높이를 의미하는 dz 역시 존재해야 합니다. 따라서 for문을 6개로 구분하여 for i in range(6):으로 해결해야 합니다.

문제 해결을 위한 팁

3차원 리스트의 선언은 다음과 같이 선언할 수 있습니다.

graph = [[[0] * m for _ in range(n)]for _ in range(h)]

이렇게 하면 n행 m열의 그래프가 h만큼의 높이를 가지게 됩니다. 

접근하는 방법은 다음과 같습니다. 0번째 층의 1행 2열을 접근하려면 graph [0][1][2]로 접근할 수 있고

1번째 층의 2행 3열에 접근하려면 graph[1][2][3]으로 접근할 수 있습니다. 이 3차원 리스트에 지식을 가지고 접근하면 쉽게 해결할 수 있습니다.

소스코드
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
from collections import deque
 
def bfs(graph, tomato):
  count = 0
  while tomato:
    for _ in range(len(tomato)):
      x, y, z = tomato.popleft()
      for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        nz = z + dz[i]
        if nx < 0 or ny < 0 or nz < 0 or nx >= n or ny >= m or nz >= h:
          continue
        if graph[nz][nx][ny] == 0:
          graph[nz][nx][ny] = 1
          tomato.append((nx, ny, nz))
    count += 1
  return count
 
m, n, h = map(int, input().split())
graph = [[[0] * m for _ in range(n)] for _ in range(h)]
tomato = deque()
 
for k in range(h):
  for i in range(n):
    inputData = list(map(int, input().split()))
    for j in range(m):
      graph[k][i][j] = inputData[j]
      if graph[k][i][j] == 1:
        tomato.append((i, j, k))
 
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
 
day = bfs(graph, tomato)
numOfZero = 0
 
for k in range(h):
  for i in range(n):
    for j in range(m):
      if graph[k][i][j] == 0: 
        numOfZero += 1
 
if numOfZero == 0:
  print(day-1)
else:
  print(-1)
 
      
 
 cs

 

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

백준 알고리즘 2579번: 계단 오르기(Python)  (0) 2022.01.19
백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15
백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14

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

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 적록색약을 가진 분들과 적록색약이 아닌 분들이 보는 것이 다르다는 것을 이용한 문제입니다.

그것을 제외하고는 일반적인 bfs 문제와 같습니다. 예시를 들면 다음과 같습니다.

위의 그림이 있을 때 적록색약이 아닌 분들은 R, G, B로 3가지 구역, 적록색약인 분들은 RG, B로 2가지 구역으로 보는 것입니다. 따라서 이 점에 유의하며 bfs를 구현하면 됩니다.

문제 해결을 위한 팁

저의 경우는 그래프를 2개로 하여 기존에 입력받은 그래프를 복사하여 사용하였습니다. 이를 copy를 이용하였는데 copy의 경우 shallow copy, deep copy가 존재합니다. shallow copy의 경우 원본 혹은 복사본을 수정할 경우 기존의 그래프 역시 수정이 되므로 deep copy를 사용하여야 합니다. 따라서 import copy, 원본 = copy.deepcopy(복사본)를 사용합니다.

소스코드
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
62
63
64
65
66
67
68
69
70
71
from collections import deque
import copy
 
def bfs(graph, i, j):
  q = deque()
  q.append((i, j))
  target = graph[i][j]
  graph[i][j] = 'a'
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= n or ny >= n:
        continue
      if graph[nx][ny] == target:
        graph[nx][ny] = 'a'
        q.append((nx, ny))
 
def bfs2(graph, i, j):
  q = deque()
  q.append((i, j))
  target = graph[i][j]
  graph[i][j] = 'a'
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= n or ny >= n:
        continue
      if target == 'R' or target == 'G':
        if graph[nx][ny] == 'R' or graph[nx][ny] == 'G':
          graph[nx][ny] = 'a'
          q.append((nx, ny))
      else:
        if graph[nx][ny] == target:
          graph[nx][ny] = 'a'
          q.append((nx, ny))
      
        
 
n = int(input())
graph = [['a'] * n for _ in range(n)]
for i in range(n):
  inputData = list(input()) 
  for j in range(n):
    graph[i][j] = inputData[j]
 
graph2 = copy.deepcopy(graph)
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
count = 0
for i in range(n):
  for j in range(n):
    if graph[i][j] != 'a':
      bfs(graph, i, j)
      count += 1
 
print(count, end=" ")
 
count = 0
for i in range(n):
  for j in range(n):
    if graph2[i][j] != 'a':
      bfs2(graph2, i, j)
      count += 1
 
print(count)
 cs

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

백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14
백준 알고리즘 7576번: 토마토(Python)  (0) 2022.01.14

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

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 일반적인 상, 하, 좌, 우 네가지 방향을 탐색하는 bfs 문제에서 조금 벗어난 대각선까지 포함하는 8가지 방향을 탐색해야 하는 문제 입니다. 

일반적인 네가지 방향의 경우와 달리 여덟가지 방향을 그림으로 표현하면 다음과 같습니다.

따라서 dx, dy 리스트를 다음과 같이 만들고 for i in range(8)로 반복하면 됩니다.

 

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

dy = [0, 1, 1, 1, 0, -1, -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
27
28
29
30
31
32
33
34
35
from collections import deque
 
def bfs(graph, visited, i, j):
  q = deque()
  q.append((i, j))
  visited[i][j] = 1
  while q:
    x, y = q.popleft()
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= n or ny >= m:
        continue
      if graph[nx][ny] == 1 and visited[nx][ny] == 0:
        visited[nx][ny] = 1
        q.append((nx, ny))
      
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]  
while True:
  m, n = map(int, input().split())
  if m == 0 and n == 0:
    break
  graph = []
  for _ in range(n):
    graph.append(list(map(int, input().split())))
  visited = [[0] * m for _ in range(n)]
 
  count = 0
  for i in range(n):
    for j in range(m):
      if graph[i][j] == 1 and visited[i][j] == 0:
        bfs(graph, visited, i, j) 
        count += 1
  print(count)
 cs

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

백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14
백준 알고리즘 7576번: 토마토(Python)  (0) 2022.01.14
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.12

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

 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 전형적인 bfs의 형태는 아니지만 자주 등장하는 형태입니다. 따라서 이러한 유형을 bfs로 푸는 것에 익숙해져야 합니다. 수빈이가 이동할 수 있는 곳인 (현재 위치 -1, 현재 위치 +1, 현재 위치 * 2)를 bfs의 형태로 탐색을 하여 해결합니다. 다만 주의해야 할 점은 리스트의 범위입니다. 이러한 문제의 경우 인덱스 에러가 쉽게 발생할 수 있으므로 범위에 신경을 써서 문제를 해결해주셔야 합니다. 소스코드는 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from collections import deque
 
def bfs(n, k):
  q = deque()
  q.append(n)
  visited[n] = 1
  while q:
    v = q.popleft()
    for i in [v-1, v+1, 2*v]:
      if 0 <= i < 100001 and visited[i] == 0:
        visited[i] = visited[v] + 1
        q.append(i)
      if i == k:
        return visited[i] - 1
 
n, k = map(int, input().split())
visited = [0] * 100001
 
print(bfs(n, k))
 cs

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

백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15
백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 7576번: 토마토(Python)  (0) 2022.01.14
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.12
백준 알고리즘 11723번: 집합(Python)  (0) 2022.01.10

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

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 단순한 BFS에서 아주 조금 응용을 하면 쉽게 해결할 수 있는 문제였습니다. 그래프를 입력받을 때 토마토가 들어있는 좌표를 따로 tomato라는 deque를 만들어 저장한다면 쉽게 해결할 수 있었습니다. 그 후로는 일반적인 bfs문제를 풀 때처럼 bfs를 적용합니다. 다만 전체 상자 안에 토마토가 익으려면 며칠이 걸리는지를 물어보는 문제였기 때문에 while 문 안에 for _ in range(len(tomato))를 두어서 이 해당하는 for문을 벗어날 때만 하나씩 count를 증가시켜주면 됩니다. for문을 추가해주는 이유는 한 번에 즉 하루에 bfs로 탐색할 수 있는 양이 tomato라는 deque에 추가되기 때문에 이 deque의 전체가 비면 하루가 지난 것 이기 때문입니다. 추가적으로 bfs로 탐색 후 전체 그래프에서 0 즉 익지 않은 토마토가 하나라도 존재하면 -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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from collections import deque
 
def bfs(grpah, tomato):
  count = 0
  while tomato:
    for _ in range(len(tomato)):
      x, y = tomato.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
          continue
        if graph[nx][ny] == 0:
          graph[nx][ny] = 1
          tomato.append((nx, ny))
    count += 1
  return count
 
m, n = map(int, input().split())
graph = []
tomato = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
  graph.append(list(map(int, input().split())))
  for j in range(m):
    if graph[i][j] == 1:
      tomato.append((i, j))
 
day = bfs(graph, tomato)
 
numOfZero = 0
for i in range(n):
  for j in range(m):
    if graph[i][j] == 0:
      numOfZero += 1
 
if numOfZero == 0:
  print(day-1)
else:
  print(-1)
 cs

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

백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.12
백준 알고리즘 11723번: 집합(Python)  (0) 2022.01.10
백준 알고리즘 14499번: 주사위 굴리기(Python)  (0) 2022.01.10

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

 

18870번: 좌표 압축

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 N의 범위가 1,000,000 이므로 O(N^2)의 알고리즘으로는 시간 초과 판정을 받기 때문에 logN의 시간복잡도를 가지고 있는 이진탐색으로 해결할 수 있습니다. 문제의 예시를 설명하면 다음과 같습니다.

 

2 4 -10 4 -9

2 보다 작은 수는 -10, -9 총 2개 입니다.

4보다 작은 수는 -10, -9, 2 총 3개 입니다.

-10보다 작은수는 없습니다. 총 0개 입니다.

4보다 작은 수는 -10, -9, 2 총 3개 입니다.

-9보다 작은 수는 -10 총 1개 입니다.

따라서 결과는 2, 3, 0, 3, 1 입니다.

 

다만 두번째 예시에서 알 수 있듯이 중복된 숫자도 고려해줘야 합니다. 즉 다음과 같습니다.

1000 999 1000 999 1000 999

1000 보다 작은 수는 999 총 1개 입니다.

999보다 작은 수는 없습니다. 총 0개 입니다.

1000 보다 작은 수는 999 총 1개 입니다.

999보다 작은 수는 없습니다. 총 0개 입니다.

1000 보다 작은 수는 999 총 1개 입니다.

999보다 작은 수는 없습니다. 총 0개 입니다.

따라서 결과는 1, 0, 1, 0, 1, 0 입니다.

즉 이를 통해서 중복을 제거해줘야 하므로 set 즉 집합을 사용해야하는것을 알 수 있고 집합을 사용하여 정렬한 뒤 이진탐색을 통해 해당 위치를 찾으면 됩니다. 소스코드는 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def find(num, start, last):
  while last >= start:
    mid = (start + last) // 2
    if data2[mid] == num:
      return mid
    elif data2[mid] > num:
      last = mid - 1
    else:
      start = mid + 1
 
n = int(input())
data = list(map(int, input().split()))
data2 = set(data)
data2 = list(data2)
data2.sort()
 
 
for i in range(n):
  print(find(data[i], 0, len(data2)-1), end=" ")
 cs

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

백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14
백준 알고리즘 7576번: 토마토(Python)  (0) 2022.01.14
백준 알고리즘 11723번: 집합(Python)  (0) 2022.01.10
백준 알고리즘 14499번: 주사위 굴리기(Python)  (0) 2022.01.10
백준 알고리즘 2941번: 크로아티아 알파벳(Python)  (0) 2022.01.07
이 포스팅은 윤성우 님의 열혈 자료구조를 기반으로 합니다.

스택의 이해와 ADT 정의

스택은 자료구조중에 하나로서 흔히 박스를 쌓는 구조로 설명을 한다. 이를 그림으로 표현하면 다음과 같다.

스택의 그림


위의 그림을 보면 2, 4, 6, 8, 10 의 순서로 삽입을 한 형태이다. 먼저 들어온 2가 바닥에 있고 나중에 넣은 10이 위에 있음을 알 수 있다. 이를 상자를 쌓았다고 가정해보자. 상자의 밑 부분 부터 뺄 수 없으므로 당연히 맨 위에 부분부터 뺄 수 있을 것이다. 스택 역시 마찬가지이며 10 부터 뺼 수 있음을 알 수 있다. 이를 후입선출이라 하며 영어로 LIFO(Last In First Out)이다. 그렇다면 스택의 ADT를 살펴보자. 다음과 같다.

void StackInit(Stack * pstack);
// 스택의 초기화를 진행한다.
// 스택 생성 후 제일 먼저 호출되어야 하는 함수이다.

int SIsEmpty(Stack * pstack);
// 스택이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.

void SPush(Stack * pstack, Data data);
// 스택에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

Data SPop(Stack * pstack);
// 마지막에 저장된 요소를 삭제한다.
// 삭제된 데이터는 반환이 된다.
// 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Data SPeek(Stack * pstack);
// 마지막에 저장된 요소를 반환하되 삭제하지 않는다.
// 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

이제 이 ADT를 기반으로 배열 기반, 연결 리스트 기반으로 구현해보자.

배열 기반 스택 구현

스택에서 구현해야 하는 함수는 push, pop이 있고 이를 top이라는 스택의 가장 윗 부분을 담당하는 변수를 이용하여 구현한다.
가장 중요한 함수는 push, pop으로 push의 경우 top을 한칸 올리고 top이 가리키는 위치에 데이터를 저장하고
pop의 경우 top이 가리키는 데이터를 반환하고, top을 아래로 한칸 내린다. push연산을 그림으로 표현하면 다음과 같다.

push 연산

확인할 수 있는 점은 top의 시작은 -1 이며 하나의 데이터가 들어올 때 0이 된다는 것이다. 처음에 A를 추가할 때
top이 하나 증가한 뒤 해당 top의 위치에 원소가 추가되는것을 확인할 수 있으며 이후로도 마찬가지 이다.

pop연산역시 그림으로 표현하면 다음과 같다.

pop 연산

소스코드는 다음과 같다.

<ArrayBaseStack.h>

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
#ifndef __AB_STACK_H__
#define __AB_STACK_H__
 
#define TRUE    1
#define FALSE    0
#define STACK_LEN    100
 
typedef int Data;
 
typedef struct _arrayStack
{
    Data stackArr[STACK_LEN];
    int topIndex;
} ArrayStack;
 
typedef ArrayStack Stack;
 
void StackInit(Stack * pstack);
int SIsEmpty(Stack * pstack);
 
void SPush(Stack * pstack, Data data);
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);
 
#endif
 cs

<ArrayBaseStack.h>

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
#include "ArrayBaseStack.h"
#include <stdio.h>
 
void StackInit(Stack* pstack) {
    pstack->topIndex = -1;
}
 
int SIsEmpty(Stack* pstack) {
    if (pstack->topIndex == -1)
        return TRUE;
    else
        return FALSE;
}
 
void SPush(Stack* pstack, Data data) {
    pstack->topIndex += 1;
    pstack->stackArr[pstack->topIndex] = data;
}
 
Data SPop(Stack* pstack) {
    if (SIsEmpty(pstack)) {
        printf("Stack memory error!");
        return -1;
    }
 
    Data rdata = pstack->stackArr[pstack->topIndex];
    pstack->topIndex -= 1;
 
    return rdata;
}
 
Data SPeek(Stack* pstack) {
    if (SIsEmpty(pstack)) {
        printf("Stack memory error!");
        return -1;
    }
 
    return pstack->stackArr[pstack->topIndex];
}
 cs

<ArrayBaseStackMain.c>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include "ArrayBaseStack.h"
 
int main(void)
{
    // Stack의 생성 및 초기화 ///////
    Stack stack;
    StackInit(&stack);
 
    // 데이터 넣기 ///////
    SPush(&stack, 1);  SPush(&stack, 2);
    SPush(&stack, 3);  SPush(&stack, 4);
    SPush(&stack, 5);
 
    // 데이터 꺼내기 ///////
    while(!SIsEmpty(&stack))
        printf("%d ", SPop(&stack)); 
 
    return 0;
}
 cs

스택의 연결 리스트 기반 구현

앞서 스택을 배열로 구현하였는데 연결 리스트로도 구현할 수 있다. 단순하게 자료구조가 바뀐것 이외에는 개념적 단계에서의 구현에는 큰 차이가 없으므로 바로 헤더파일과 이를 통한 구현을 보일것이다.

<ListBaseStack.h>

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
#ifndef __LB_STACK_H__
#define __LB_STACK_H__
 
#define TRUE    1
#define FALSE    0
 
typedef int Data;
 
typedef struct _node
{
    Data data;
    struct _node * next;
} Node;
 
typedef struct _listStack
{
    Node * head;
} ListStack;
 
 
typedef ListStack Stack;
 
void StackInit(Stack * pstack);
int SIsEmpty(Stack * pstack);
 
void SPush(Stack * pstack, Data data);
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);
 
#endif
 cs

<ListBaseStack.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
#include "ListBaseStack.h"
#include <stdio.h>
#include <stdlib.h>
 
void StackInit(Stack* pstack) {
    pstack->head = NULL;
}
 
int SIsEmpty(Stack* pstack) {
    if (pstack->head == NULL)
        return TRUE;
    else
        return FALSE;
}
 
void SPush(Stack* pstack, Data data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
 
    newNode->next = pstack->head;
    pstack->head = newNode;
}
 
Data SPop(Stack* pstack) {
    if (SIsEmpty(pstack)) {
        printf("stack memory error!");
        exit(-1);
    }
 
    Data rdata;
    Node * rNode;
 
    rNode = pstack->head;
    rdata = pstack->head->data;
    
    pstack->head = pstack->head->next;
 
    free(rNode);
 
    return rdata;
}
 
Data SPeek(Stack* pstack) {
    if (SIsEmpty(pstack)) {
        printf("stack memory error!");
        exit(-1);
    }
 
    return pstack->head->data;
}
 cs

<ListStackBaseMain.c>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include "ListBaseStack.h"
 
int main(void)
{
    // Stack의 생성 및 초기화 ///////
    Stack stack;
    StackInit(&stack);
 
    // 데이터 넣기 ///////
    SPush(&stack, 1);  SPush(&stack, 2);
    SPush(&stack, 3);  SPush(&stack, 4);
    SPush(&stack, 5);
 
    // 데이터 꺼내기 ///////
    while(!SIsEmpty(&stack))
        printf("%d ", SPop(&stack)); 
 
    return 0;
}
 cs

'자료구조' 카테고리의 다른 글

4. 연결 리스트  (0) 2021.07.19
3. 배열 기반 리스트  (0) 2021.07.19
2. 재귀 (Recursion)  (0) 2021.06.27
1. 자료구조와 알고리즘의 이해  (0) 2021.06.27

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

 

11723번: 집합

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 알고리즘의 분류상 구현 문제로 문제에서 주어진 대로만 차분하게 구현하면 쉽게 해결할 수 있는 문제였습니다. 다만 실버 5 티어라는 난이도에 비해 정답률이 29%로 낮은 편인데 그 이유는 메모리 제한 때문이라 생각됩니다. 저 역시 pypy3로 풀었을 때 메모리 초과 판정을 받았고 pypy는 시간 복잡도가 좋은 대신 공간 복잡도 측면에서 불리하다는 사실을 알게 되어 python3으로 해결한 결과 정답 판정을 받을 수 있었습니다. 문제의 조건을 그대로 구현하면 되는 문제이기 때문에 해결방안은 따로 제시하지 않습니다.

소스코드
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
import sys
input = sys.stdin.readline
 
n = int(input())
s = set()
for i in range(n):
  a = input().split()
  if a[0] == 'empty' or a[0] == 'all':
    if a[0] == 'all':
      s = set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20])
    elif a[0] == 'empty':
      s = set()
  else:
    b = int(a[1])
    if a[0] == 'add':
      s.add(b)
    elif a[0] == 'check':
      if s.intersection(set([b])):
        print(1)
      else:
        print(0)
    elif a[0] == 'remove':
      if s.intersection(set([b])):
        s.remove(b)
    elif a[0] == 'toggle':
      if s.intersection(set([b])):
        s.remove(b)
      else:
        s.add(b)
 cs

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

백준 알고리즘 7576번: 토마토(Python)  (0) 2022.01.14
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.12
백준 알고리즘 14499번: 주사위 굴리기(Python)  (0) 2022.01.10
백준 알고리즘 2941번: 크로아티아 알파벳(Python)  (0) 2022.01.07
백준 알고리즘 14659번: 한조서열정리하고옴ㅋㅋ(Python)  (0) 2022.01.06

+ Recent posts

티스토리툴바