https://www.acmicpc.net/problem/17281 안녕 풀이 알고리즘 BruteForce + Simulation 시간복잡도 50(이닝수) * 27(최악의 simulation : 3 아웃되는 동안 모든 타자가 타석에 서는 경우) * 8팩토리얼(타자 순서 정하는 모든 경우의 수) = 5500만 정도 함수 getResult : 타자 순서를 정하고 기저조건에서 점수를 얻어와 최대 점수를 반환하는 함수 playGame : 기저조건이 되었을 때 문제의 조건에 맞게 이닝별로 점수를 계산해서 반환하는 함수 movePlayer : 이닝별로 playGame에서 Simulation을 할 때 아웃이 아닌 경우에 1~3루, 홈 에 선수들을 옮기는 함수 코드 //! 2020.02.20 ~ 2020.02.21 /..

https://www.acmicpc.net/problem/16637 풀이 Algorithm BruteForce + Simulation inData : 초기 input 수식 check : 괄호를 넣을 때 앞에 위치하는 숫자의 index에 true값을 넣어둘 변수 numbers : inData 에서 숫자만 빼서 저장한 변수 calcs : inData 에서 수식만 빼서 저장한 변수 함수 changeArr : inData에서 numbers와 calcs를 만드는 함수 calculate : 수식, 숫자 2개를 받아서 수식에 맞는 연산을 한 후 결과를 반환하는 함수 getCalcRet : 괄호를 넣을 위치를 지정한 이후에 그에 맞게 처음부터 끝까지 연산한 값을 반환하는 함수 연산하는 방식은 다음과 같다. 첫번째 숫자..

2020.02.18 algospot / LIS 풀이 수열이 맨 왼쪽부터 하나씩 들어온다고 했을 때,다음 숫자가 들어왔을 때 그보다 작은 숫자들 중 최대인 녀석을 찾고 거기에 +1 한 값과 DP에 써져있는 값을 비교해서 큰 녀석을 DP에 update 한다. 이와 같은 풀이를 진행하면 C = 50, N = 500, 모든 수가 1~ 100000을 다 지나간다고 했을 때 대략 50 * 500 * 100000 정도의 시간복잡도가 될 거고 이는 25억이 되어 시간초과가 발생할 거라 생각했다. update하면서 가장 큰 최댓값을 기억해두고 마지막에 이를 출력한다. 해당 숫자를 맨 오른쪽 끝으로 하는 수열의 길이를 DP에 적어둔다. 1번의 알고리즘에서 들어온 숫자를 DP에 update하는 알고리즘은 동일하지만 들어온 ..

2020.02.18 백준17135 캐슬디펜스 풀이 궁수 위치 3개를 뽑는 경우의 수를 조합으로 찾는다. simulation을 이용해 그 때 제거한 적의 수를 구하고 경우의 수 중 최댓값을 찾는다. 변수 inMap : 초기 map 상태 nextMap : 게임을 진행하면서 변화하는 map length : 각 열에서 가장 위에있는 적부터 옮길 수 있도록 하기 위해서 맨 위 행 번호를 기록한 변수 nextLen : 초기 길이 변수 만큼만 적을 옮기도록 최적화하기 위해 변화하며 사용할 length 변수 check : 처음 input에서 이미 담은걸 안담도록 만들기 위해 사용한 변수 함수 search : 궁수의 위치를 받아서 제거할 수 있는 적의 위치를 반환하는 함수 kill : 궁수가 적을 제거하는 함수 move..

2020.02.17 TRIANGLEPATH 풀이 행을 한칸씩 이동할 때, 아래와 오른쪽 대각선 아래 두가지 경우의 수가 있다. 재귀함수를 이용해서 마지막 행에 도착하는 순간 그때의 최대 거리를 리턴하는 getResult 함수를 만들었다. 처음에 메모이제이션을 마지막에 도달했을 때 최댓 거리를 DP 행렬에 기록하려고 시도했었다. 우연히 정답이 나왔으나 이는 같은 결과가 나올 수 없었다. 경로가 달라질 때마다 마지막에 도달하는 거리는 달라진다. 같은 지점에 대해 같은 결과가 나오는 것에 대해 메모이제이션을 활용해야 하는데 잘못된 알고리즘을 구상한 것이다. 잘못된 메모이제이션 활용 //! 2020.02.17 // TODO AS_TRIANGLEPATH.cpp // Dynamic Programming #inclu..

