전체

백준 18243 Small World Network(플로이드-와샬, BFS)

https://www.acmicpc.net/problem/18243 18243번: Small World Network 첫 번째 줄에 지구에 있는 사람의 수 N과 친구 관계의 개수 K가 주어진다. 모든 사람은 1부터 N까지 번호가 매겨져 있다. (1 ≤ N ≤ 100, 0 ≤ K ≤ N×(N-1)/2) 두 번째 줄부터 K+1번째 줄까지 친구 www.acmicpc.net import sys n, k = list(map(int,input().split())) edges = [list(map(int,input().split())) for _ in range(k)] INF = sys.maxsize def make_graph(): graph = [[INF] * n for _ in range(n)] for frm, ..

10816 숫자 카드 2(Hashmap, Counter)

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net #단순 리스트 탐색 n = int(input()) data1 = list(map(int,input().split())) m = int(input()) data2 = list(map(int,input().split())) for i in data2: temp = data1.count(i) print(temp, end=' ') N과 M이 500,000이기 때문에 단순..

백준 1764 듣보잡(set() 자료형)

그냥 단순하게 중복을 제외시키는 문제이지만 list를 이용하여 if - in 을 이용하면 시간초과가 난다. #시간초과 import sys input = sys.stdin.readline n,m = list(map(int,input().split())) data = [] data1 = [] for _ in range(n): data.append(input()) for _ in range(m): data1.append(input()) res = 0 ans = [] for i in data: if i in data1: res += 1 ans.append(i) print(res) ans.sort() for i in ans: print(i) 따라서 집합 자료형을 써서 교집합의 성질을 이용하면 쉽게 풀 수 있다. ..

백준 1780 종이의 개수

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 종이에 써져있는 숫자가 모두 같다면 그걸 하나로 보고 아니면 9개로 자른다. 9개로 자른다는것은 사각형의 좌측상단. 즉 처음 시작점에 대한 좌표를 알아내면 된다. 각 좌표는 (x + i * n//3, y + j * n//3)라는 규칙을 가지고 있다. 처음에 0,0으로 시작해서 0,0이 -1, 0, 1인지 기준을 잡은다음에 n x n까지 돌리는데 만약 1개라도 잘못 나오게 된다면 그 즉시..

백준 2667 단지번호붙이기(BFS, DFS)

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제를 보면 그래프 문제라는걸 바로 알 수 있고 dfs, bfs로 풀어야함을 알 수 있다. 0으로 구분되어져 있는 단지는 몇개인지 모르기 때문에 처음 1을 찾아줘서 거기서 탐색을 진행해 0으로 만들어주면 다음 단지를 찾을 때 방금 탐색했던 단지는 고려하지 않아도 됨을 알 수 있다. BFS 이용 from collections import deque def bfs(x, y): dx = [-1, 1, 0..

백준 18111 마인크래프트

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 일단 땅고르기를 위해 가장 최소의 시간을 구하기 위해서는 여러 방법이 있었다. 1. ground 2차원 배열에서 중간값을 찾아서 그 중간값을 기준으로 잡고 땅고르기를 하기(이분탐색) ground의 min값 ~ max값 사이의 range를 돌면서 그때 해당하는 조건에 대해서 테스트하는것도 좋은 방법 n, m, b = list(map(int, input().split())) ground = [lis..