알고리즘매일매일

https://programmers.co.kr/learn/courses/30/lessons/64063

먼저 깔끔한 문제풀이 설명은 카카오 테크 블로그에서 볼 수 있다.

https://tech.kakao.com/2020/04/01/2019-internship-test/

효율성 테스트가 있는 문제로 k의 범위가 크기 때문에 방을 하나하나 순차적으로 검사해주면 효율성 테스트에 실패한다.

효율성을 통과하는 방법은 위의 카카오 테크 블로그에 그림과 함께 굉장히 잘 설명되어있는데, 

요청한 방이 빈방이라면 바로 배정하고 배정된 방이 바로 다음 방을 가리키도록 해준다.

요청한 방이 빈방이 아니라면 그 방이 가리키는 다음 방을 계속 찾아가며 빈방을 찾는다.

이 방법은 Union-Find 알고리즘을 사용해서 효율적으로 구현할 수 있다. 부모 노드가 다음 빈 방의 번호 값을 가지도록 해주면 된다.

https://programmers.co.kr/learn/courses/30/lessons/64064

먼저 깔끔한 문제풀이 설명은 카카오 테크 블로그에서 볼 수 있다.

https://tech.kakao.com/2020/04/01/2019-internship-test/

당첨에서 제외되어야 할 제재 아이디 목록이 몇 가지 경우의 수가 가능한 지를 구해야하는데 id배열의 크기가 8 이하이므로 모든 경우를 구해봐도 된다.

먼저 각 불량 아이디에 대해 모든 응모 아이디와 비교하여, 매핑될 수 있는 응모 아이디를 찾아 각각의 응모 아이디에 매핑되는 경우를 조합해준다. 불량 아이디와 매핑 될 수 있는 응모 아이디는 불량 아이디의 *부분을 제외한 모든 문자가 일치해야 하고 문자열의 길이도 같아야 한다.

응모 아이디를 제재목록으로 만들어주는 방법은 응모 아이디의 인덱스를 문자열로 만든 후에 이전 제재 목록 문자열과 합쳐서 넘겨주는 방법으로 구현했다.

문제에 나온 첫 번째 예시로 예를 들어보면 

user_id

frodo와 abc123을 선택하는 경우는 각각 인덱스가 0과 3이므로 "03"

fradi와 abc123을 선택하는 경우는 각각 인덱스가 1과 3이므로 "13"이 된다.

그리고 제재 아이디 목록은 순서가 상관없으므로 이 문자열을 정렬해준 후 set에 넣어줘서 중복을 제거해줬다.

최종적으로 set의 크기가 정답이 된다.

https://programmers.co.kr/learn/courses/30/lessons/64065

먼저 깔끔한 문제풀이 설명은 카카오 테크 블로그에서 볼 수 있다.

https://tech.kakao.com/2020/04/01/2019-internship-test/

튜플이 (2, 1, 3)인 경우 문제 조건에 따라 집합으로 표현하면 다음과 같이 된다.

{{2}, {2, 1}, {2, 1, 3}} 

또한, 문제에서도 나와 있듯이 집합의 원소는 순서가 바뀌어도 상관없으므로

{{1,2}, {3, 1, 2}, {2}} 와 같이 표현해도 튜플 (2, 1, 3)을 나타낸다.

하지만 집합으로부터 튜플을 찾기 위해서는 {{2}, {2, 1}, {2, 1, 3}} 와 같이 원소의 개수가 작은 순으로 정렬되어 있어야 한다.

1. 우선 집합이 문자열로 주어지므로 파싱해서 같은 원소끼리 벡터에 넣어준다.

위의 {{1,2}, {3, 1, 2}, {2}} 로 예시를 들면, 원소들을 넣은 벡터를 다시 벡터에 넣어줘서

아래와 같이 2차원 벡터가 되도록 만들어준다.

vector<vector<char>> tmp = {{1,2}, {3, 1, 2}, {2}};

c++로 하다 보니까 문자열 파싱이 조금 번거롭긴 하지만 { 와 }, 쉼표( , ) , 숫자를 각각 구분해주면 된다.

숫자는 110처럼 한 자릿수가 아닐 수도 있으므로 쉼표가 나오기 전까지 하나의 숫자로 만들어주어야 한다. (이전의 수에 곱하기 10을 하고 현재수를 더해준다)

