솔직히 백트래킹이나 완전탐색이 뭔지 대략적으로 느껴지긴 하지만 정확히 이게 ~다 라고 못하겠습니다.. 그냥 다 돌아본다 이런 느낌은 받고 있습니다. 이번 같은 경우는 dfs로 구현을 해보았는데 일단 입력받은 문자를 정렬시키고 사용할 문자의 인덱스값을 함수에 전달시켜줘서 무조건 이전 인덱스보다 뒤에, 즉 사전순으로 정렬되도록 하였습니다. 총 전달하는 값은 4개의 값을 전달시켜주었습니다. (현재 단어, 가장 마지막에 사용한 문자의 인덱스, 자음의 개수, 모음의 개수) 이렇게 4개를 전달시켜주었고, c와 단어의 길이가 같아지면 자음의 개수와 모음의 개수가 같다면 print하고 return 아니면 그냥 return 해주었습니다. 자음 모음 판별은 그냥 a e i o u가 들어간 리스트에 해당 스펠링이 들어있나 ..
전체 글
항공대 알고리즘 동아리 Koala 🥰이분 탐색 문제는 많이 안 풀어봐서 그런지 항상 볼 때마다 접근 방법이 확실하게 생각나지 않는 것 같습니다. 힌트 주신 거에서 or를 보지 못하고 우선순위 큐와 이분 탐색을 어떻게 같이 써야 되나 고민하느라 이상한 쪽에서 시간을 보냈습니다. 접근 방법 1. 좌표 사이 값의 최대가 최소가 되도록 만들어야 했기 때문에 우선은 사이 값이 큰 수부터 처리를 해주어야 한다고 생각했습니다.(우선순위 큐 사용) 2. 테스트 케이스에 따라서 좌표와 좌표 사이 중간에 휴게소를 세웠을 때 최소가 되지만 백준에서 예시로 들어준 테스트 케이스와 같이 좌표와 좌표 사이에 여러 개의 휴게소를 세워야 하는 경우도 있습니다. 이 부분 처리를 어떤 식으로 해줘야 할지 모르겠어서 올려주신 풀이를 참고하였습니다.(굉장히 참신했던 것 같아..
1.vector로 입력을 받고 순서대로 정렬 2. 구간 길이 구하기 ( 0 ~ L ) 사이의 모든 구간 포함 3. 구간의 길이와 그 구간 내의 구간 개수를 같이 저장해야 한 구간을 여러 번 나눴을 때 거리 계산 가능...? 4. 나눴을 때 소수 값이 나올 수 있다는 점 유의....(이거 때문에 총 8번 시도하게 됐다...) 처음 틀렸을 때 여러 케이스를 돌려보니 소수 값이 나온다는 것을 알게 됐다. 그래서 소수 값을 처리하기 위해 while(m--){ double maxlen = dist.top().first; int section = dist.top().second; dist.pop(); dist.push({(maxlen*section) / (section+1) , section+1}); } doubl..
제가 사용한 풀이는 다음과 같습니다. 1. n개의 휴개소 위치와 0(시작점)과 l(맨 끝)을 가지는 배열을 정렬시키면 0~l까지 휴게소 위치를 차례대로 알 수 있으므로 한 위치와 다음 위치의 차가 거리가 됩니다. 이렇게 n+1개의 원소를 갖는 배열을 통해 n개의 거리를 얻을 수 있었습니다. 2. 이제 거리를 우선순위 큐에 넣어주도록 했습니다. 이때 넣을 때는 파이썬은 낮은 값이 맨 앞에 오므로 튜플 형태로 (-1*거리,거리) 이런식으로 넣어줄 수 있습니다. 그리고 이후에 탐색에 사용할 값인 나뉘기 전의 거리값과 나눈 분모도 같이 넣어주었습니다. (-거리,거리,나누기 이전의 값,나눈 분모) 이런 형식으로 값을 저장할 것이고 맨 처음에는 나누기 이전의 값과 나눈 분모는 0을 넣어주었습니다. 3. 거리가 가장..
문제에서 가장 중점적으로 봤던 부분 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..
생각해놓은 풀이는 여러가지가 될 수 있지만 두 가지 방법을 시도해보았습니다. 첫 번째 방법은 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..