본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

Algorithm/기타 알고리즘21

[시뮬레이션] 압축 - 2018 KAKAO BLIND RECRUITMENT 해결방법 i) map을 이용하여 길이가 1인 모든 단어를 포함하는 사전을 초기화한다. map은 쌍으로 만들면 된다. ii) map에서 현재 입력과 일치하는 가장 긴 문자열을 찾는다. iii) 가장 긴 문자열에 해당하는 사전의 색인 번호를 출력한다. iv) 가장 긴 문자열의 뒤에 문자가 남아있을 경우, 가장 긴 문자열에서 그 문자를 덧붙이고 map에 넣는다. v) 현재 위치를 그 문자의 위치로 이동한다. 소스코드 #include #include #include using namespace std; map dic; vector solution(string msg) { vector answer; for(int i=0;i 2022. 6. 28.
[시뮬레이션] 프렌즈4블록 - 2018 KAKAO BLIND RECRUITMENT 해결 방법 필자는 아래 이미지처럼 2차원 벡터를 이용하여 아래 블록부터 각 열 벡터에 저장했다. 아래 블록부터 저장하면 블록을 삭제하는 과정이 편리하기 때문이다. 또, 블록의 삭제는 화살표의 역방향으로 진행하는게 편리하다. 보드를 탐색해나가며 같은 종류의 2x2 블록들을 찾아서 boolean 2차원 배열에 삭제할 블록들을 표시해두고, 나중에 일괄적으로 삭제하는 방법을 이용하면 삭제할 수 있는 블록이 겹치더라도 연산이 간단해진다. 삭제할 수 있는 블록이 겹칠 수 있으므로 같은 종류의 2x2를 발견하자마자 지우는 것은 절대 안된다. 주기마다 삭제한 블록의 개수를 누적시켜주면 문제는 해결된다. 소스코드 #include #include #include using namespace std; vector vboar.. 2022. 6. 5.
[n진수] n진수 게임 - 2018 KAKAO BLIND RECRUITMENT 해결 방법 10진수 i를 n진수로 변환한 값을 문자열 형태로 반환하는 converter함수를 만들어 두었다. 16진수 이하의 변환은 16진수 기준으로 변환해도 모두 적용되므로, 2진수든 8진수든 모두 16진수 변환 방법을 써도 된다. 0부터 n진수로 변환한 값들을 임의의 문자열에 계속 추가해두면 되는데, 최종 문자열의 길이는 t*m이면 충분하다. 이제 이 문자열을 참고하여 튜브 차례에 해당하는 문자들을 추출하면 문제가 해결된다. 소스코드 #include #include using namespace std; char hexa[17] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; string converter(int n, int i.. 2022. 5. 31.
[집합] 뉴스 클러스터링 - 2018 KAKAO BLIND RECRUITMENT 해결 방법 i) str1, str2에 있는 대문자를 모두 소문자로 전환한다. ii) str1, str2에 대하여 각각 연속된 두 영문자씩 쪼개어 벡터에 넣어준다. iii) 두 벡터의 크기가 모두 0인 경우와 두 벡터 중 하나의 크기가 0인 경우를 반영한다. iv) 두 벡터의 교집합 요소를 찾는다. 값이 같은 요소가 있기 때문에 방문 배열을 활용한다. v) 합집합 요소의 개수를 찾는다. 합집합 요소는 두 벡터의 크기의 합에서 교집합 요소의 개수를 뺀 값이다. -> n(A∪B)=n(A)+n(B)-n(A∩B) 소스 코드 #include #include using namespace std; vector s1; vector s2; int inter; // 교집합 요소의 개수 bool check[1001]; //s.. 2022. 5. 24.
[Linked List] 표 편집 - 2021 카카오 채용연계형 인턴십 해결 방법 이 문제는 연결리스트를 이용하여 풀 수 있다. 굳이 포인터를 사용하지 않고도 배열을 이용하여 연결리스트를 구현할 수도 있다. 또, 'Z' 명령은 최근에 삭제했던 행을 복구하는 명령이므로 Stack이 필요하다. 주의할 점이 있다면, 맨 앞에 있는 요소는 앞 노드로 연결하는 링크가 없고, 맨 뒤에 있는 요소는 뒷 노드로 연결하는 링크가 없음을 고려해야 한다. 그리고 'U', 'D' 명령의 경우에는 이동할 칸 수를 나타내는 정수가 나오는데, 이 정수는 한 자리 숫자가 아닐 수도 있기 때문에 모든 자리 수를 추출해야 한다. 노드를 삭제하는 경우에는 기존 노드의 앞, 뒤 노드를 서로 이어주면 되고, 노드를 복구하는 경우에는 제거되었던 노드의 앞, 뒤 노드를 해당 노드로 이어주면 된다. 소스 코드 아래 .. 2022. 5. 22.
[시뮬레이션] 수식 최대화 - 2020 카카오 인턴십 해결 방법 (i) 문자열을 파싱하여 정수 부분과 연산자 부분을 따로 추출하여 벡터에 저장한다. (ii) 우선 순위를 배정한다. 우선순위에 대한 경우의 수는 6이기 때문에 6가지 경우만 시뮬레이션 하면 된다. (iii) 남아 있는 연산자들 중 가장 우선 순위가 높은 연산자를 찾아서, 해당 연산자에 대한 연산을 수행한다. (iv) 연산 결과는 합쳐서 정수 벡터에 반영하고, 사용한 연산자는 연산자 벡터에서 제거하고, 남은 해당 연산자 카운트를 1 감소시킨다. 이렇게 하면 연산마다 정수 벡터와 연산자 벡터의 크기는 각각 1씩 줄어들 것이고, 모든 연산을 수행했을 때는 정수 결과값 하나만 남게 된다. (v) 모든 경우에 대한 정수 결과값들의 최댓값을 구한다. 소스 코드 #include #include #inclu.. 2022. 5. 14.
[구간합] 쿠키 구입 - Summer/Winter Coding(~2018) 문제를 해결한 후에도 다른 풀이법에 대한 호기심이 생겨서 찾아보았다. 내 풀이법도 간단하다고 생각하지만 이 블로그에 설명된 풀이법이 더 간단해보이니 궁금한 분들은 참고하길 바란다. https://hwan-shell.tistory.com/308 이제 내 풀이법을 소개한다. 해결 방법 cookie 벡터에 대한 누적합 배열 cookie_acc을 만들어 놓았기 때문에 구간합 공식을 쉽게 구할 수 있었다. 예를 들어, 구간 [a, b]에 대한 구간합은 cookie_acc[b]-cookie_acc[a-1]이다. 이 문제에서는 a 2022. 5. 1.
[시뮬레이션] 스킬트리 - Summer/Winter Coding(~2018) 해결 방법 먼저 스킬트리의 순서를 map에 저장해두고, 뒤에 나와야 할 스킬이 앞에 나왔다면 그 스킬트리는 잘못 됐다고 판단하면 된다. 소스 코드 #include #include using namespace std; map m; int solution(string skill, vector skill_trees) { int answer = 0; for(int i=0;i 2022. 4. 29.
[수학] 멀쩡한 사각형 - Summer/Winter Coding(2019) 해결 방법 일차 함수의 특성을 이용하여 문제를 해결했다. 입출력 예 #1에서 좌측 하단 꼭짓점을 원점이라고 했을 때, 일차 함수식은 다음과 같다. y=-(h/w)x+h x축으로 좌표를 1씩 옮겨가며 선에 걸치는 사각형들을 제거해주는 방법을 사용하면 문제를 해결할 수 있다. 이제, 좌측에 있는 사각형부터 제거해보자. 먼저 x=0일 때 y=12이고, x=1일 때 y=10.5다. 이 경우에는 y의 좌표가 10~12 사이에 있는 사각형 2개가 제거된다. 그 다음에 x=1일 때 y=10.5이고, x=2일 때 y=9다. 이 경우에는 y의 좌표가 9~11 사이에 있는 사각형 2개가 제거된다. 이런식으로 계속 두 좌표를 비교하여 사각형을 제거해나가면 되는데, 이 때 왼쪽 좌표의 y값은 올림을 하고 오른쪽 좌표의 y값은.. 2022. 4. 22.

티스토리툴바