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

 

21608번: 상어 초등학교

상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호

www.acmicpc.net

문제 해결을 위한 과정

구현 유형에 해당하는 문제 입니다. 조건 자체는 복잡할 수 있으나, 조건에 유의하여 소스코드를 작성하면 해결할 수 있었습니다. (저의 경우 possible.append()를 graph[nx][ny] == 0 즉 비어있을 때만 해줘야하는데 실수로 그렇지 않은 경우에도 append할 수 있게 작성하여 여러번 시도하여 해결했습니다.)

소스코드
a = int(input())
n = a * a
graph = [[0] * a for _ in range(a)]
friend = []
happy = [0, 1, 10, 100, 1000]
for _ in range(n):
  friend.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for i in range(len(friend)):
  main = friend[i][0]
  bestFriend = friend[i][1:5]
  possible = []
  
  for j in range(a):
    for k in range(a):
      cnt = 0
      emptyCnt = 0
      if graph[j][k] == 0:
        for l in range(4):
          nj = j + dx[l]
          nk = k + dy[l]
          if nj < 0 or nk < 0 or nj >= a or nk >= a:
            continue
          if graph[nj][nk] in bestFriend:
            cnt += 1
          elif graph[nj][nk] == 0:
            emptyCnt += 1
            
        possible.append((cnt, emptyCnt, j, k))
  possible.sort(key=lambda x: (-x[0], -x[1], x[2], x[3]))
  j, k, x, y = possible[0]
  graph[x][y] = main
  
ans = 0
for i in range(a):
  for j in range(a):
    for k in range(len(friend)):
      if graph[i][j] == friend[k][0]:
        bestFriend = friend[k][1:5]
        cnt = 0
        for l in range(4):
          nx = i + dx[l]
          ny = j + dy[l]
          if nx < 0 or ny < 0 or nx >= a or ny >= a:
            continue
          if graph[nx][ny] in bestFriend:
            cnt += 1
        ans += happy[cnt]
print(ans)

 

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

백준 9663번: N-Queen(Python)  (0) 2024.04.06
백준 14891번: 톱니바퀴 (Python)  (0) 2024.04.04
백준 21610번: 마법사 상어와 비바라기(Python)  (0) 2024.04.02
백준 1238번: 파티(Python, cpp)  (0) 2022.02.27
백준 1753번: 최단경로(Python, cpp)  (0) 2022.02.22

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

 

21610번: 마법사 상어와 비바라기

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기

www.acmicpc.net

문제 해결을 위한 과정

구현 유형에 해당하는 문제 이므로 문제에서 주어진 조건을 따라서 차분하게 작성하면 어렵지 않게 풀 수 있는 문제 입니다. 문제의 예시를 보고 한 단계씩 확인하면서 작성하여 크게 어렵지 않게 해결할 수 있었습니다.

소스코드

n, m = map(int, input().split())
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))
moves = []
for _ in range(m):
  x, y = map(int, input().split())
  moves.append((x-1, y))
cloud = [(n-1, 0), (n-1, 1), (n-2, 0), (n-2, 1)]

def move_cloud(d, s):
  length = len(cloud)
  for i in range(length):
    x, y = cloud[0]
    cloud.pop(0)
    nx = x + dx[d] * s
    ny = y + dy[d] * s
    nx = nx % n
    ny = ny % n
    cloud.append((nx, ny))

for i in range(len(moves)):
  d, s = moves[i]
  move_cloud(d, s)
  for j in range(len(cloud)):
    x, y = cloud[j]
    graph[x][y] += 1
  for j in range(len(cloud)):
    x, y = cloud[j]
    count = 0
    for k in range(1, 8, 2):
      nx = x + dx[k]
      ny = y + dy[k]
      if nx < 0 or ny < 0 or nx >= n or ny >= n:
        continue
      if graph[nx][ny] >= 1:
        count += 1
    graph[x][y] += count 
  tempCloud = []
  for a in range(n):
    for b in range(n):
      if graph[a][b] >= 2 and (a, b) not in cloud:
        tempCloud.append((a, b))
  cloud.clear()
  for j in range(len(tempCloud)):
    x, y = tempCloud[j]
    cloud.append((x, y))
    graph[x][y] -= 2

