본문 바로가기

problem solving

 (93)
[프로그래머스]불량 사용자 1. 2중 반복문을 돌려 banned_id에 매핑되는 user를 store 배열에 저장한다. 2. 저장한 배열을 이용해 가능한 모든 경우의 수를 구하기 위해 user_count 함수를 이용해 깊이 우선 탐색을 이용한다. 3. 모든 경우의 수를 저장한 total 배열을 정렬한 후 비교해 중복되는 값을 제외한 개수를 구한다. #include #include #include #include using namespace std; int MAX = 0; map M; vector total; vector store[8]; vector temp; vector temp_copy; void user_count(int cur) { if (cur >= MAX) { temp_copy = temp; sort(temp_copy...
[프로그래머스]외벽 점검 DFS(or permutation)와 백트래킹을 이용해 모든 경우의 수를 탐색했다. weak의 처음부터 끝까지 반복문을 순회하는데, 각 반복마다 해당 weak의 위치부터 dist 거리만큼 검사한다. 검사하면서 weak의 위치면서, 아직 방문하지 않았다면 방문 표시를 하고 백트래킹 기법으로 방문 표시를 다시 제거하기위해 store 배열에 저장한다. 다음 dist를 검사하기 위해 search_result 함수를 호출한다. 마지막으로 현재 반복문에서 store에 visited 위치를 알려주는 변수를 추출해 방문표시를 제거한다. 위의 순서를 반복하면 답을 찾을 수 있다. #include #include #include #include using namespace std; bool visited[250]; boo..
[프로그래머스]블록 이동하기 구현이 어려운 문제다. 어떻게 풀지 생각하는데 오래 걸리지 않았는데, 신경써야 할 부분이 많아 풀이하는데 오래걸렸다. 풀이 방법은 다음과 같다. 로봇이 이동할 수 있는 경우는 회전하거나 전체가 움직이는 경우다. 1. 회전의 경우 로봇의 각 좌표를 기준으로 회전했을 때 가능한 경우가 있으면 이동한다. 2. 전체가 움직이는 경우는 2개 좌표에 같은 값을 + 또는 - 연산을 진행해 가능한 위치가 있으면 이동한다. 3. 1,2 번을 통해 이동한 좌표는 다시 방문하지 않도록 visited 배열을 이용해 표시한다. 4, 1,2,3 번을 반복하다 목표 좌표에 도착하면 값을 반환한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ..
[프로그래머스]기둥과 보 설치 시뮬레이션 문제는 있는 그대로 구조를 구현하는게 중요하다는 것을 명심하자 기둥과 보 문제는 다음과 같이 풀이하는데 핵심은 다음과 같다. 1. 주어진 build_frame 배열을 순회하면서 기둥과 보를 설치하는데 check_gidung, check_bo 이 때 함수를 이용해 설치가 가능한지 검사한다. 2. 삭제하지 못하는 경우가 있을 수 있는데 remove_gidung, remove_bo 사용해서 주변의 보와 기둥이 있다면 현재 삭제하려고 하는 것을 제거한 후에도 구조가 유지되는지 확인한다. 최대한 있는 그대로 구현하는 것이 중요하다는 점을 꼭 명심하자 #include #include #include using namespace std; const int MAX = 150; bool gidung[MAX][..
[프로그래머스]자물쇠와 열쇠 이 문제는 모든 경우의 수를 찾아서 문제를 해결했다. 문제를 해결한 순서는 다음과 같다. 1. 우선 키를 90'회전하면 4개의 키를 얻을 수 있다. 2. 구해진 4개의 키를 1차원으로 펼쳐주는데 이때 자물쇠의 크기보다 키의 크기가 작으면 자물쇠의 크기에 맞도록 여백(0값)을 추가한다. 3. 키를 1차원으로 펼친것과 같이 자물쇠도 펼쳐준다((키 == 자물쇠) 여부를 비교하기 편하게 하기 위함) 4. 자물쇠를 위아래로 이동시하면서 자물쇠와 키가 맞는지 검사하고(동일하다면 return true) 가능한 모든 형태를 저장한다. 5. 4번 과정에서 저장한 값을 이용해 좌우를 이동하면서 자물쇠와 키가 맞는지 검사하며, 동일하다면 true 값을 return 한다. 6. 4,5번 과정에서 자물쇠와 키가 맞지 않았다면 ..
[프로그래머스]수식 최대화 주어진 문자열에서 각각의 숫자와 연산자를 토큰화해 벡터에 저장한다. 만들어진 벡터를 이용해 3!의 경우의 수만큼 반복문을 순회하는데, 현재 반복에서 operation에 정의된 문자가 {"*", "-", "+"}라면 벡터에서 * 연산자만 찾아서 전후의 값을 연산한다. 만약 전과 후의 값이 300과 500이라면 15000이라는 값이 결과로 나온다. 그리고나서 연산에 사용된 3개의 값("*", 300, 500)을 erase하고, 결과 값을 해당 위치에 insert한다. 마지막으로 새로나론 결과부터 연산을 진행할 수 있도록 반복문의 값을 1만큼 줄여준다. 현재 반복문에서 operation 순서가 {"*", "-", "+"}라면 벡터에서 *연산을 전부 진행한 후 -연산을 전부 진행하고 +연산을 진행하면 마지막에 ..
[프로그래머스]후보키 #include #include #include #include using namespace std; vector sub_key;vector store; vector str_tokenization(string str) { vector store; string temp = ""; int index = 0; while(index
[BOJ]13460번: 구슬 탈출2 생각보다 어려웠던 문제 #include #include #include const int dx[4] = { 0, 0, 1, -1 }; const int dy[4] = { 1, -1, 0, 0 }; const int MAX = 20; int N, M; std::string str[MAX]; std::pair pos_B, pos_R; int min = INT_MAX; int temp_Ry, temp_Rx, temp_By, temp_Bx; void swap(int y, int x, char color) { char temp; if (str[y][x] == 'O') { if (color == 'R') { str[temp_Ry][temp_Rx] = '.'; } else if (color == 'B') { str[..

티스토리툴바