{ 인 경우는 따로 의미가 없어서 그냥 continue로 넘어가 주고

} 인 경우에 하나의 원소가 끝난 것이므로 벡터에 원소를 넣어주고 원소들을 넣어줬던 벡터를 다시 2차원 벡터에 넣어준다. 이때, 나중에 크기 순으로 정렬하기 위해서 원소들을 넣어줬던 벡터의 사이즈와 벡터를 함께 pair로 넣어준다.

vector < pair<int, vector<int> > > vt;

pair를 사용하면 정렬했을 때 pair의 첫 번째 값을 기준으로 먼저 정렬되기 때문에 이렇게 구현했지만, 크기를 기준으로 정렬하는 compare함수를 구현해서 정렬할 때 넣어줘도 된다.

2. 위에서도 언급했지만 순서가 섞여있는 집합을 {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4},... {a1, a2, a3, a4,..., an}}의 순서로 만들어 주어야 (a1, a2, a3, ..., an)의 튜플을 나타내는 원소를 쉽게 찾을 수 있는데, 그러기 위해서는 크기(원소가 들어가 있는 개수)를 기준으로 정렬해주면 된다.

위의 {{1,2}, {3, 1, 2}, {2}} 로 예시를 들면 크기로 정렬했을 때, {{2}, {2, 1}, {2, 1, 3}} 가 된다.

({2}는 1개이므로 크기가 1, {2, 1}은 2개이므로 크기가 2)

3. 마지막으로는 set을 이용하여 중복 체크를 해줬다. 벡터를 탐색하며 set에 없다면 set에 추가하고 answer에도 추가해줘서 튜플의 원소로 추가해준다.

https://programmers.co.kr/learn/courses/30/lessons/64061

먼저 깔끔한 문제풀이 설명은 카카오 테크 블로그에서 볼 수 있다.

https://tech.kakao.com/2020/04/01/2019-internship-test/

인형을 바구니에 쌓는 것을 스택을 이용해서 구현해준다.

터트려져 사라진 인형의 개수를 구하는 것이므로 터질 때마다 정답에 2씩 더 해주면 된다.

처음에 문제를 제대로 안 읽어서 바구니에 남아있는 인형이 정답인 줄 알고 왜 정답이 안 나오지 하고 있었다...

먼저 moves에 있는 인형을 뽑을 위치는 1부터 시작하므로 인덱스로 사용하기 위해서 1을 빼주고 사용한다.

그리고 해당 위치에서 인형이 있는 곳까지 아래로 쭉쭉 내려간다.

문제 조건에 따라 인형을 발견하지 못하면 그냥 다음 뽑을 위치로 넘어가면 되고, 집어 올린 인형과 바구니 위의 가장 위에 있는 인형을 비교해준다.

바구니(스택)의 가장 위에 있는 인형과 현재 뽑은 인형이 같다면 가장 위에 있는 인형을 스택에서 pop 해주고 정답에 2를 더해준다.

같지 않다면 그냥 뽑은 인형을 바구니(스택)에 push 해준다.

스택에 쌓이든 터져서 사라지든 일단 크레인으로 잡혀서 왔으므로 원래 있던 자리는 0으로 만들어서 빈칸으로 만들어주고 다음 위치로 크레인을 작동시키기 위해서 아래칸으로의 탐색은 중단한다.

https://www.acmicpc.net/problem/18809

백준에서 BaaaaaaaaaaarkingDog님이 코딩 테스트 대비 모의고사로 출제하신 완전 탐색+bfs문제이다.

대회가 열렸을 때 들어가서 풀어봤는데 재밌었다. 처음 제출했을때 시간초과가 나서 당황했는데 쓸데없는 작업을 줄여줬더니 통과했다

(꽃이 피는 곳을 저장해놓은 배열을 나중에 처음부터 끝까지 확인해서 꽃의 수를 세줬었는데, 꽃이 필때 꽃을 바로 세는 걸로 바꿔줬다)

다른 한 문제는 18808 스티커 붙이기(문제 링크)이다. (18808 스티커 붙이기 풀이 링크)

풀이 코드는  BaaaaaaaaaaarkingDog님의 블로그에서도 볼 수 있다.

나는 다음과 같은 방법으로 풀었다.