ans = 0
for i in range(n):
  for j in range(n):
    ans += graph[i][j]
print(ans)

 

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

백준 14891번: 톱니바퀴 (Python)  (0) 2024.04.04
백준 21608번: 상어 초등학교(Python)  (0) 2024.04.03
백준 1238번: 파티(Python, cpp)  (0) 2022.02.27
백준 1753번: 최단경로(Python, cpp)  (0) 2022.02.22
백준 12100번: 2048(Python, cpp)  (0) 2022.02.21

서버 vs 클라이언트

클라이언트 : 서버로 요청하는 프로그램을 말함 ex) 웹 브라우저

서버: 클라이언트의 요청을 받아 처리 해주는 것

 

DB

DBMS: 데이터베이스 관리 시스템(Database Management System) 데이터의 보안, 무결성 유지, 동시성 제어, 백업 및 회복 기능. 일반적으로 RDBMS, NoSQL로 분류

RDBMS: 관계형 데이터베이스 시스템. 행 열 로 이루어짐 - 성능 향상 불리(스케일 업, 스케일 아웃)

NoSQL: 비 관계형 데이터베이스. 빅데이터, 분산 시스템 환경에서 대용량 처리에 용이 - 성능 향상 용이

 

IP & Port

IP는 아파트 건물

Port는 호 수 로 비유 가능

ex) localhost:8080 

 

라이브러리 vs 프레임워크 

라이브러리

1. 개발자가 필요할 때 사용할 수 있는 함수, 클래스의 모음

2. 개발자가 직접 호출

3. 개발자가 프로그램의 제어 흐름 관리

프레임워크

1) 제어흐름을 프레임워크가 관리(IOC)

2) 의존성 주입(DI)

 

CI/CD

Continuous Integration (CI - 지속적 통합):
여러 명의 개발자가 동시에 작업하는 경우 코드 충돌과 버그가 발생 가능. CI는 이러한 문제를 해결하기 위해 개발자가 작성한 코드를 자동으로 빌드하고 테스트하는 프로세스. CI를 통해 변경된 코드가 메인 코드베이스에 통합되기 전에 자동으로 테스트되므로 개발자들은 통합 문제를 빠르게 감지하고 해결 가능.


Continuous Deployment (CD - 지속적 배포):
Continuous Deployment는 CI 프로세스를 확장하여 테스트를 통과한 코드를 자동으로 프로덕션 환경에 배포하는 것을 의미.즉, 새로운 코드 변경이 테스트를 통과하면 자동으로 사용자에게 제공되어 실시간으로 업데이트가 이루어짐. 이를 통해 빠른 속도로 소프트웨어를 개발하고 배포할 수 있으며, 사용자들은 항상 최신 버전의 소프트웨어를 사용할 수 있다.

 

Spring

관점지향 프로그래밍: AOP 

관점을 분리하여(핵심 관점, 부가 관점 분리) 로직을 모듈화 하여 프로그램의 변경, 확장에도 유연하게 대응할 수 있어서 좋다.

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

 

1238번: 파티

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 역방향을 생각해야 하는 것이 가장 중요한 문제였습니다. 예제에서 파티가 열리는 장소가 2번이기 때문에 2를 다익스트라 알고리즘의 start로 넣어주면 2에서 다른 지점으로 가는 최소 거리를 구할 수 있고

역방향 그래프를 생성한 후 역방향의 그래프로 2를 다익스트라 알고리즘의 start로 넣어주면 다른 지점에서 2로 가는 최소 거리를 구할 수 있습니다.

소스코드 - 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
41
42
43
44
45
46
47
48
49
50
51
52
53
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
 
