문제에서 가장 중점적으로 봤던 부분 1. 첫 번째 주사위가 놓이는 방향 2. 주사위를 쌓았을 때 bottom과 top이 아닌 수 중에서 가장 큰 수가 더해지는 값이 된다는 점. 문제 풀이 방법 1. bottom의 인덱스가 0~6일 때 top의 인덱스를 구해주어 bottom과 top을 저장하는 백터에 넣어주었습니다. 2. bottom과 top이 모두 6이 아니라면 6을, bottom이 5, top이 6(bottom이 6, top이 5)의 상황인 경우 4를, 그 이외에는 5를 sum에 더해주었습니다. 3. 최종적으로 maxsum을 구해서 가장 큰 수를 출력합니다. #include #include #include using namespace std; int dia[10001][6]; vector vec[100..
Koala - 4기
생각해놓은 풀이는 여러가지가 될 수 있지만 두 가지 방법을 시도해보았습니다. 첫 번째 방법은 2개 2개 2개 짝을 짓고 이전 주사위의 맨 위의 값이 들어있는 짝을 제외한 4개중 가장 큰 값을 층마다 더해주고, 맨 위의 값이 들어있는 짝에 들어있는 맨 위의 값이 아닌 수가 곧 다음 주사위에서는 이전 주사위의 맨 위의 값이 되도록 코드를 짰습니다. from sys import stdin input=stdin.readline n=int(input()) stack=[] mx=0 for i in range(n): dice=list(map(int,input().split())) pair=[[dice[1],dice[3]],[dice[0],dice[5]],[dice[2],dice[4]]] stack.append(pai..
첫 번째 주사위를 어떻게 놓는지가 가장 중요해 보였다. 첫 번째 주사위의 윗면에 따라 나머지 위에 쌓이는 주사위의 옆면의 최대값은 고정이다. 맨 아래 놓인 주사위에 따라 최대값이 달라지기 때문에 처음 주사위의 모든 면을 확인해서 계산 후 6개의 결과 값들 중 max를 구하면 될 것이라 생각했다. 주사위의 반대 면을 어떻게 확인할까 검색해보니 ABCDEF 순으로 받는 것 보다는 ABCFDE 순으로 받으면 (i+3)%6의 공식이 성립했기 때문에 ABCFDE 순으로 받아서 풀었다. 한 주사위를 확인할 때는 top, bottom이 아닌 것 중에서 가장 큰 값으로 갱신시켰다 #include #include using namespace std; int main(){ ios_base::sync_with_stdio(0..
문제 링크 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 연산자 우선순위와 괄호를 고려하는 부분이 많이 까다로웠던 문제입니다. 😂 import sys input = sys.stdin.readline operators = {"/": 2, "*": 2, "+": 1, "-": 1, "(": 0} stack = [] foluma = input() for s in foluma: if s == "\n": continue if s.isalpha(): print(s, end="") elif s == "(": s..
스택 사용해야할 것 같다 A~Z는 그냥 바로 출력 * / 가 나오면 스택 스택이 비어있지 않고, top에 *나 /가 있는 경우 -> top을 출력하고 pop한다. 그 후 스택에 넣는다. +나 -가 나오면 스택에 넣는다. !empty -> 스택이 빌 때까지 top 출력 후 pop 그 후 스택에 넣는다. 스택에 ( 이 있는 경우 -> ( 가 나올 때까지 출력하고 pop한다. 그 후 스택에 넣는다. ( 가 나오면 스택에 넣는다. ) 가 나오면 ( 전까지 스택에 있는 값을 출력한다. 모든 과정이 끝났는데 스택에 값 존재하면 모두 출력 #include #include #include using namespace std; int main(){ string line; stack s; cin >> line; for(i..
후위 표기식 문제 정리 문제를 두 가지 방법으로 풀어보았습니다. 첫 번째는 switch case 문을 사용하여 모든 연산자에 대한 처리를 해주었고, 두 번째는 map을 사용하여 +, -, *, /에 우선순위를 미리 부여하여 문제를 풀었습니다. 첫 번째 방법 A-Z의 문자는 바로 출력 '(' 문자가 들어올 시 우선순위를 0으로 지정하여 stack에 push ')' 문자가 들어올 시 '('를 만나기 전까지 stack에 들어있는 연산자 pop +, -, *, /가 들어올 시 stack의 top에 있는 문자와 새로 들어온 문자의 우선순위를 비교하여 새로 들어온 문자의 우선순위가 top 문자의 우선순위와 같거나 작을 경우 stack의 top 문자 출력 stack에 남아있는 연산자가 있다면 마지막에 모두 출력 두 ..
정보 상인 호석 문제 정리 이번 문제는 우선순위 큐와 map을 사용하여 문제를 풀었습니다. key로 Name을 value로 우선순위 큐를 담아서 map을 구성해주었습니다. 가치 순으로 가장 비싼 정보 : 우선순위 큐를 떠올림 Name에 따라 정보 가치가 저장된다는 점에서 map을 떠올림 처음 제출했을 때에는 "큐에 남아 있는 정보 가치의 개수 < 호석이가 거래하려고 하는 정보 개수"를 고려해주지 못해 SegFault가 나왔었는데 그 부분 처리를 해주었더니 정답으로 인정이 되었습니다. 정보 상인 호석 소스 코드 #include #include #include #include using namespace std; int main(void) { map mp; int t; long long int sum = 0..
크게 봤을 때 정보를 저장하고, 원하는 만큼 삭제하는 문제였다. 이름, 정보의 개수, 정보의 가치가 가장 주된 내용이었다. 쿼리의 처음 입력 값이 1 일 때와 2일 때를 나눠 구분해 1이면 정보 저장 이름에 해당하는 정보들을 우선순위 큐에 집어 넣으면 된다고 생각했다. map query; 으로 선언해 해당 정보상인의 정보들을 저장한다. 2이면 정보 삭제를 하면 된다. 원하는 정보의 개수인 b 만큼 우선순위 큐에서 pop하면 된다. 우선순위가 정해져 있기 때문에 top()을 b번 pop한다 pop한 값들을 모두 더하면 답이 된다. 처음에는 아무 생각 없이 답을 int로 선언했다가 틀렸었다. 이를 long long으로 선언하니 풀렸다. #include #include #include #include #inc..
플로이드 알고리즘을 처음 써봐서 좀 해맸던 것 같다 adj는 소요 시간, route에는 이전 방문 집하장 INF를 987654321로 초기화 시켜놓았다. 1번부터 순서대로 경로에 추가 후 해당 집하장을 들리는 것과 현재 소요시간과 비교해서 더 작을 때 업데이트 #include #include #include #include #include #include using namespace std; #define INF 987654321; int adj[201][201]; int route[201][201]; int main(){ int n, m; cin>> n >> m; while(m--){ int v1, v2, w; cin >> v1 >> v2 >> w; adj[v1][v2] = w; adj[v2][v1] ..
자바스크립트를 주로 사용해와서 보자마자 아래와 같은 데이터 구조를 만들면 되겠구나! 생각했지만, 파이썬에서는 나름 생각할게 많았던 문제였습니다. const infos = { Cpp: [1, 2, 3, 4, 5], python: [1, 2, 3, 4] ... } 우선 구현해야 할 것은 명확했는데, 파이썬의 딕셔너리(C++의 맵과 유사합니다!)를 활용해 (키 : 값) 쌍을 (정보 이름 : 정보 값이 담긴 우선순위 큐) 형태로 만들어주면 될 것 같았습니다. 그래서 처음에는 infoMap = dict([name, infoHeap]) 처럼 코드를 작성해 문제를 풀려 했는데, 파이썬의 딕셔너리는 C++과 다르게 "문자열 : 리스트" 타입의 맵으로 초기화할수 없다는 것을 알게 되었습니다. 다만 초기화가 아닌, 빈 맵..
각 상인의 이름을 키로 갖고 우선순위 큐를 밸류로 갖는 맵, 딕셔너리를 만들면 되는 문제였습니다. 입력받은 첫 번째 값이 1인지 2인지 한번 나눠주고 그 다음 알맞게 우선순위 큐에 푸시해주고, 큐에 존재하는 원소의 개수보다 지워야 할 값의 개수가 많을 때만 생각해주면 간단했습니다. python from heapq import heappush,heappop from sys import stdin input=stdin.readline q=int(input()) total=0 shopkeeper={} for i in range(q): order=input().rstrip().split() if order[0]=='1': try: for i in range(3,len(order)): heappush(shopke..
힌트 1 더보기 시간 복잡도를 잘 생각하셔야 합니다! 만약 이미 90만 개의 원소가 배열에 있을 때, 나머지 쿼리 1만개에서 원소를 하나씩 넣고, 넣을 때마다 정렬한다고 합시다. 그렇게 되면 시간 복잡도는 대략 (10,000) * (100만 log 100만) 이 되어버립니다. 힌트 2 더보기 우선순위 큐(최대힙)의 원소 삽입에 걸리는 시간 복잡도는 logn입니다. 힌트 3 더보기 우리는 이 문제를 맵을 이용해 간단화 시킬 수 있습니다. 어떤 고릴라의 정보 배열을 나타낼 때 c++에서는 map 로 만든다면, 각 고릴라가 key값이 되고 해당 고릴라가 가진 정보들이 value가 됩니다. 문제 풀이 더보기 얼핏 보면 정렬 문제 같지만, 절대 정렬로 풀면 안되는 문제입니다. 이유는 힌트 1에 있습니다! 문제에서..
