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과 동일하게 연결되어있다면 해당 선거구의 총 인구수를 반환,..

2020.02.14 큐빙 풀이 알고리즘 : Simulation box[6] 에 큐브의 6개 면에 대해 char 를 인덱싱 할 수 있도록 써두었다. color[6]에 큐브 6개의 면을 초기화 할 색깔들을 써두었다. myCube에 6개의 면(각 면마다 3x3) 의 색들을 담았다. turnIdx 배열을 통해 6개의 면 중 바라보고 돌릴 면과 이때 바라보는 면을 둘러싸는 4개의 면을 아래,오른쪽,위,왼쪽 순으로 찾을 수 있도록 써두었다. turnInfo : 6개의 면 중 바라보고 돌릴 면을 정했을 때 turnIdx에서 나온 결과에 따라 해당 index들 중 기준점이 되는 점이 각 경우마다 달라지므로 경우에 맞게 써두었다. blockIdx : turnInfo에서 받아온 기준점에 따라 다음 두개의 숫자를 가져오는 ..

2020.02.12 나무재테크 Solution InMap : 매 턴 마다 양분의 값을 저장하는 변수 (초기값은 모두 5) deadMap : 봄에 죽은 나무들이 여름에 더해질 양분을 저장하는 변수 plusMap : 처음에 input으로 주어지는 로봇이 겨울에 더하는 양분 treeInfo : 칸에 있는 나무들이 저장되는 vector 변수 알고리즘 : Simulation 주어지는 정보에 맞게 spring, summer, fall, winter 함수를 만들어 K번 만큼 수행하고 살아있는 나무의 개수를 세어 출력. //! 2020.02.12 // TODO BJ16235_나무재테크 #include #include #include using namespace std; const int MAX = 15; const i..

2020.02.12 백준 12100 / 2048(Easy) Solution inMap : input map nextMap : 2048 게임이 진행됨에 따라 변경되는 map dirInfo : 완전탐색으로 1번째~5번째에 블락을 이동시키는 방향을 결정해둔 배열 myQ : 코드 1의 방식에서 사용될 Q check : 코드 2의 방식에서 사용될 bool 배열 알고리즘 기본적으로 5번의 턴에 사용될 방향을 완전탐색을 이용해 경우의 수를 구한다. O(4^5) 각 경우의 수 마다 5번의 턴을 수행시키고 최댓값을 갖는 블락의 수를 출력한다. 턴을 수행하는 방식은 기본적으로 방향에 따라 행/열 마다 블락들을 이동시키도록 구상하였다. 각 행/열 에서 블락들을 이동시키는 방식을 두 가지로 구현해보았다. Solution1 옮..