n, m, x = map(int, input().split())
graph = [[] for _ in range(1+n)]
graphR = [[] for _ in range(1+n)]
distance = [INF] * (n+1)
distanceR = [INF] * (n+1)
 
for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
  graphR[b].append((a, c))
  
def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start))
  distance[start] = 0
  while q:
    dist, now = heapq.heappop(q)
    if distance[now] < dist:
      continue
    for i in graph[now]:
      cost = dist + i[1]
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))
 
def dijkstraR(start):
  q = []
  heapq.heappush(q, (0, start))
  distanceR[start] = 0
  while q:
    dist, now = heapq.heappop(q)
    if distanceR[now] < dist:
      continue
    for i in graphR[now]:
      cost = dist + i[1]
      if cost < distanceR[i[0]]:
        distanceR[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))
        
dijkstra(x)
dijkstraR(x)
 
result = []
for i in range(1, n+1):
  result.append(distance[i] + distanceR[i])
 
result.sort(reverse = True)
print(result[0])
 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
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#define MAX 1001
using namespace std;
 
vector<pair<int, int>> graph[MAX];
vector<pair<int, int>> graphR[MAX];
vector<int> result;
int d[MAX];
int dR[MAX];
int n, m, x;
 
void dijkstra(int start) {
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));
    d[start] = 0;
    while (!pq.empty()) {
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        for (int i = 0; i < graph[now].size(); i++) {
            int cost = dist + graph[now][i].second;
            if (cost < d[graph[now][i].first]) {
                d[graph[now][i].first] = cost;
                pq.push(make_pair(-cost, graph[now][i].first));
            }
        }
    }
}
 
void dijkstraR(int start) {
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));
    dR[start] = 0;
    while (!pq.empty()) {
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        for (int i = 0; i < graphR[now].size(); i++) {
            int cost = dist + graphR[now][i].second;
            if (cost < dR[graphR[now][i].first]) {
                dR[graphR[now][i].first] = cost;
                pq.push(make_pair(-cost, graphR[now][i].first));
            }
        }
    }
}
 
int main(void) {
    scanf("%d %d %d", &n, &m, &x);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
        graphR[b].push_back(make_pair(a, c));
    }
 
    int INF = (int)1e9;
    fill(d, d + MAX, INF);
    fill(dR, dR + MAX, INF);
    dijkstra(x);
    dijkstraR(x);
 
    for (int i = 1; i < n+1; i++) {
        result.push_back(d[i] + dR[i]);
    }
    
    sort(result.begin(), result.end(), greater<int>());
    
    cout << result[0] << endl;
    return 0;
}
 cs

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

백준 21608번: 상어 초등학교(Python)  (0) 2024.04.03
백준 21610번: 마법사 상어와 비바라기(Python)  (0) 2024.04.02
백준 1753번: 최단경로(Python, cpp)  (0) 2022.02.22
백준 12100번: 2048(Python, cpp)  (0) 2022.02.21
백준 16236번: 아기상어(Python, cpp)  (0) 2022.02.15

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

 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가

www.acmicpc.net

문제 해결을 위한 과정

다익스트라 알고리즘을 이용하여 해결할 수 있는 문제였습니다. 다익스트라 기본 코드를 정확하게 알고 있다면 매우 쉽게 해결할 수 있었습니다.

소스코드 - 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
import heapq, sys
input = sys.stdin.readline
INF = int(1e9)
 
 
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
 
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
v, e = map(int, input().split())
start = int(input())
graph = [[] for _ in range(v+1)]
distance = [INF] * (v+1)
 
for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
 
dijkstra(start)
 
