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

Algorithm/기타 알고리즘21

[구간합] 광고 삽입 - 2021 KAKAO BLIND RECRUITMENT 해결 방법 필자는 초 단위로 누적 재생시간에 대한 구간합을 구해서 해결했다. 최대 재생 시간은 359999초이기 때문에 O(N)의 시간복잡도 정도는 부담스럽지 않다. 이렇게 구간합을 구해두면 [0, adv_time) 구간부터 [play_time - adv_time, play_time)에 대한 모든 구간합을 구하는데 O(N)의 시간복잡도로 해결할 수 있다. 그리고 "hh:mm:ss" 문자열 형식으로 표현된 시간을 초 단위의 정수로 변환하는 함수와 초 단위의 정수를 "hh:mm:ss" 문자열 형식으로 변환하는 함수를 추가해서 손 쉽게 시간을 계산할 수 있도록 했다. 소스 코드 #include #include using namespace std; #define MAX 360000 int dup[MAX]; //.. 2022. 10. 11.
[구현] 순위 검색 - 2021 KAKAO BLIND RECRUITMENT 해결 방법 정확성 테스트라면 어렵지 않게 통과할 수 있을 것이지만, info, query 벡터에 대해 그대로 2중 for문을 쓴다면 효율성에서 좋은 점수를 받지 못할 것이다. 필자는 다음과 같이 4차원 벡터를 선언했다. vector iv[4][3][3][3]; 개발언어 항목, 지원 직군 항목, 경력구분 항목, 소울 푸드에 있는 각 정보를 차례대로 정수로 나타내어서 저장하기 위해 4차원 형태로 만들었다. cpp/java/python/- backend/frontend/- junior/senior/- chicken/pizza/- '-' 부분에는 나머지 조건에 해당 하는 모든 경우를 넣어주면 된다. 조건이 4개이기 때문에 하나의 조건이라도 반영하지 않는 경우의 수는 15(4C1+4C2+4C3+4C4=15)가 될.. 2022. 10. 7.
[구간합] 파괴되지 않은 건물 - 2022 KAKAO BLIND RECRUITMENT 해결 방법 정확성 테스트라면 어렵지 않게 통과할 수 있을 것이지만, 2차원 누적합 알고리즘을 사용하지 않는다면 효율성 테스트에서 통과하기 힘들 것이다. 필자는 데미지 범위를 나타내는 벡터와 데미지를 나타내는 벡터 총 2개의 벡터를 만들어서 해결했다. 입출력 예 #1를 기반으로 해결 방법을 설명해보겠다. 데미지 범위 벡터(damage_pos) 먼저, 데미지 범위 벡터의 모든 요소는 0으로 초기화해둔다. (r1, c1)부터 (r2, c2)까지 degree 만큼의 공격을 받았다고 해보자. 이 때는 damage_pos의 (r1, c1), (r2+1, c2+1)에는 degree만큼 빼주고, (r1, c2+1), (r2+1, c1)에는 degree만큼 더해준다. 이를 그림으로 나타내면 다음과 같다. 회색 부분은 (.. 2022. 10. 4.
[구간합] 두 큐 합 같게 만들기 - 2022 KAKAO TECH INTERNSHIP 해결 방법 입출력 예 #1를 이용하여 해결 방법을 설명해보겠다. 필자는 2개의 큐를 각각 다른 순서로 결합한 2개의 벡터를 만들어놓고 구간합을 이용해서 해결했다. 2개의 결합 벡터를 만든 이유는 모든 구간합을 편하게 계산하기 위함이다. 2개의 결합 벡터는 다음과 같다. 그리고 각 큐의 합은 두 큐의 합의 1/2이어야 하기 때문에 구간합이 15인 구간을 따로 선정했다. 각 결합 벡터에 대한 누적합 벡터를 따로 만들어서 이 누적합 벡터에 투포인트 알고리즘을 적용해서 구간합을 구하는 것이 효율적이다. 이제 특정 구간합만 왼쪽 큐에 모을 수 있게 해보자. 큐의 원소는 한쪽으로만 들어오고 다른 한쪽으로만 나간다는 특성을 이용해서 들어오는 원소의 개수와 나가는 원소의 개수를 합하기만 하면 작업 횟수를 구할 수 있다.. 2022. 9. 30.
[시뮬레이션] 주차 요금 계산 - 2022 KAKAO BLIND RECRUITMENT 해결 방법 맵을 이용하여 을 map으로 표현했다. bill 구조체 주차중인지의 여부 : 출차 기록이 나와있지 않은 경우에는 23:59에 출차되었다고 간주해야 되기 때문에 현재 주차중인지도 표시해야 한다. 입장 시간 : 차가 하루에 2번 이상 들어오는 경우도 있기 때문에 입장 시간을 계속 갱신해줘야 한다. 누적 시간 : 최종 주차 요금은 나중에 일괄적으로 계산하기 때문에 누적 시간을 반영했다. 실수할 만한 부분 초과 요금 계산 : 기본 시간 밑으로 주차한 경우에는 초과 요금이 0이 되어야 한다. 올림 연산 : 실수형 타입(float, double 등)에 대해 올림을 수행해야 한다. ceil(excess_time/fees[2]) // X ceil((double)excess_time/fees[2]) // O .. 2022. 9. 20.
[n진수] k진수에서 소수 개수 구하기 - 2022 KAKAO BLIND RECRUITMENT 해결 방법 문제에서 원하는 소수에 대한 조건은 다음과 같다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우 P처럼 소수 양쪽에 아무것도 없는 경우 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다. 겉보기에는 복잡한 조건을 가지고 있는 것처럼 보이지만, 0을 기준으로 split해서 나온 숫자들 중에서 소수는 몇 개인지만 계산하면 된다. 테스트케이스 1, 11번에서 틀리는 경우에는 소수를 추출해서 판별할 때 long 자료형을 사용해보자. 진수 변환을 하면 숫자가 매우 길어지기 때문에 int보다는 long을 선택하는 것이 좋다. 그리고 테스트케이스 12번에서 틀리는 경우에는 소수 판별.. 2022. 9. 16.
[시뮬레이션] 자물쇠와 열쇠 - 2020 KAKAO BLIND RECRUITMENT 해결 방법 아래 이미지와 같이 x, y 좌표의 범위가 모두 [m-1, m+n-1)인 Lock 구간을 정하고, 모든 경우에 대하여 Key를 맞춰보면 된다. key를 회전하는 경우도 반드시 반영하도록 하자. 먼저, board에 lock 구간을 미리 반영해둔다. 입출력 예의 경우에는 다음과 같은 결과가 나올 것이다. 0000000 0000000 0011100 0011000 0010100 0000000 0000000 그리고 key를 board에 배치할 수 있는 모든 경우를 따져보면 된다. 각 경우마다 board에 key를 더하고, board의 lock 구간만 탐색해서 1이 아닌 칸이 존재하면 자물쇠를 풀 수 없다고 판단하면 된다. lock + key = 0인 경우 : 자물쇠의 홈을 채울 수 없다. lock + .. 2022. 9. 13.
[시뮬레이션] 기둥과 보 해결 방법 먼저, 각 좌표마다 상하로 기둥이 있는지, 좌우로 보가 있는지를 판별할 수 있게 했다. 따라서, 아래와 같은 구조체를 생성해서 좌표마다 배치해줬다. struct State{ bool up_column; // 기둥이 존재하는가? bool down_column; // 기둥이 받치고 있는가? bool left_beam; // 왼쪽으로 보가 연결되어 있는가? bool right_beam; // 오른쪽으로 보가 연결되어 있는가? }; State state[101][101]; ▣ 기둥을 설치할 수 있는 경우 기둥 또는 보가 받치고 있다. 바닥이다. ▣ 보를 설치할 수 있는 경우 왼쪽 또는 오른쪽 기둥이 받치고 있다. 양쪽 보를 연결할 수 있다. ▣ 기둥을 삭제할 수 없는 경우 위 좌표에 기둥이 있을 때,.. 2022. 9. 9.
[시뮬레이션] 파일명 정렬 - 2018 KAKAO BLIND RECRUITMENT 해결 방법 문자열 파싱 부분은 NUMBER은 첫 연속 숫자열만 반영해야 한다는 사실만 잘 고려하면 어렵지 않을 것이다. 파일의 TAIL 부분은 파일 정렬에 고려하지 않기 때문에 TAIL 부분은 신경쓰지 않아도 되지만, 두 파일의 HEAD 부분과 NUMBER 부분이 모두 같을 때는 입력 벡터의 인덱스 순으로 정렬해야 하기 때문에 입력 인덱스까지는 고려해줘야 한다. 그래서 파일의 인덱스, HEAD 부분, NUMBER 부분에 해당하는 파일 구조체를 만들어두면 문제를 쉽게 해결할 수 있다. 또, 문자의 대소문자를 판별할 때나, 정수 여부를 판별하는 경우에는 아스키 코드를 이용하면 편리하고, 정수 문자열을 정수로 바꿀 때는 stoi 함수를 이용하면 편리하다. stoi 함수는 앞 부분에 0이 여러 개 붙더라도 이를.. 2022. 7. 5.

티스토리툴바