본문 바로가기
728x90
반응형

코딩/이코테-파이썬32

구현: 기둥과 보 설치 (python) https://school.programmers.co.kr/learn/courses/30/lessons/60061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 기둥이 조건에 맞는지 확인하고 True,False로 리턴하는 함수 1개 보가 조건에 맞는지 확인하고 True,False로 리턴하는 함수 1개를 우선 만들었다 기둥 설치시 조건확인함수를 돌려 True일 때 설치했다 기둥 삭제시 기둥을 우선 삭제한 다음, 남은 기둥과 보에 대해 조건확인을 싹 다 돌려 하나라도 False를 반환하는 경우 기둥을 다시 추가하여 기둥삭제 명령을 무시하도록 했다 보 설치시 .. 2022. 8. 31.
이코테 구현: 자물쇠와 열쇠 def solution(key, lock): answer = False new_lock=[[0]*(2*len(key)-2+len(lock))for i in range(2*len(key)-2+len(lock))] for i in range(len(lock)): for j in range(len(lock)): new_lock[len(key)-1+i][len(key)-1+j]=lock[i][j] for i in range(len(key)-1+len(lock)-1): #열쇠 가로로 이동 for j in range(len(key)-1+len(lock)-1): #열쇠 세로로 이동 for k in range(4): #회전 4번 key=turn_90(key) #키 회전 #키 맞춰보기 for a in range(len(.. 2022. 8. 29.
이코테: 구현 - 자물쇠와 열쇠 https://school.programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음부터 다 구현하기는 힘들것같아서... 우선은 자물쇠와 키의 크기가 같을 때 회전만 해서 자물쇠를 따는걸 구현해보았다 def solution(key, lock): answer = False return answer def turn_90(key): #행과 열을 바꿔서 90도 회전 length=len(key) result=[] for i in range(length): tmp=[] for j in .. 2022. 8. 29.
문자열 압축 https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1글자씩 묶을 때, 2글자씩 묶을 때, . . . 각각을 다 계산해보고 가장 작은 값을 출력하도록 했다 내가 짠 코드는 실행이 안 돼서 결국 다른 코드를 참고했다 def solution(s): result=[] if len(s)==1: return 1 for i in range(1, len(s)//2+1): b='' cnt=1 tmp=s[:i] #시작부터i개만큼의 문자열 for j in range.. 2022. 8. 28.
무지의 먹방라이브 https://school.programmers.co.kr/learn/courses/30/lessons/42891 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 무지의 먹방 라이브 * 효율성 테스트에 부분 점수가 있는 문제입니다. 평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다. 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 .. 2022. 8. 24.
알고리즘 기출문제: 그리디2 볼링공 고르기 볼링공 개수n, 볼링공의 최대무게m이 주어지고 다음 줄에 각 볼링공의 무게가 주어진다 두 사람이 서로 다른 무게의 볼링공을 고르고자 할 때, 고를 수 있는 조합의 개수는? n,m=map(int,input().split()) balls=list(map(int,input().split())) result=0 for i in range(n-1): for j in range(i,n): if balls[i]!=balls[j]: result+=1 print(result) 2022. 8. 17.
알고리즘 기출문제: 그리디 1. 모험가 길드 n명의 모험가가 있다 각각의 모험가는 공포도가 있는데, 공포도가 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야 모험을 떠날 수 있다 최대 몇개의 모험가 그룹을 만들 수 있을까? n=int(input()) data=list(map(int,input().split())) data.sort() result=0 count=0 for i in data: count+=1 if count >= i: result+=1 count=0 print(result) 모험가를 한 명씩 데려와서 count를 세고 현재 모험가의 공포도보다 count가 크거나 같다면 result+=1, count는 초기화 한다 2. 곱하기 혹은 더하기 각 자리가 숫자로만 이루어진 문자열 S가 주어진다. 왼쪽부터 .. 2022. 8. 16.
기타 알고리즘: 투 포인터 알고리즘, 구간 합 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다 투 포인터 알고리즘을 잘 활용할 수 있는 문제로는 '특정한 합을 가지는 부분 연속 수열 찾기' 가 있다 1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다. 2. 현재 부분 합이 M과 같다면, 카운트한다. 3. 현재 부분 합이 M보다 작다면, end를 1 증가시킨다. 4. 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다. 5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다. n=5 #데이터의 개수 5개 m=5 #찾고자 하는 부분합 m=5 data=[1,2,3,2,5] #전체 수열 count=0 interval_sum=0.. 2022. 8. 15.
9. 기타 알고리즘: 소수 판별, 에라토스테네스의 체 알고리즘 소수: 1보다 큰 자연수 중에서 1과 자신을 제외한 자연수로는 나누어 떨어지지 않는 수 이걸 코드로 그대로 옮기면 def is_prime_number(x): for i in range(2,x): if x%i==0: return False return True 이렇게 간단하게 쓸 수 있다 숫자가 X일 때 시간복잡도는 O(X)가 된다 여기서 약수의 성질을 이용하면 시간복잡도를 줄일 수 있다 모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다 예를 들어 16의 약수는 1, 2, 4, 8, 16인데, 1*16=16, 2*8=16으로, 4를 기준으로 대칭이다 따라서 특정한 자연수의 모든 약수를 찾을 때, 가운데 약수(제곱근)까지만 확인하면 된다 이것을 소수판별 알고리즘에 적용시키면 import m.. 2022. 8. 14.
8. 기타 그래프 알고리즘 예제 3문제 (팀 결성, 도시 분할 계획, 커리큘럼) 팀 결성(union - find) n명의 학생이 있다 두 학생의 팀을 합치는 연산과 두 학생의 같은 팀 여부를 확인하는 연산이 있다 입력받아서 연산하고~ 같은팀 여부 확인 연산은 같은팀일 시 Yes, 아닐 시 No 출력 import sys input=sys.stdin.readline def find_parent(parent,x): if parent[x]!=x: parent[x]=find_parent(parent,parent[x]) else: return parent[x] def union_parent(parent,a,b): a=find_parent(parent,a) b=find_parent(parent,b) if a 2022. 8. 9.
8. 기타 그래프 이론: 위상 정렬 위상정렬은 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는'것임 사이클이 없는 방향그래프(DAG:Direct Acycle Graph) 에서 위상정렬 하는 방법 설명. 1. 진입차수가 0인 노드를 큐에 넣는다 2. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 이것을 큐가 빌 때까지 반복한다 만약 그래프에 사이클이 존재한다면.. 사이클에 포함되는 노드는 진입차수가 모두 1이상이 되므로 큐에 들어가지 못하고 정렬이 끝날것이다 from collections import deque v,e=map(int,input().split()) indegree=[0]*(v+1) graph=[[]for i in range(v+1)] for i in range(e): a,b=ma.. 2022. 8. 8.
8. 기타 그래프 이론: 크루스칼 알고리즘 크루스칼 알고리즘 최소 신장 트리를 찾는 알고리즘 최소 신장 트리는 사이클이 존재하지 않고 모든 노드가 연결되어 있어야 함 모든 도시가 연결되어야 하고 도로 건설 비용을 최소화 해야할 때 크루스칼 알고리즘을 사용하면.. 도로를 짓는 데 필요한 최소 비용을 계산할 수 있다 먼저 간선의 정보를 입력받는다(노드1,노드2,비용) 비용에 대하여 오름차순으로 정렬한다 비용이 적게 드는 순으로 노드1,노드2가 사이클이 아니라면(부모 노드가 같지 않다면) 노드 1,2를 union연산을 수행하고, 노드1,2의 부모노드가 같다면 무시한다 동그라미 안 숫자는 각 간선의 비용에 대하여 오름차순으로 번호를 매긴 것이고, 그래프에서 빨간 선은 연결된 것, 파란 선은 연결하지 않고 무시한 것이다 def find_parent(par.. 2022. 8. 8.
8. 기타 그래프 이론: 사이클 판별 def find_parent(parent,x): #연결된 부모 찾는거 if parent[x]!=x: parent[x]=find_parent(parent,parent[x]) return parent[x] def union_parent(parent,a,b): a=find_parent(parent,a) b=find_parent(parent,b) if a 2022. 8. 8.
8. 기타 그래프 이론: 서로소 집합 자료구조 union, find union,find def find_parent(parent,x): #연결된 부모 찾는거 if parent[x]!=x: parent[x]=find_parent(parent,parent[x]) return parent[x] def union_parent(parent,a,b): a=find_parent(parent,a) b=find_parent(parent,b) if a 2022. 8. 8.
최단 경로 알고리즘 예제: 미래 도시 n개의 회사가 있고 m쌍의 회사가 연결되어있다 (양방향으로 연결되어있다) 1번회사에서 출발해 k번 회사를 거쳐 x번 회사까지 가는데 걸리는 최단시간은? 나는 다익스트라 알고리즘을 이용해 풀었다 1에서 출발하여 k까지 가는 최단거리 + k에서 출발하여 x까지 가는 최단거리 라고 생각할 수 있고 다익스트라를 두 번 실행하면 답을 얻을 수 있다 import sys, heapq input=sys.stdin.readline n,m=map(int,input().split()) #노드의 개수n, 간선개수m graph=[[]for i in range(n+1)] for i in range(m): a,b=map(int,input().split()) #서로 연결된 두 회사 a,b graph[a].append(b) graph.. 2022. 7. 27.
최단 경로 알고리즘 예제: 전보 도시가 n개 있고 통로가 m개 있다. c도시에서 메세지를 보낼 건데, 총 몇 개의 도시에 메세지를 보낼 수 있으며 메세지가 도달하는데 걸릴 시간은 어떻게 되겠는가? 노드개수n, 간선개수m, 출발지점 c를 입력받고 c에서 출발하는 모든 최단거리를 계산하고, 최단거리가 INF가 아닌 값들의 개수, 최단거리 중 가장 큰 값을 찾아 출력하면 된다 import sys, heapq input=sys.stdin.readline INF=int(1e9) n,m,c=map(int,input().split()) #노드개수 n, 간선개수 m, 출발지점c graph=[[]for i in range(n+1)] #노드 연결정보를 저장할 그래프 for i in range(m): x,y,z=map(int,input().split()).. 2022. 7. 27.
최단 경로 알고리즘: 플로이드 워셜 모든 지점에서 다른 모든 지점까지의 최단거리를 구해야 하는 경우에 사용하는 알고리즘 graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b]) graph[a][b]는 a에서 b까지 가는 최단거리를 의미한다 a에서 b까지의 최단거리와, a에서k까지 갔다가 k에서 b 까지 가는 (k를 거쳐가는)최단거리를 비교해, 더 짧은 경로를 graph에 갱신시키는 방법이다 """ 시간복잡도가 O(N^3)이므로 간선의개수가 500개 이하일 때만 사용해야겠다 """ INF=int(1e9) n=int(input()) #노드개수 m=int(input()) #간선개수 graph = [[INF]*(n+1) for _ in range(n+1)] #2차원 거리리스트 for a in range(1,n.. 2022. 7. 27.
최단 경로 알고리즘: 다익스트라(Dijkstra) 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘으로 볼 수 있다.. 다익스트라 알고리즘의 원리 1. 출발 노드를 설정한다 2. 최단 거리 테이블을 초기화한다 (자기자신=0, 다른노드=무한으로 설정함) 3. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 위 과정에서 3번과 4번을 반복한다. 간단한 ver 파이썬 코드 import sys input = sys.stdin.readline INF = int(1e9) n,m = map(int,inpu.. 2022. 7. 26.
다이나믹 프로그래밍: 바닥 공사 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 이 바닥을 1x2의 덮개, 2x1의 덮개, 2x2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하라. n=int(input()) d=[0]*1000000 d[1]=1 d[2]=3 for i in range(3,n+1): d[i]=d[i-1] + d[i-2]*2 print(d[n]) d [i]=가로가 i일 때 바닥을 채우는 모든 경우의 수 d [i]=d [i-1] + d [i-2]*2 가로가 i일 때.. "i-1까지의 것" + "2x1 짜리 타일 1개"로 구성할 수도 있고 "i-2까지의 것" + "2x2 짜리 타일 1개"로 구성할 수도 있고 "i-2까지의 것" + "1x2 짜리 타일 2개"로 구성할 수도 .. 2022. 7. 20.
다이나믹 프로그래밍: 효율적인 화폐 구성 n종류의 화폐가 있다. 이 화폐들을 최소한으로 이용해서 m원을 만들 때 필요한 화폐의 개수는? 앞서 배운 다이내믹 프로그래밍 예제들처럼 보텀업 방식을 이용했다. 반복문을 이용하여 0원~m원까지 필요한 화폐 수를 차근차근 구하고, 이미 구했던 화폐 수를 이용하여 다음 값을 찾는 식으로 구성했다. n,m=map(int,input().split()) #화폐종류 n개, 목표 M원 list_coin=[] for i in range(n): list_coin.append(int(input())) d=[-1]*10001 for i in list_coin: d[i]=1 #동전 1개로 사용가능한 것 초기화함 for i in range(min(list_coin)+1,m+1): count=0 for coin in list_c.. 2022. 7. 19.
728x90
반응형

티스토리툴바