for i in range(1, v+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[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
#include <bits/stdc++.h>
#define MAX 20001
#define INF (int)1e9
using namespace std;
vector<pair<int, int> > graph[MAX];
int d[MAX];
int v, e;
 
void dijkstra(int start) {
    priority_queue<pair<int, int> > pq;
    pq.push({ 0, start });
    d[start] = 0;
 
    while (!pq.empty()) {
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        if (d[now] < dist)
            continue;
        for (int i = 0; i < (signed)graph[now].size(); i++) {
            int cost = dist + graph[now][i].second;
            if (cost < d[graph[now][i].first]) {
                d[graph[now][i].first] = cost;
                pq.push({ -cost, graph[now][i].first });
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> v >> e;
    int start;
    cin >> start;
    fill(d, d + MAX, INF);
 
    for (int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
    }
 
    dijkstra(start);
 
    for (int i = 1; i <= v; i++) {
        if (d[i] == INF) {
            cout << "INF" << "\n";
        }
        else {
            cout << d[i] << "\n";
        }
    }
    return 0;
}
 cs

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

백준 21610번: 마법사 상어와 비바라기(Python)  (0) 2024.04.02
백준 1238번: 파티(Python, cpp)  (0) 2022.02.27
백준 12100번: 2048(Python, cpp)  (0) 2022.02.21
백준 16236번: 아기상어(Python, cpp)  (0) 2022.02.15
백준 숨바꼭질 1697번: 숨바꼭질(Python, cpp)  (0) 2022.02.04

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

 

12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 백트레킹 및 dfs 방식으로 해결할 수 있었다. dfs함수를 짜는 건 어렵지 않았지만 이동하는 함수 moveGraph 함수는 작성하기 어려웠다. 다만 차근차근 조건을 따져가며 작성하니 생각보다는 어렵지 않았던 문제였다. https://chldkato.tistory.com/163 이 분의 포스팅을 참조하여 소스코드를 작성하였다. 구현 유형을 조금 더 많이 접하여 친숙해진다면 보다 쉽게 해결할 수 있을것으로 기대된다.

소스코드 - python
import copy

def move(dir): # n e s w
    if dir == 0:
        for j in range(n):
            idx = 0
            for i in range(1, n):
                if graph[i][j] != 0: # if not 0
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[idx][j] == temp:
                        graph[idx][j] *= 2
                        idx += 1
                    elif graph[idx][j] == 0:
                        graph[idx][j] = temp  
                    elif graph[idx][j] != temp:
                        idx += 1
                        graph[idx][j] = temp
                        

    elif dir == 1:
        for i in range(n):
            idx = n-1
            for j in range(n-2, -1, -1):
                if graph[i][j] != 0: # if not 0
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[i][idx] == temp:
                        graph[i][idx] *= 2
                        idx -= 1
                    elif graph[i][idx] == 0:
                        graph[i][idx] = temp
                    elif graph[i][idx] != temp:
                        idx -= 1
                        graph[i][idx] = temp
                        
    
    elif dir == 2: # s
        for j in range(n):
            idx = n-1
            for i in range(n-2, -1, -1):
                if graph[i][j] != 0:
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[idx][j] == temp:
                        graph[idx][j] *= 2
                        idx -= 1
                    elif graph[idx][j] == 0:
                        graph[idx][j] = temp
                    elif graph[idx][j] != temp:
                        idx -= 1
                        graph[idx][j] = temp
                        

    elif dir == 3: # w
        for i in range(n):
            idx = 0
            for j in range(1, n):
                if graph[i][j] != 0:
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[i][idx] == temp:
                        graph[i][idx] *= 2
                        idx += 1
                    elif graph[i][idx] == 0:
                        graph[i][idx] = temp
                    elif graph[i][idx] != temp:
                        idx += 1
                        graph[i][idx] = temp
                        

def dfs(count):
    global ans, graph
    if count == 5: # 5인 경우
        for i in range(n):
            ans = max(ans, max(graph[i]))
        return

    copyGraph = copy.deepcopy(graph)
    for i in range(4):
        move(i)
        dfs(count + 1)
        graph = copy.deepcopy(copyGraph)
        

n = int(input())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))
ans = 0
dfs(0)
print(ans)
소스코드 - c++
#include <bits/stdc++.h>
#define MAX 21	
using namespace std;

int n;
int graph[MAX][MAX];
int ans;

void moveGraph(int dir) { // N, E, S, W
	if (dir == 0) {
		for (int j = 0; j < n; j++) {
			int idx = 0;
			for (int i = 1; i < n; i++) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[idx][j] == temp) {
						graph[idx][j] *= 2;
						idx += 1;
					}
					else if (graph[idx][j] == 0)
						graph[idx][j] = temp;
					else {
						idx += 1;
						graph[idx][j] = temp;
					}
				}
			}
		}
	}

	else if (dir == 1) {
		for (int i = 0; i < n; i++) {
			int idx = n-1;
			for (int j = n-2; j > -1; j--) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[i][idx] == temp) {
						graph[i][idx] *= 2;
						idx -= 1;
					}
					else if (graph[i][idx] == 0)
						graph[i][idx] = temp;
					else {
						idx -= 1;
						graph[i][idx] = temp;
					}
				}
			}
		}
	}

	else if (dir == 2) {
		for (int j = 0; j < n; j++) {
			int idx = n-1;
			for (int i = n-2; i > -1; i--) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[idx][j] == temp) {
						graph[idx][j] *= 2;
						idx -= 1;
					}
					else if (graph[idx][j] == 0)
						graph[idx][j] = temp;
					else {
						idx -= 1;
						graph[idx][j] = temp;
					}
				}
			}
		}
	}

	else {
		for (int i = 0; i < n; i++) {
			int idx = 0;
			for (int j = 1; j < n; j++) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[i][idx] == temp) {
						graph[i][idx] *= 2;
						idx += 1;
					}
					else if (graph[i][idx] == 0)
						graph[i][idx] = temp;
					else {
						idx += 1;
						graph[i][idx] = temp;
					}
				}
			}
		}
	}
}

