본문 바로가기
반응형

프로그래밍/알고리즘 문제39

[BOJ 2667 - 단지번호붙이기] BFS (Python) 문제 조건 위, 아래, 왼쪽, 오른쪽에 집이 있는지 탐색 쭈욱 이어진 곳은 하나의 단지로 세팅 (연결요소 개념) 핵심개념 위, 아래, 왼쪽, 오른쪽 이동을 위한 배열을 만든다. 이동을 하되, 범위를 벗어났는지 아닌지도 체크한다. 모든 정점을 한번씩 시작점으로 하여 탐색한다. 2차원 배열 활용하는 법을 익힌다. (생성, 입력받기, 1차원배열로 만들기 등) 문제풀이 (BFS) 재귀 없이 deque 활용하기 from collections import deque from collections import Counter from functools import reduce # 입력받기 n = int(input()) # 지도 입력받기 (2차원) a = [list(map(int,list(input()))) for _ .. 2019. 10. 3.
[B0J - 14888 연산자 끼워넣기(2)] 브루트포스(순열) python 문제조건 연산자를 N-1개 나열하여 숫자를 계산한다. (순열) 핵심개념 재귀함수와 check 배열을 사용하여 순열을 만들거나 재귀함수와 cnt 배열을 사용한다. (1) 재귀함수와 check배열 사용하는 방법 (시간초과가 나는데 ㅠㅠ) # 입력받기 n = int(input()) num = list(map(int, input().split())) cnt = list(map(int, input().split())) # 연산자 중에서 cal = [0] * cnt[0] + [1] * cnt[1] + [2] * cnt[2] + [3] * cnt[3] # n-1 개를 뽑은 순열 a = [0] * (n - 1) # 연산자 중복 체크용 check = [False] * (len(cal)) # 계산값 ans = [] # n.. 2019. 9. 29.
[BOJ-6603 로또] 브루트포스(조합) (python) 문제조건 k개 수 중에 6개를 고른다. (조합) 핵심개념 파이썬 itertools.combinations 라이브러리를 사용하거나 재귀함수를 이용하거나 next_permutations 함수를 구현하여 사용하는 방법이 있다. 코드 (1) 파이썬 itertools.combinations 라이브러리 사용하는 방법 from itertools import combinations while True: num = list(map(int, input().split())) if num[0] == 0: break #입력받은 수에서 (맨 왼쪽 제외) 6개를 선택하는 경우 for i in combinations(num[1:], 6): print(' '.join(map(str, i))) print() (2) 재귀함수 사용하는 방.. 2019. 9. 29.
[BOJ 15658] 연산자 끼워넣기(2) - python 문제조건 N개의 수가 주어진다. 연산자는 N-1개보다 더 많이 주어질 수 있다. N개의 수의 순서는 변하지 않는다. 연산자의 순서만 바뀐다. 핵심개념 연산자 개수 중에서 N-1개를 뽑아 순열을 구해야 한다. 이를 위해 DFS, 백트래킹을 활용하여 모든 경우의 수를 탐색한다. python 코드 N = int(input()) a = list(map(int,input().split())) cnt = list(map(int,input().split())) max_ans = -1000000000 min_ans = 1000000000 def dfs(idx, ans): global max_ans,min_ans if idx == N: max_ans = max(max_ans, ans) min_ans = min(min_a.. 2019. 9. 24.
[프로그래머스] kakao 2018 코딩테스트 - 후보키 (python) 다른사람 풀이 참고해서 다시 코딩 from itertools import combinations def solution(data): result = 0 col_cnt=len(data[0]) lst=list(range(0,col_cnt)) c_lst=[] final=[] for i in range(1,col_cnt+1): c=combinations(lst,i) c_lst.extend(c) # 유일성 만족하는 조합 찾기 for i in c_lst: final_tmp=[] for row in range(0,len(data)): tmp_lst=[] for t in i: tmp_lst.append(data[row][t]) final_tmp.append(tuple(tmp_lst)) #check (컬럼 조합한 값에서.. 2019. 9. 4.
[프로그래머스] kakao 2018 코딩테스트 - 오픈채팅방 (python) def solution(record): answer = [] id_nic={} # uid / 닉네임 딕셔너리 생성 for i in range(len(record)): temp=record[i].split(" ") if temp[0]!="Leave": id_nic[temp[1]]=temp[2] # 결과값 출력 for i in range(len(record)): temp=record[i].split(" ") if temp[0]=="Enter": answer.append(id_nic[temp[1]]+"님이 "+"들어왔습니다.") elif temp[0]=="Leave": answer.append(id_nic[temp[1]]+"님이 "+"나갔습니다.") return answer 아이디어 Enter 혹은 Chang.. 2019. 9. 3.
반응형

티스토리툴바