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

Algorithm143

[시뮬레이션] 주차 요금 계산 - 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.
[완전탐색] 외벽 점검 - 2020 KAKAO BLIND RECRUITMENT 기존에 필자가 풀이한 방법은 통과는 했지만 실행 시간이 꽤 길어서 다른 좋은 풀이 방법을 찾아보았다. 참고한 풀이 방법의 출처는 맨 아래에 표시하겠다. 해결 방법 필자가 설명할 풀이 방법은 완전 탐색을 사용한 방법이다. 이런 식으로 원을 탐색하는 문제는 2n 크기의 1차원 배열로 풀어서 생각하면 쉽다. 늘어난 부분은 원의 위치 0을 기준으로 2바퀴 째 도는 부분인 것이다. 즉, weak 배열의 크기를 2배로 늘리고 늘어난 부분은 기존의 원소에 n을 더해서 추가하면 된다. ※ 예) n=12이고 weak=[1, 5, 6, 10]인 경우에는 weak=[1, 5, 6, 10, 13, 17, 18, 22]로 만든다. 이렇게 되면 기존의 weak의 크기를 w라고 했을 때, [0, w) 범위의 정수인 임의의 i에 대.. 2022. 9. 8.
[스택/큐] 캐시 - 2018 KAKAO BLIND RECRUITMENT 이 문제는 LRU(Least Recently Used) 알고리즘을 구현하는 문제다. 해결 방법 LRU 알고리즘은 가장 오랫동안 사용되지 않은 요소를 제거하는 교체 알고리즘이며, 필자가 구현한 방법은 다음과 같다. 먼저, 큐에 있는 요소들을 pop해가며, cache hit이 발생한 요소를 제외하고 모두 임시 큐로 옮겨놨다가 다시 기존 큐로 옮긴다. cache hit이 발생했다면 cache hit이 발생한 요소는 큐의 맨 뒤에 push한다. 만약 cache hit이 발생하지 않았다면 새로운 요소를 큐에 넣어야 하는데, 그 전에 cacheSize를 따져서 큐가 모두 찼다면 가장 오래된 요소를 제거해두면 된다. 마지막으로 cache hit의 여부에 따라 cache hit이 발생했다면 answer에 1을 더하고,.. 2022. 7. 5.
[시뮬레이션] 파일명 정렬 - 2018 KAKAO BLIND RECRUITMENT 해결 방법 문자열 파싱 부분은 NUMBER은 첫 연속 숫자열만 반영해야 한다는 사실만 잘 고려하면 어렵지 않을 것이다. 파일의 TAIL 부분은 파일 정렬에 고려하지 않기 때문에 TAIL 부분은 신경쓰지 않아도 되지만, 두 파일의 HEAD 부분과 NUMBER 부분이 모두 같을 때는 입력 벡터의 인덱스 순으로 정렬해야 하기 때문에 입력 인덱스까지는 고려해줘야 한다. 그래서 파일의 인덱스, HEAD 부분, NUMBER 부분에 해당하는 파일 구조체를 만들어두면 문제를 쉽게 해결할 수 있다. 또, 문자의 대소문자를 판별할 때나, 정수 여부를 판별하는 경우에는 아스키 코드를 이용하면 편리하고, 정수 문자열을 정수로 바꿀 때는 stoi 함수를 이용하면 편리하다. stoi 함수는 앞 부분에 0이 여러 개 붙더라도 이를.. 2022. 7. 5.
[시뮬레이션] 압축 - 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.
[완전탐색] 후보키 - 2019 KAKAO BLIND RECRUITMENT 해결 방법 i) 테이블의 모든 속성에 대한 조합(Combination)을 구한다. - 예를 들어, 테이블의 속성 번호를 0, 1, 2, 3으로 매겼을 때, 모든 속성에 대한 조합은 {0, 1, 2, 3, {0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}, {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}, {1, 2, 3, 4}}가 된다. - 조합을 C++ 코드로 구현하는 방법은 https://kimcoder.tistory.com/118?category=888042 에 설명했으니 이를 참고하면 된다. ii) 모든 속성 조합에 대하여 유일성을 검증한다. - 각각의 속성 조합들에 대한 중복 여부를 검증한다. - 예를 들어, 필자는 ["이름", "전.. 2022. 6. 24.

티스토리툴바