void dfs(int count) {
	if (count == 5) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				ans = max(ans, graph[i][j]);
			}
		}
		return;
	}

	int copyGraph[MAX][MAX] = { 0, };
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			copyGraph[i][j] = graph[i][j];
		}
	}

	for (int k = 0; k < 4; k++) {
		moveGraph(k);
		dfs(count + 1);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				graph[i][j] = copyGraph[i][j];
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j];
		}
	}
	dfs(0);
	cout << ans;
	return 0;
}

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

백준 1238번: 파티(Python, cpp)  (0) 2022.02.27
백준 1753번: 최단경로(Python, cpp)  (0) 2022.02.22
백준 16236번: 아기상어(Python, cpp)  (0) 2022.02.15
백준 숨바꼭질 1697번: 숨바꼭질(Python, cpp)  (0) 2022.02.04
백준 알고리즘 11052번: 카드 구매하기(Python)  (0) 2022.02.02

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

 

코딩테스트 연습 - 신고 결과 받기

문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의

programmers.co.kr

문제 해결을 위한 과정

문제의 범위에서 알 수 있듯이 단순하게 리스트를 이용하여 해결하면 시간 초과 판정을 받는 문제였습니다. 따라서 dictionary를 이용하여 해결해야 합니다.

소스코드
def solution(id_list, report, k):
  report = list(set(report))
  rCount = {string:0 for string in id_list}
  answer = {string:0 for string in id_list}
  for temp in report:
    user, rUser = temp.split()
    rCount[rUser] += 1

  for temp in report:
    user, rUser = temp.split()
    if rCount[rUser] >= k:
      answer[user] += 1

  ans = list(answer.values())
  return ans

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

프로그래머스 전화번호 목록(Python)  (1) 2024.04.07
프로그래머스 의상(Python)  (0) 2024.04.06
실패율 (Python)  (0) 2021.01.11
가사 검색 (Python)  (0) 2020.12.17
블록 이동하기 (Python)  (0) 2020.12.07

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

 

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가

www.acmicpc.net

문제 해결을 위한 과정

