14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 안전 구역의 크기의 최댓값을 구하는 문제다. 벽은 3개 설치할 수 있는데, 벽은 안전구역에 설치할 수 있다. 전체 그래프 크기 N*M = 8*8 = n or ny = m: continue # 벽으로 간 경우 if graph[nx][ny] == 1: continue # 다른 바이러스의 칸으로 간 경우 # if graph[nx][ny] == 2: # continue if not visited[nx][ny]: if graph[nx][ny] == 0 or grap..
이코테
18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net BFS 문제다. 문제에서 모든 도로의 거리는 1이라고 했으니, 모든 간선의 비용이 1인 것이다. 이럴 때는 BFS를 활용해서 최단 거리를 구할 수 있다.(간선의 비용이 다른 경우에는 다익스트라) 노드의 개수 N은 300,000 이하이고, 간선의 개수 M은 1,000,000 이하이므로, 시간 복잡도는 O(N+M)에 의해 완전완전 가능하다. 기초적인 BFS 구현을 통해 풀 수 있는 문제다. 풀이..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현 문제다. 구현이 쉽지 않다. 내가 코드를 짜면 코드가 너무 복잡해진다. 그래서 풀이를 볼 수 밖에 없었다. 풀이 제한 조건을 봤을 때, weak 리스트와 dist 리스트의 길이가 매우 작으므로 완전 탐색 가능하다. -> 이건 알고 있었음 문제에서 찾고자 하는 것은 "투입해야 하는 친구 수의 최솟값"이다. 이 때 전체 친구의 수(dist의 길이)는 최대 8이므로, 모든 친구를 무작위로 나열하는 모든 순열의 개수를 계산하면 8P8 = 40,320으로 충분히 계산가능하다. -> 이것도 알고 있었음 그러므로 친..
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 이해는 쉽지만 구현이 까다로웠던 문제다. 완전탐색으로 풀려고하니, 내 구현에서는 4중 for문까지 들어가더라. 4중 for문으로 풀어도 되겠다는 생각이 들었던 이유는 대충 시간복잡도를 계산해보면 1초에 간당간당하게 들어간다고 판단했기 때문이다. 먼저 치킨 집을 최대 m개 뽑는다고 하는데 그래서 combinations를 사용했다. 먼저 전체 맵의 크기 N의 범위는 2
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현 문제다. 처음에는 기둥이나 보가 좌표에 있을 경우 1, 없을 경우 0으로 구현하려고 했으나, 그럴 경우에는 기둥과 보를 어떻게 구현해야 할지 모르겠더라. 그리고 기둥, 보 조건을 확인할 때, 인덱스를 넘어서는 경우는 또 조건문을 넣어서 구현해야하나? 라는 생각이 들었고 ,그럴 경우 코드가 너무 복잡해지는 것 같다는 생각이 들었다. 이러한 이유들로 끙끙대다가 풀이를 봤다. 풀이 코드 # 현재 answer 리스트 안의 구조물이 가능한 구조물인지 판단하는 함수 def is_possible(answer): fo..
