후위 표기식 문제 정리 문제를 두 가지 방법으로 풀어보았습니다. 첫 번째는 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에 있습니다! 문제에서..
이번 문제는 풀기에 난이도가 좀 높았던 것 같습니다. 아직 구현을 잘 못해서 그런지 시뮬레이션이나 브루트포스 같이 구현 비중이 높은(?) 문제가 나오면 항상 어렵다고 느끼게 되네요. 다른 분들이 푼 것을 참고해서 이해하고 풀어보았습니다. 정리 문제를 풀면서 제일 까다로웠던 부분은 블록 그룹을 찾아주는 부분이었습니다. 처음 접근 방식은 bfs로 행, 열 좌표, 블록 그룹과 무지개 블록 개수, 블록 그룹 개수를 찾아주었습니다. 행 열 좌표를 찾으려고 했던 이유는 조건 1번 때문이었는데요. 나중에 생각해보니 왼쪽 위부터 순차적으로 내려오기 때문에 무지개 블록 수와 블록 그룹의 개수가 같다면 마지막 블록 그룹이 저장될 수밖에 없었습니다. 일반 블록은 한 번 방문하면 또다시 방문할 수 없지만, 무지개 블록의 경우..
삼성기출문제집에서 본 기억이 있었습니다. 그리고 그 중 제가 풀어본 것들과 비슷하게 하루종일 구현하고 나면 한번에 끝나는 법이 없고 수정하는데도 한참 걸렸습니다... 중력, 회전, 조건에 맞는 bfs와 리턴되는 값 이것들만 잘 설계하면 풀릴 문제라고 생각했습니다. 일단 중력부터 구현해주었습니다. 밑에서부터 올라오다 조건에 맞는 값을 찾으면 다른 블럭이 있거나 -1 또는 맨밑일때 까지 그 값의 위치를 내려주었습니다. def gravity(): for i in range(n-1,-1,-1): for j in range(n): if board[i][j]>=0: start=i while True: if 0
아직 노드나 에지같은 개념을 잘 몰라서 플루이드 워셜같은 개념을 이해하기 힘들었습니다. 이해가 완벽하지 않아서 엄청 해매게 되었습니다... 자료구조 개념을 공부할 필요를 느꼈습니다. 문제를 총 2가지 방법으로 풀었습니다. 첫 번째 방법은 다익스트라를 모든 적하장마다 해 주는 방법입니다. from sys import stdin from heapq import heappush,heappop from math import inf input=stdin.readline n,m=map(int,input().split()) time_table={i:[]for i in range(n)} route_table=[[0 for i in range(n)]for j in range(n)] for i in range(m): x,..
정리 이번 문제는 플로이드-와샬을 사용해서 풀었습니다. 전에 3문제 정도 플로이드-와샬과 관련된 문제를 전에 풀어봤었는데 그래서인지 다익스트라보다는 조금 더 친숙한 감이 있기도 했고, 경로표의 형태를 보니까 플로이드-와샬로 풀어도 무방할 것 같았습니다. 다른 건 괜찮았는데 마지막에 조금 헤맸던 부분이 1->2->5->6과 같이 2개 이상의 노드를 거쳐서 갔을 때 최단거리가 나오는 부분이었는데요. 처음에 짰던 코드로 돌렸을 때에는 2가 아닌 계속 5(도착 노드 바로 전 노드)가 나왔습니다. 어떤 식으로 접근을 해야 할지 감이 잡히지 않아서 이 부분 풀이를 참고했는데, road 배열(최단 경로를 가기 위해 처음 방문하는 노드를 담은 배열)의 경우 [i][k]를 구해주면 최단거리로 가기 위해서 제일 처음 방문..
문제 링크 : https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 1753번처럼 한 노드에서 다른 노드들까지의 최단거리를 찾되, 모든 노드에 대해 이를 반복해 풀 수 있는 문제입니다. 다만 두 가지 함정이 숨어 있었는데요, 한번 천천히 알아보도록 하겠습니다. 이번 답안은 다익스트라 입문 문제인 1753번 코드를 많이 참고하면서 완성했는데요, 첫 번째 함정은 이번 문제는 그래프가 양방향 그래프가 된다는 것입니다. 1753번에서는 단순히 한 노드..