1. 정원의 정보를 입력받을 때, 값이 2 (배양액을 뿌릴 수 있는 땅)이면 벡터에 넣어놓는다.
2. 앞에서 저장해논 배양액을 뿌릴 수 있는 땅들에 대해 배양액을 뿌리지 않는 경우 / 초록색 배양액을 뿌리는 경우 / 빨간색 배양액을 뿌리는 경우를 모두 골라준다. 배양액을 뿌리는 경우에는 뿌리는 배양액의 수 - 1을 매개변수로 넘기고 뿌리지 않는 경우는 배양액의 수를 그대로 넘긴다.
   • 이때 백트랙킹으로 시간을 줄여줘야 하므로
   • 남은 배양액의 수가 남아있는 배양액을 뿌릴 수 있는 땅보다 많으면 안 되므로 더 이상 탐색을 진행하지 않는다.(배양액을 남김없이 사용해야 하고, 땅에 배양액 2개를 사용할 수 없으므로)
   • 초록색과 빨간색 배양액을 둘 다 모두 사용했다면 남은 땅의 경우의 수를 더 정해주지 않고 바로 bfs로 배양액을 퍼뜨려준다.
3. bfs를 진행할 때에는 초록색 배양액과 빨간색 배양액을 각각 큐에 넣어서 따로 bfs를 진행해주는데, 도착한 시간을 저장하는 배열도 각각 사용한다. 또한, 각각의 큐 사이즈만큼씩 진행해서 bfs를 단계별로 진행한다.(각 초마다 bfs를 진행 가능)
   • 나는 먼저 초록색 배양액을 퍼뜨려줬다. 꽃이 피었거나 / 호수이거나 / 이미 배양액이 뿌려져 있는 경우를 제외하고 바로 퍼뜨리면 된다.
   • 그다음에 큐 사이즈만큼 진행함으로써 초록색 배양액을 뿌린 같은 시간 동안 빨간색 배양액을 뿌릴 수 있다. 빨간색 배양액을 뿌릴 때에는 초록색 배양액이 이미 뿌려져 있어도 같은 시간에 뿌려진 것이라면 꽃이 피므로 이때 꽃의 수를 늘려준다. 이때, 큐에는 넣지 않고 시간만 저장해줘서 다음에 배양액이 퍼지지 않도록 한다.
4. 배양액을 모두 퍼뜨렸다면 꽃의 수를 저장해놓은 최댓값과 비교한다.

https://www.acmicpc.net/problem/18808

백준에서 BaaaaaaaaaaarkingDog님이 코딩 테스트 대비 모의고사로 출제하신 시뮬레이션 문제이다. 대회가 열렸을 때 들어가서 풀어봤는데 재밌었다. 총 두 문제였는데 나머지 한 문제는 18809번 Gaaaaaaaaaarden (문제 링크)이다. (풀이 링크)

스티커 붙이기 문제가 좀 더 쉽다. 

먼저 매번

 sticker를 저장할 int배열 / 모니터에 스티커가 붙여졌는지 확인할 bool 배열 / 스티커를 90도 회전시킬 때 임시로 사용할 int 배열

이렇게 세 가지 배열을 사용하였다.

문제에서 나와있는 스티커를 붙이는 조건은 다음과 같다.

1. 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
3. 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

위의 조건에 따라 먼저 입력받은 스티커를 노트북의 위쪽부터 붙일 수 있는지 확인한다. 

(0, 0)부터 (N-R, M-C) 칸까지 각 칸을 스티커의 시작점으로 했을 때의 스티커를 붙이는 경우를 순차적으로 해보고

붙일 수 있다면 바로 그 자리에 붙인다. 문제 조건에서 스티커를 붙일 우선순위는 가장 먼저 가장 위쪽, 그다음에 가장 왼쪽이므로 일반적인 for문으로 돌리고 찾는 순간 바로 탐색을 종료하면 자연스럽게 구현할 수 있다.

스티커를 붙일 수 있는지는 단순히 스티커를 저장해놓은 배열과 모니터에 스티커가 붙어있는지 확인할 배열을 비교해주면 된다.

비교할 때나 모니터에 스티커를 붙여줄 때, 확인할 모니터의 시작점을 주의해야 한다.

스티커는 매번 (0, 0)부터 검사해주면 되지만 모니터는 스티커를 붙이기 시작하는 칸부터 검사해야 하므로

스티커를 모니터의 (x, y) 칸부터 붙여본다고 한다면 스티커의 (i, j)를 확인할 때는 모니터의(i+x, j+y) 칸을 비교해주어야 한다.