2020.02.17 WILDCARD 풀이 기본적으로 input1, input2를 입력받으면서 바로 비교하도록 함수를 구현하였고 비교해서 조건을 만족하면 결과 벡터에 푸시하였다. 마지막으로 compare와 함께 결과를 sort 해서 출력하였다. *, ?, 문자 경우를 나누어 재귀함수를 이용해 idx1,idx2를 증가, 그대로 두며 완전탐색하도록 만들었다. 동적계획법 문제인데 먼저 완전탐색으로 확인하여 시간초과가 나면 DP를 어떻게 적용할지 고려해보려 했는데 시간초과없이 통과해버렸다.. 코드 //! 2020.02.17 // TODO AS_WILDCARD // Brute Force (Dynamic Programming) #include #include #include #include using namespac..

2020.02.17 백준1918 / 후위 표기식 풀이 order : 계산에 필요한 연산기호, 문자의 우선순위를 저장하는 딕셔너리 calculator : ( 가 나오면 push, 문자가 나오면 push, 연산기호들이 나오면 연산기호의 우선순위가 낮은 녀석들(문자포함)을 스택에서 pop해서 결과에 저장하고 현재 연산기호 push(단, ) 는제외) 코드 (python) inputData = input() myStack = [] top = -1 order = {'(' : 4, ')' : 4,'+': 3, '-': 3, '*': 2, '/': 2} for i in range(26): order[chr(i + ord('A&..

2020.02.17 백준17070 / 파이프 옮기기 1 풀이 알고리즘 : 완전탐색 전역변수 inMap : 주어진 input map checkMap : 파이프를 밀면서 파이프가 갈 수 있는 곳인지 없는지 표시해둠 함수 checkNext : dir과 y,x를 이용해서 다음 칸이 맵의 범위 내에 있는지 & 파이프가 갈 수 있는 곳인지 확인하는 함수 getResult : 이전 dir과 y,x를 이용해 갈 수 있는 모든 다음 y,x로 이동하고 도착점에 도착하는 경우의 수를 세어 리턴하는 함수 파이프의 머리를 이용해 다음 갈 수 있는 칸을 탐색하고 이동하는 완전탐색을 통해 모든 경우의 수 중 가능한 경우의 수를 세도록 구현하였다. 코드 //! 2020.02.17 // TODO BJ17070_파이프옮기기1 #incl..

2020.02.16 백준17406 / 배열돌리기4 풀이 알고리즘 : 완전탐색 + Simulation 전역변수 inMap : 초기 배열 A 상태 nextMap : 경우의 수에 따라 회전을 진행한 배열 A rotateOrder : K번의 회전을 수행할 때 0 ~ K-1 번째 회전 index를 저장하는 변수 checkRotate : 순열을 재귀함수로 구현할 때 이미 사용한 index인지 체크하는 변수 rotateInfo, rotateSize : r,c,s로 주어지는 회전정보들을 0 ~ K-1 번에 저장하는 변수 함수 getMin : 배열A의 최소 크기를 계산하면서 nextMap을 처음 inMap으로 초기화하는 함수 getResult : n번~K-1번의 회전정보를 결정하고 simulate 함수를 이용해 배열 A..

2020.02.15 백준17471 / 게리맨더링 Solution 알고리즘 : 완전탐색 + BFS 전역변수 inMap : input으로 주어지는 각 지역의 인구수를 저장하는 배열 numMap : 완전탐색으로 할당할 각 지역의 선거구 정보(1 혹은 2로 구분) myMap : input으로 주어지는 각 지역의 연결상태 checkMap : BFS에서 방문 상태를 저장하는 배열 myQ : BFS에서 탐색 순서를 담을 큐 함수 resetCheck : BFS 함수를 마치고 나서 다음 BFS를 위해 check배열을 초기화 BFS : start(탐색 시작 구역)와 sizeMap(선거구 1 혹은 2의 총 갯수) 을 받아서 연결 지역들을 탐색하고 만약 sizeMap과 동일하게 연결되어있다면 해당 선거구의 총 인구수를 반환,..