본문 바로가기
728x90

TIL - 프로그래밍/Python 알고리즘198

[백준] 2178. 미로탐색 -Python https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net que # 미로 크기 N*M # 1이동, 0이동X # (1,1)출발 -> (N,M) 도착 : 이동 중 지나야 하는 최소의 칸 수 구하기 # 칸 셀 때 시작과 도착 포함 N,M = map(int,input().split()) maze = [list(map(int,input())) for _ in range(N)] # 최소이동거리 찾는 거니깐 큐 # (행, 열, 이동한 칸 수) # 이동한 칸 수(시작 위치 포함이므로 1부터 시작) .. 2022. 5. 30.
[프로그래머스] Lv.1 신고 결과 받기 - Python https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 코드 def solution(id_list, reports, k): N = len(id_list) answer = [0] * N # 신고 당한 사람 reported = [] # {신고 한 사람 : 신고 당한 사람} reportDic = {id: [] for id in id_list} # set으로 중복 제거 for i in set(reports): rep.. 2022. 5. 29.
[프로그래머스] Lv.1 신규 아이디 추천 - Python https://programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 코드 def solution(new_id): answer = '' # 1. 모두 소문자 new_id = new_id.lower() # 2. 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)만 허용 no = new_id.maketrans('~!@#$%^&*()=+[{]}:?,/',' ') new_id = new_id.translate(no).re.. 2022. 5. 27.
[프로그래머스] Lv.1 실패율 - Python https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 코드 def solution(N, stages): p = [[0,0] for _ in range(N+1)] p[0][1] = len(stages) for i in range(1,N+1): # 도달했으나 아직 클리어하지 못한 플레이어 수 p[i-1][0] = stages.count(i) # 도달한 사람 p[i][1] = p[i-1][1]-p[i-1][0] # 실패.. 2022. 5. 21.
[프로그래머스] Lv.2 문자열 압축 - Python https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 코드(for문 사용) def solution(s): # 최초에 문자열이 분할이 안되면 결국 입력된 문자열의 길이가 최소의 길이가 됨 answer = len(s) # 문자열을 앞출할때 최소단위는 1에서 문자열길이의 반이다 for step in range(1, len(s) // 2 + 1): # 예를 들어 aaa 면 3a abcabc면 2abc 지만 abcd.. 2022. 5. 12.
알고리즘 - 플로이드 플로이드 모든 노드에서 다른 모든 노드까지 가는데 최소비용, O(V^3) 다익스트라 : 한 노드 -> 다른 모든 노드, O(ElogV) 작동원리 노드 j -> 노드 i 비용 배열 만들기, 초기값 INF 간선의 값을 비용 배열에 반영 모든 노드에 대해 해당 노드 거쳐서 가서 비용 작아질 경우 값 갱신 import sys INF = sys.maxsize # 초기값 INF rs = [[INF]*(n+1) for _ in range(n+1)] # 자기 자신으로 가는 건 0 for i in range(1,n+1): rs[i][i] = 0 for i in range(m): # a에서 b로 가는데 비용(혹은 거리) c a,b,c = map(int,input().split()) # 만약 a에서 b로 가는 길이 여러개이.. 2022. 5. 5.
반응형

티스토리툴바