모니터에 이미 스티커가 있는데 모눈종이 위에도 스티커가 있다면 붙일 수 없으므로 바로 false를 리턴해서 다음 경우로 넘어간다.

붙일 수 있다면 모니터에 스티커를 붙여주고 다음 스티커로 넘어간다.

모든 칸에서 시작해도 스티커를 붙일 수 없다면 90도 회전해서 똑같은 과정을 반복한다.

90도씩 회전시켜서 모든 경우(0도, 90도, 180도, 270도)를 해봤는데도 붙일 수 없다면 문제 조건에 따라 해당 스티커는 버린다.

90도 회전을 시킬 때는 위의 그림과 같이 tmp배열의 index를 기준으로 복사해줬다.

90도 회전하게 되면 행의 수(R)와 열의 수(C)가 되므로 for문에서 i는 C 전까지, j는 R 전까지 해주면 된다.

for문을 이용해서 tmp배열은 순차적으로 채워주면 되고, 스티커 배열은 i와 추가적인 변수 l 을 사용해서 위의 그림에 나와있는 순서대로 값이 들어가도록 구현했다. 코드로 보면 다음과 같다.

for (int i = 0; i < c; i++) {

        for (int j = 0, l = r-1; j < r; j++, l--) {

            tmparr[i][j] = sticker[l][i];

        }

    }

tmp배열에 모두 복사했다면 R과 C의 값을 아예 바꿔주고 tmp배열의 값을 원래 스티커 배열로 다시 옮겨준다.

k번의 스티커를 모두 붙여 본 후에 모니터에 스티커가 붙여져 있는지 확인하는 배열을 검사해서 최종 답을 구한다.

https://www.acmicpc.net/problem/17822

원판을 회전시키며 인접한 수를 비교하고, 같다면 숫자를 지우는 작업을 반복하는 시뮬레이션 문제이다.

T회만큼 반복하면서 x의 배수인 원판들을 모두 회전시킨 후 인접한 같은 수를 저장해놓았다가 나중에 한 번에 지워준다. (미리 지워서 0으로 만들어버리면 다른 방향으로 인접한 수를 지울 수 없다)

인접한 수 중 같은 숫자인게 없다면 원판에 있는 숫자의 평균을 구해서 평균보다 작으면 1을 증가시켜주고 크면 1을 감소시킨다. 여기서 지워진 숫자는 제외하고 평균을 구해야 한다

//k칸만큼 회전시키기

먼저 k칸만큼 시계방향 회전시킨 방법은 아래와 같이 했다. 예를 들어 k가 4인 경우이다.

편의상 배열은 인덱스가 1부터 시작하도록 구현했다.

원래 원판에 있던 숫자를 첫 번째부터 tmp배열의 k만큼 떨어진 곳인 5번 자리부터 복사한다. 인덱스가 배열 밖으로 넘어가면 안 되므로 작업을 tmp배열의 마지막 부분인 6번 인덱스까지만 먼저 진행한다.

그다음 아래 그림처럼 원판의 나머지 부분을 이어서 tmp배열의 처음 칸부터 k번 인덱스까지 순차적으로 채워주면 된다.

시계 반대 방향으로 1번 회전시킨 것은 시계 방향으로 M-1번 회전시킨 것과 같고

마찬가지로 시계 반대 방향으로 2번 회전시킨 것은 시계 방향으로 M-2번 회전시킨 것과 같으므로

같은 함수를 이용해서 회전 횟수를M-k번으로 해주면 된다.

//인접한 숫자 중 같은 수 찾기

문제에 나와있는 인접한 수의 조건은 다음과 같다.

