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

Algorithm143

[DFS] 불량 사용자 - 2019 카카오 개발자 겨울 인턴십 경우의 수를 구하는 유형의 문제는 DFS 또는 DP 문제일 확률이 높다. 경우의 수를 조합이나 순열같은 수식으로 해결해보려고 시도해보았지만 꽤 복잡해서 DFS로 풀기로 결정했다. 해결 방법 먼저, banned_id의 1번째 id와 매칭 가능한 user_id가 있는지 확인해서 매칭 가능한 user_id를 발견했다면 save 벡터에 해당 user_id를 저장해둔다. 그리고 이후의 banned_id들에 대해서도 동일한 과정을 반복하여 모든 banned_id가 매칭되었다면 하나의 경우가 완성된 것이다. 이 때의 save 정보를 다른 벡터에 저장해놓고 DFS를 이어서 수행해주면 된다. 조건에 맞는 모든 경우들을 모두 저장했다면 중복되는 아이디 목록을 최종적으로 제거해주고 남은 경우의 수를 구하면 문제가 해결된다... 2022. 4. 5.
[DFS] 다단계 칫솔 판매 - 2021 Dev-Matching 난이도가 Level3인 것 치고는 쉽게 해결한 것 같다. 이 문제는 DFS로 해결할 수 있으며, 분배금을 10% 떼어내고 남은 몫은 자신이 가지고 다음 노드(인원)에게 10%의 분배금을 전달하는 과정을 반복하면 된다. 그리고 일일이 간선을 연결하는 과정 없이 map을 활용하여 간단히 DFS를 수행할 수 있다. 주의할 점이 있다면, 분배금이 1원 미만일 때에도 DFS를 진행하면 시간초과가 난다. 그래서 반드시 분배금이 있을 때만 DFS 함수를 호출해야 한다. 소스 코드 #include #include using namespace std; map mres; map mref; vector answer; void distribute(string seller, int money) { if(seller=="-") .. 2022. 4. 3.
[이분 탐색] 징검다리 건너기 - 2019 카카오 개발자 겨울 인턴십 코딩테스트 문제가 이분 탐색 문제인지를 확인할 수 있는 꼼수가 있다. 그것은 주어진 값의 범위를 확인하는 것이다. 이 문제는 주어진 범위를 아무리 잘 조합해봐도 복잡도가 터무니없는 수(억 단위)가 나온다. 보통 코딩테스트에서 효율성을 따질 때 최대 복잡도가 억 단위 이상이 나오면 거의 실패한다. 이분 탐색은 값을 미리 가정하고 푸는 알고리즘이다. 처음으로 가정하고 싶은 값은 어떠한 값을 골라도 상관이 없지만 보통 중간값을 선택한다. 해결 방법 중간값을 m으로 지정했다면 m명이 모두 징검다리를 건널 수 있는지를 체크해야 한다. m명이 모두 건널 수 없다면 m명 이상인 경우는 전부 건널 수 없다는 뜻이므로 범위의 최댓값을 m-1명으로 지정하고, m명이 모두 건널 수 있다면 범위는 m명~2억명 사이에 있다는 .. 2022. 3. 29.
[시뮬레이션] 행렬 테두리 회전하기 - 2021 Dev-Matching 해결 방법 단순한 시뮬레이션 문제지만 한 가지 주의할 점이 있다. 그것은 칸에 있는 숫자를 저장하는 변수가 하나 필요하다는 것인데, 칸에 있는 숫자를 기억하지 않고 이동해버리면 값이 덮어 씌워져서 데이터가 날아가버릴 수 있기 때문이다. 그래서 현재의 좌표에 있는 숫자를 저장해뒀다가 다음 칸에 넣을 수 있는 save라는 변수를 하나 추가했다. 그리고 회전의 경우에는 상하좌우 4개의 테두리를 지나는 상황으로 나눠서 반복문을 수행했다. 각 반복문은 각 꼭짓점 사이에서 수행되는 것이다. 소스 코드 #include using namespace std; vector v; int rotate(vector query) { int mini=10001; int x, y; // 현재 좌표 저장 int save; // 현재 .. 2022. 3. 27.
[투 포인터] 보석 쇼핑 - 2020 카카오 인턴십 gems 배열의 크기는 최대 100000이기 때문에 O(n^2) 이상의 알고리즘으로는 효율성에서 통과하지 못할 것이다. 즉, 구간의 왼쪽과 오른쪽 끝점을 조절해가며 해답을 찾는 투 포인터 알고리즘이 필요하다. 해결 방식을 그림으로 표현하면 이렇다. 모든 보석의 종류를 포함하는 첫 구간(0부터 시작)을 기준으로 투 포인트 알고리즘을 수행하면 되는 방식이다. 왼쪽 끝점은 이동할 수 있는 만큼 이동하고 오른쪽 끝점은 1만큼 이동하는 과정을 반복했고, 각 과정이 끝날 때마다 구간의 길이가 최솟값이면 벡터에 저장했다. 왼쪽 끝점에 있는 보석이 구간에 단 1개만 있는 상태에서 왼쪽 끝점을 이동해버리면 그 구간은 모든 보석의 종류를 포함할 수 없게 된다. 반대로, 왼쪽 끝점에 있는 보석이 구간에 여러개가 있다면 왼쪽.. 2022. 3. 20.
[BFS] 블록 이동하기 - 2020 카카오 블라인드 채용 물체가 보드의 2칸을 차지하는 유형의 BFS 문제다. BFS 문제들 중에서는 꽤 난이도가 있는 문제였던 것 같다. 해결 방법 2x1 크기를 차지하는 로봇에 대한 구조체를 {좌표1, 좌표2, BFS 깊이}로 구성하여 생성했다. 이렇게 좌표 2개를 동시에 따지면 로봇이 가로로 서있는지, 세로로 서있는지, 어느 방향으로 서있는지 고려할 필요 없다. 또 BFS에서 방문 여부를 검사할 때도 좌표 2개를 동시에 따져야 한다. 그래서 방문 배열을 사용하지 않고, 두 좌표를 pair로 저장하는 벡터에 저장했다. 로봇이 움직일 수 있는 경우는 크게 3개로 나뉜다. 1) 회전하지 않고 상하좌우로 이동하는 경우 2) 좌표1을 기준으로 회전하는 경우 3) 좌표2를 기준으로 회전하는 경우 좌표1, 좌표2 둘 중 하나라도 벽과 .. 2022. 3. 18.
[문자열] 방금그곡 - 2018 카카오 블라인드 채용 해결 방법 이 문제의 핵심은 치환이다. 치환 방법을 사용하지 않는다면 많은 소스 코드가 필요할 것이다. 왜냐하면, 하나의 음이 하나의 문자열을 차지해야 string 라이브러리를 편리하게 사용할 수 있기 때문이다. A#, C#, D#, F#, G#도 하나의 음이기 때문에 이를 각각 a, c, d, f, g로 치환해서 해결하면 된다. 각 함수의 용도는 주석으로 표시했다. 소스 코드 #include #include #include #include using namespace std; // 음악의 순번, 시작 시간, 끝 시간, 이름, 악보, 재생시간을 담은 구조체 struct music { int id; string start; string end; string name; string sheet; int len.. 2022. 3. 15.
[DFS] 괄호 변환 - 2020 카카오 블라인드 채용 단순히 주어진 조건대로 코딩하면 되는 문제이기 때문에 소스 코드에 사용된 함수만 설명하였다. bcheck 함수 괄호 문자열에는 균형잡히지 않은 괄호 문자열, 균형잡힌 괄호 문자열, 올바른 괄호 문자열 3가지 경우가 있는데, 어느 경우인지를 판단하여 반환하는 함수다. 괄호 문자열을 첫 문자부터 검사하면서 누적 '('과 ')'의 수를 카운트 하여 어느 케이스의 문자열인지 판단할 수 있다. - 균형잡히지 않은 괄호 문자열 : 누적 ')'의 개수가 누적 '(' 개수보다 큰 순간이 있는 경우 - 균형잡힌 괄호 문자열 : 총 ')'의 개수와 총 '(' 개수가 같은 경우 - 올바른 괄호 문자열 : 총 ')'의 개수와 총 '(' 개수가 같고, 누적 ')'의 개수가 누적 '(' 개수보다 큰 순간이 없었을 경우 dfs 함.. 2022. 3. 13.
[그리디] 추석 트래픽 - 2018 카카오 블라인드 채용 해결 방법 프로그래밍 언어로는 날짜 계산에 익숙한 Java를 선택했다. 요청 날짜가 밀리초(millis)까지 표시되므로, 두 날짜의 차이는 두 Date 객체의 getTime() 값의 차이로 구할 수 있다. getTime()은 지정된 시간을 long 타입의 밀리초로 표시한다. 그리고, 처리시간은 시작시간과 끝시간을 포함하므로, 측정 범위에서 끝시간-시작시간=999ms가 된다는 점을 기억해두자. 날짜 계산은 이렇게 하는걸로 하고, 이제 요청 i와 요청 j가 1초 간격 내에 포함되는가를 따져봐야 한다. 먼저, 요청 i의 왼쪽점 기준으로 따져봐야 한다. 요청 i의 왼쪽점 기준으로 요청 i와 요청 j가 1초 간격 내에 포함되는 경우는 다음과 같다. 위 4가지 경우는 3가지 조건으로 다음과 나타낼 수 있다. -> .. 2022. 3. 9.

티스토리툴바