개발자 블로그

문제 설명 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 나의 풀이 from collections import deque def changing_graph_zero_one(graph, rain_amount): safety_graph = [[1]*len(graph[0]) for _ in range(len(graph))] for i in range(len(graph)): for j in range(len(graph[0])): if graph[i][j]

문제 설명 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 나의 풀이 from collections import deque def bfs(graph, q): dx = [-1,1,0,0] dy = [0,0,-1,1] while q: y, x = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

문제 설명 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 나의 풀이 from collections import deque def bfs(graph, start_node): if not graph[start_node[0]][start_node[1]]: return False q = deque() q.append(start_node) graph[start_node[0]][start_node[1]] = 0 dx = [-1,1,0,0] dy = [0,0,-1,1] while q: current_y, current_x = q.p..

문제 설명 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 나의 풀이 from collections import deque def bfs(graph, start_node): if graph[start_node[0]][start_node[1]] == "0": return False visited = [] q = deque() q.append(start_node) visited.append(start_node) graph[start_node[0]][start_node[1]] = "0" dx = [-1, 1, 0, ..

DFS # 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다! graph = { 1: [2, 5, 9], 2: [1, 3], 3: [2, 4], 4: [3], 5: [1, 6, 8], 6: [5, 7], 7: [6], 8: [5], 9: [1, 10], 10: [9] } visited = [] # 방문한 걸 저장하기 위한 배열 1. 우선 탐색 시작 노드를 1로 잡겠습니다! 2. 현재 방문한 노드인 1을 visited 에 추가합니다. # visited -> [1] 3. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들은 [2, 5, 9] 입니다. 2 에 방문합니다. 4. 현재 방문한 노드인 2을 visited 에 추가합니다. # visited -> [1, 2] 5. 인접한 노드들인 [..

문제 설명 더보기 추석 트래픽 이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다. 입력 형식 solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다. 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:..

흔히 우리가 탐색을 할 때, 모든 배열을 확인하는 방법을 지양한다. 예를 들어 100까지 수 중에서 하나를 골라 up/down 게임을 한다고 하자. 우리는 보통 중간부터 수를 불러 좁혀나가는 식으로 하는 것이 빠르다는 것을 알고 있다. 따라서 모든 배열을 탐색하는 배열의 길이만큼의 시간 복잡도 대신 log2n의 시간복잡도를 갖을 수 있다. 이를 코드로 구현해보자! # 이진 탐색 - 정렬이 되어있는 배열에서 가능 finding_target = 14 finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] def is_existing_target_number_binary(target, array): current_min_idx = 0..

DB DIAGRAM URI & Method Summary API endpoint method 회원가입 users/signup/ POST 로그인 users/login/ POST 로그아웃 users/logout/ POST 프로필 users//profile/ GET, PUT, DELETE 구매 목록 조회 users//purchaselist/ GET 판매 목록 조회 users//sellinglist/ GET 찜 목록 조회 users//likelist/ GET 상품 products/ POST, GET products// GET, PUT, DELETE 댓글 products//comments/ POST, GET products//comments// GET, PUT, DELETE 좋아요 products//like/ P..

보호되어 있는 글입니다.

컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다. 해쉬 자료구조는 파이썬에서 딕셔너리와 같다. key값으로 빠르게 해당하는 value를 찾고 저장할 수 있는 자료구조이다. key와 매핑된 벨류를 반환하기 때문에 모든 배열을 돌아보지 않고 조회가 가능하므로 상수 시간의 시간 복잡도를 갖고 있다. 알고리즘 문제를 풀다보면 시간 복잡도를 줄이기 위해 index()라는 함수보다 딕셔너리로 값들을 저장하곤 한다. 하지만 딕셔너리도 다소 메모리가 더 잡히는 부분 때문에 이러한 부분도 ..