• (i, 1)은 (i, 2), (i, M)과 인접하다.
• (i, M)은 (i, M-1), (i, 1)과 인접하다.
• (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
• (1, j)는 (2, j)와 인접하다.
• (N, j)는 (N-1, j)와 인접하다.
• (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

그냥 같은 원판(같은 행) 안에서 바로 양 옆이 인접한 수이고, 바로 위나 아래에 있는 원판 중에서는 같은 열이 인접한 수이다. 그래서 같은 원판 안에서는 마지막 숫자의 옆이 다시 첫 번째 숫자인 것을 처리해주어야 하지만

서로 다른 원판들의 위아래를 비교할 때는 맨 위의 원판과 맨 아래의 원판은 인접한 것이 아니므로 따로 처리해줄 필요는 없다.

//인접한 같은 수 지우기

또, 인접한 같은 수를 미리 지워서 0으로 만들어버리면 다른 방향으로 인접한 수와 비교할 수 없으므로 나중에 한 번에 지워줘야 한다. 그러기 위해서 인접한 같은 수를 가진 좌표들을 저장해놓아야 한다.

중복되는 좌표도 발생할 것 같아서 set을 이용하였다. 인접한 수를 찾으면 set에 원판의 위치(i, j)를 pair로 넣어주고, 나중에 set에서 한 번에 위치를 꺼내서 원판의 해당 위치의 숫자를 지워준다. 

(이때 나는 한쪽 방향으로만 비교하도록 구현했기 때문에 인접한 같은 두 수의 위치를 모두 넣어줬다)

//평균 구해서 더하고 빼주기

위에서 인접한 같은 수가 없어서 지워진 수가 하나도 없다면 문제 조건에 따라

원판에 있는 수들의 평균을 구해서(지워진 수는 제외) 평균보다 높다면 1을 빼주고 평균보다 낮다면 1을 더해준다.

c++에서 int형으로 몫을 구했다면 소수점을 제외한 몫만 저장하므로 나누어 떨어지지 않는 경우를 따로 처리해준다.

나누어 떨어지는 경우는 정말 값이 같은 경우이므로 값을 바꿔줄 필요가 없고

나머지가 있다면 실제 값은 몫+나머지 이므로 원판의 값이 평균보다 더 작은 것이므로 1을 더해준다.

//최종 답

T번의 회전이 모두 끝나면 원판의 숫자를 모두 더해준 값이 정답이다.

개인적으로 실수한 부분들 메모...

1. 평균을 구하는 과정에서 0으로 나누는 경우가 발생하면 안 된다.
2. 문제 조건에서 평균보다 큰 경우와 작은 경우에 대해만 나와있으므로 같은 경우에는 값이 변하지 않는다.
3. n과 m을 또 반대로 씀... 문제에서 반대로 해놓은 것이 아니었음에도 불구하고...
4. 문제 조건을 제대로 안 읽고, 인접한 수가 없는 경우 평균을 구해서 값을 변경시켜주는 부분을 안봄...
5. 인접한 같은 수 두 개를 set에 넣을 때 하나만 넣어줘서 제대로 안 지워짐

https://programmers.co.kr/learn/courses/30/lessons/60059

lock의 크기와 key의 크기가 최대 20이므로 완전 탐색으로 해결할 수 있다.

(key를 90도씩 회전시키는 네 가지 경우) X (자물쇠에 열쇠를 맞춰보는 모든 경우)를 구해주면 된다.

주의할 점은 예제에는 똑같이 나와있지만 lock의 크기와 key의 크기는 다를 수 있다.

또, 열쇠를 회전시킬 때 회전시키는 함수에서 실제 key 벡터를 회전시켜야 하므로 &로 받아야 한다.

문제 조건에 따라서 열쇠는 자물쇠 밖으로 나가도 되므로

열쇠를 자물쇠 홈에 맞춰보는 모든 경우를 위해서 아래 그림과 같이 새로운 2차원 vector를 만들어줬다.

열쇠의 가장 오른쪽 아랫부분과 자물쇠의 가장 위쪽 부분을 맞추는 경우부터

열쇠의 가장 왼쪽 윗부분과 자물쇠의 가장 오른쪽 아래 부분을 맞추는 경우까지를 모두 해주면 되기 때문에

lock의 크기 + (key의 크기 -1)*2 크기의 벡터를 만들어주면 된다.

그러면 매 회전 때마다 key의 시작 부분이

(0,0)에서 시작하는 경우부터 lock의 가장 마지막 부분(boardsize-keysize)에서부터 시작하는 경우까지 해보면서

key를 board에 더해 lock부분이 모두 1인지(홈이 모두 채워졌는지)를 확인하면 된다

한 곳이라도 0이거나(비어있는 홈) 2(돌기 두 개가 만남) 이면 안되므로 바로 false를 리턴한다.

**기존 상태에서 먼저 열쇠를 맞춰보면 회전은 3번만 하면 된다고 생각해서

반복문을 3번만 실행하도록 했어서 한참 헤맸다;;

맞춰보는 경우는 어쨌든 4번 해야 하므로 반복문을 4번 실행해주어야 한다...