구현 유형에 해당하는 문제 이므로 문제에서 주어진 조건을 따라서 차분하게 작성하면 쉽게 해결할 수 있는 문제 입니다. bfs를 통해 이동할 수 있는 구역을 탐색한 후 먹을 수 있는 물고기들을 배열에 담아 정렬 후 가장 첫번째에 있는 물고기를 먹으면 되는 문제 입니다.

소스코드 - python
from collections import deque

def bfs(x, y, size, visited):
  q = deque()
  q.append((x, y))
  count = 0
  visited[x][y] = 1
  while q:
    for _ in range(len(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] <= size and visited[nx][ny] == 0:
          q.append((nx, ny))
          visited[nx][ny] = 1
          if 0 < graph[nx][ny] < size:
            eatable.append((count+1, nx, ny))
    count += 1

n = int(input())
graph = []
x = 0
y = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
size = 2 
eatable = []

for i in range(n):
  graph.append(list(map(int, input().split())))
  for j in range(n):
    if graph[i][j] == 9:
      x, y = i, j
      graph[i][j] = 0

timeInfo = 0
eatCount = 0
while True:
  visited = [[0] * n for _ in range(n)]
  bfs(x, y, size, visited)
  if len(eatable) == 0:
    print(timeInfo)
    break
  eatable.sort()
  dist, xPos, yPos = eatable[0]
  eatable = []
  x, y = xPos, yPos
  graph[x][y] = 0
  timeInfo += dist
  eatCount += 1
  if eatCount == size:
    size += 1
    eatCount = 0
소스코드 - c++
#include <bits/stdc++.h>

using namespace std;

int graph[20][20];
int visited[20][20];
int n;
int sizeOfShark;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
vector<tuple<int, int, int>> eatable; // 거리, x좌표, y좌표

void bfs(int xPos, int yPos) {
	queue<pair<int, int>> q;
	q.push(make_pair(xPos, yPos));
	visited[xPos][yPos] = 1;
	int num = 0;
	int distance = 0;

	while (!q.empty()) {
		num = q.size();
		for (int i = 0; i < num; i++) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
					continue;
				}
				if (graph[nx][ny] <= sizeOfShark && visited[nx][ny] == 0) {
					q.push(make_pair(nx, ny));
					visited[nx][ny] = 1;
					if (0 < graph[nx][ny] && graph[nx][ny] < sizeOfShark) {
						eatable.push_back(make_tuple(distance + 1, nx, ny));
					}
				}
			}
		}
		distance += 1;
	}
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	int x = 0, y = 0; // 상어 좌표
	sizeOfShark = 2; // 초기 상어 크기

	for (int i = 0; i < n; i++) { 
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j]; // 그래프 입력 받기
			if (graph[i][j] == 9) { // 상어 위치인 경우
				x = i;
				y = j;
				graph[i][j] = 0;
			}
		}
	}

	int timeInfo = 0;
	int eatCount = 0;

	while (true) {
		fill(&visited[0][0], &visited[19][20], 0);
		bfs(x, y);
		if (eatable.size() == 0) {
			cout << timeInfo;
			break;
		}
		sort(eatable.begin(), eatable.end());
		int dist = get<0>(eatable[0]);
		int xPos = get<1>(eatable[0]);
		int yPos = get<2>(eatable[0]);
		eatable.clear();
		x = xPos;
		y = yPos;
		graph[x][y] = 0;
		timeInfo += dist;
		eatCount += 1;
		if (eatCount == sizeOfShark) {
			sizeOfShark += 1;
			eatCount = 0;
		}
	}
	return 0;
}

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

백준 1753번: 최단경로(Python, cpp)  (0) 2022.02.22
백준 12100번: 2048(Python, cpp)  (0) 2022.02.21
백준 숨바꼭질 1697번: 숨바꼭질(Python, cpp)  (0) 2022.02.04
백준 알고리즘 11052번: 카드 구매하기(Python)  (0) 2022.02.02
백준 알고리즘 9461번: 파도반 수열(Python)  (0) 2022.01.31

+ Recent posts

티스토리툴바