RUBY

출처:: https://www.acmicpc.net/problem/10825 분류:: 정렬 1. 문제 이해 및 해결과정 2. 풀이방법 1. 정렬 #국영수 #https://www.acmicpc.net/problem/10825 import sys sys.stdin = open("input.txt","r") n=int(input()) arr=[] for i in range(n): arr.append(input().split()) arr=sorted(arr,key= lambda x: (-int(x[1]),int(x[2]),-int(x[3]),x[0])) for student in arr: print(student[0]) 3. 오답원인 4. 알게된 점 정렬 시 key 값 설정하기 - 리스트 원소 정렬할 때는 so..

출처:: 삼성전자 SW역량테스트 분류:: DFS 1. 문제 이해 및 해결과정 2. 풀이방법 1.DFS #연산자 끼워넣기 #https://www.acmicpc.net/problem/14888 import sys sys.stdin = open("input.txt","r") n=int(input()) num=list(map(int,input().split())) op=list(map(int,input().split())) maxv=int(-1e9) minv=int(1e9) def DFS(d,value): global maxv,minv if d==(n-1): maxv=max(maxv,value) minv=min(minv,value) return else: for i in range(4): if op[i]>0: ..

출처:: 2020카카오 신입 공채 https://programmers.co.kr/learn/courses/30/lessons/60057?language=python3 분류:: 구현 1. 문제 이해 및 해결과정 2. 풀이방법 1. 구현 def solution(s): leng=len(s) answer=leng result=str() for i in range(1,leng//2+1): #i는 자르는 개수 cur=s[0:i] sum=1 for j in range(i,len(s),i): next=s[j:j+i] if cur==next: sum+=1 else: if sum>=2: result+=str(sum)+cur else: result+=cur cur=next sum=1 if sum>=2: result+=str..

출처:: 분류:: 위상정렬 알고리즘 1. 문제 이해 및 해결과정 - 각 노드에 대하여 인접한 노드를 확인 할 때 , 인접한 노드에 대하여 현재보다 강의시간이 더 긴 경우를 찾는다면, 더 오랜 시간이 걸리는 경우의 시간 값을 저장하는 방식으로 결과 테이블을 갱신하여 답을 구할 수 있다. - 위상 정렬을 수행하면서, 매번 간선 정보를 확인하여 결과 테이블을 갱신한다. 2. 풀이방법 1. 위상정렬 #커리큘럼 # import sys from collections import deque import copy sys.stdin = open("input.txt","r") ''' 5 10 -1 10 1 -1 4 1 -1 4 3 1 -1 3 3 -1 #출력 10 20 14 18 17 ''' n=int(input()) #..

출처:: https://www.acmicpc.net/problem/1647 분류:: 최소 신장 트리 1. 문제 이해 및 해결과정 - 전체 그래프에서 2개의 최소 신장 트리를 만들어야 한다. => 최소한의비용으로 2개의 신장 트리로 분할하려면 어떻게 하면 될것인지 - 크루스칼 알고리즘으로 최소 신장 트리를 찾고 가장 큰 비용을 가지는 간선을 제거하자 2. 풀이방법 1. 크루스칼 알고리즘 #도시 분할 계획 # ''' 7 12 1 2 3 1 3 2 3 2 1 2 5 2 3 4 4 7 3 6 5 1 5 1 6 2 6 4 1 6 5 3 4 5 3 6 7 4 #출력 8 ''' import sys sys.stdin = open("input.txt","r") n,m=map(int,input().split()) pare..

출처:: 분류:: union-find 1. 문제 이해 및 해결과정 - 서로소 집합 알고리즘 문제, n과 m의 범위가 모두 10,000이상 => 경로 압축 방식의 서로소 집합 자료구조를 이용하여 시간복잡도를 개선해야함 2. 풀이방법 1. union-find #팀 결성 # import sys sys.stdin = open("input.txt","r") #0번 부터 n번까지 팀 존재, m은 연산의 개수 n,m=map(int,input().split()) parent = [0]*(n+1) def find_parent(parent,x): if parent[x]!=x: parent[x]=find_parent(parent,parent[x]) return parent[x] def union_parent(parent,a..

출처:: M기업 코딩 테스트 분류:: 플루이드 워셜 알고리즘 1. 문제 이해 및 해결과정 - N의 범위가 100이하로 매우 한정적 2. 풀이방법 1. 플루이드 워셜 #미래도시 # import sys sys.stdin = open("input.txt","r") INF = int(1e9) #10억 #노드의 개수 및 간선의 개수를 입력받기 n,m=map(int,input().split()) graph = [[INF]*(n+1) for _ in range(n+1)] #비용은 0으로 초기화 for a in range(1,n+1): for b in range(1,n+1): if a==b: graph[a][b]=0 #간선 정보 입력받기 for _ in range(m): a,b=map(int,input().split(..

그래프 : 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조 - 알고리즘 문제에서 '서로 다른 대체(객체)'가 연결되어 있다' => 그래프 알고리즘 을 떠올려야한다 - 구현 방법) 1. 인접행렬 : 2차원 배열을 사용하는 방식 - O(V^2)만큼의 메모리 공간 필요 - 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1) 의 시간으로 알 수 있다. 2. 인접리스트: 리스트를 사용하는 방식 - O(E) 만큼의 메모리 공간 필요 - 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(V) 의 시간으로 알 수 있다. 서로소 집합(Disjoint Sets) : 서로소 집합이란 공통 원소가 없는 두 집합을 의미 ex) {1,2}, {3,4} * 서로소 집합 자료구조..