Algorithm

[프로그래머스] level2 단체사진 찍기 (C++)

2017 카카오코드 본선 사람이 8명 뿐이다. 모든 사람을 줄세우는데 O(8!) 만큼의 시간이 걸릴 것이다. 따라서 백트래킹으로 모든 경우를 탐색해도 시간내에 충분히 풀린다. 백트래킹 부분 void sorting(int cnt, int &answer, vector &data, map &m){ if(cnt == 8){ if(is_valid(data, m)){ answer++; } return; } for(int i = 0; i < 8; i++){ if(visited[i]) continue; visited[i] = cnt+1; sorting(cnt+1, answer, data, m); visited[i] = 0; } } 중요한 부분은 visited배열의 정의이다. visited배열의 인덱스는 사람의 번호이다..

[프로그래머스] level2 빛의 경로 사이클 (C++)

월간 코드 챌린지 시즌 3 그림만 보면 무시무시하지만 실제 풀이는 그렇지 않다. 하나의 격자에 빛을 쏘면 내부에서 사이클을 이룬다. 내부에서 퍼지는 게 아니라 하나의 길로 쭉 들어간다고 생각해서 바로 dfs로 풀었다. bool cache[501][501][4]; cache 배열이 중요하다 cache[r][c][dir] r, c 의 격자에 dir 방향으로 들어온 적이 있는지를 체크하는 배열이다. 나는 dir 방향으로 들어온 적이 있다면 반드시 그 경우에 해당하는 사이클이 존재한다고 생각했다. 적어도 위 예제만 봐도 모든 경로를 다 탐색한다. 만약 다른 예제가 오더라도 아직 방문하지 않은 경로를 시작점으로 탐색을 하는데, 이미 탐색한 다른 경로를 건드릴일이 절대로 없다는 것이다. bool &ret = cac..

[프로그래머스] level2 튜플 (C++)

2019 카카오 겨울 인턴십 배열이 주어지고, 튜플을 만드는 방법을 문제에서 친절히 알려줬다. 원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다. {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}} 예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는 {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}} 문제에서 원하는 답은 튜플을 분석해서 원래의 배열을 구하라는 것이다. 문제는 튜플이 문자열로 주어진다는 것이다.. 나는 C++..

[프로그래머스] level2 행렬 테두리 회전하기 (C++)

2021 Dev 매칭-벡엔드 2차원 좌표에서 직사각형을 정하고, 테두리를 시계방향으로 회전시키는것을 구현하는 문제이다. 완전히 구현력을 요구하는 문제이다. 삼성 A형 기출문제와 느낌이 비슷했다. 직사각형과 회전시킬 영역이 주어진다. 나는 회전을 위해서는 4개의 꼭짓점만 알면 된다고 생각했다. 그래서 주어지는 queries배열에서 4개의 꼭짓점을 추출하고, 되돌아오는 것 까지 생각해서 총 5개의 점을 vertex 벡터에 입력했다. for(auto &q: queries){ vector vertex; vertex.push_back({q[0], q[1]}); vertex.push_back({q[0], q[3]}); vertex.push_back({q[2], q[3]}); vertex.push_back({q[2]..

[프로그래머스] level2 메뉴 리뉴얼 (C++)

2021 카카오 블라인드 채용 문제를 읽어봤는데 요구사항을 한 번에 이해하지 못했다. 카카오 문제 특징인 것 같다. 지문이 너무 길다.. 그래서 처음 풀때는 시간내에 풀지 못하고 풀이만 어렴풋이 생각해둔채로 넘겼었다. 다시 풀기위해서 차분하게 풀이를 머릿속에 모두 정리하고 코딩에 들어갔다. 개인적으로 깔끔하게 풀린것같아서 마음에 드는 코드이다. 먼저 orders로 들어온 string을 오름차순 정렬하기 위해서 char로 모두 분해한 다음에 알파벳 순으로 정렬해서 2차원 벡터 형태로 만들어줬다. vector norders; for(auto str: orders){ vector temp; for(int i = 0; i < str.size(); i++){ temp.push_back(str[i..

[프로그래머스] level2 수식 최대화 (C++)

풀이 주어진 표현식을 숫자와 연산자로 나눈 후 각각 다른 배열에 넣어준다. 기본적인 백트래킹을 사용해 '*+-'로 구성된 연산자의 순서를 정해준다. 백트래킹의 마지막 부분에 도달해 연산자의 순서가 정해지면 표현식을 순서대로 계산한다. 현재 표현식의 연산자(forj)와 우선순위에 따른 연산자(fori)가 동일한 경우에 값을 계산해서 적절한 위치에 값을 갱신해준다. 그리고 사용한 연산자와 숫자는 erase메서드를 사용해서 지워준다. 여기서 주의할 점은 벡터를 for문으로 순회하는 도중에 원소가 지워지면 인덱스에 문제가 생길 수 있다. 따라서 현재 인덱스를 지워진 원소의 개수만큼 빼줘야 한다. 계산된 값을 비교하면서 최댓값을 저장해둔다. #include #include #include using namespa..

[프로그래머스] level2 거리두기 확인하기

단순 bfs, dfs 문제이다. 최대 2칸까지 이동할 수 있다. 다음 칸이 'X'인 경우 이동하지 않는다. 다음 칸이 'P'인 경우 거리두기가 지켜지지 않은 것이므로 false를 반환한다. bfs로 풀면 queue의 각 원소가 현재 몇 칸 움직인 상태인지 저장해두는 작업이 필요해서 queue를 구성하는 struct를 새로 구현하게 되었다. #include #include #include #include #define pii pair using namespace std; struct Info{ pii now; int cnt; }; int dr[4] = {0, 0, 1, -1}; int dc[4] = {1, -1, 0, 0}; int Map[6][6]; bool check(int r, int c){ queu..

[프로그래머스] level2 뉴스 클러스터링

나는 문제를 잘못읽어서 2시간 넘게 삽질했다. 두 글자씩 끊어서 다중 집합을 만든다. 이때 집합에 특수 기호나 숫자가 들어있을 경우 그 쌍은 버린다. 이 조건을 잘못 읽었다. 어떻게 잘못 읽었냐면 주어진 문자열에서 특수 기호나 숫자를 먼저 모두 지워버리고, 특수 기호나 숫자가 없는 쌍을 만드는 걸로 착각했다. 당연히 특수 기호나 숫자를 먼저 지워버리면 제대로된 값이 나오지 않을 것이다. ex) 예제 2, 3번 풀이 입력 받은 문자열을 모두 대문자로 바꿔준다. 문자열을 2개씩 끊어서 새로운 배열에 넣어준다. 이때 2개의 문자 중 특수 기호나 숫자가 있으면 배열에 넣지 않고 넘어간다. 배열의 길이는 최대 999 * 999 = 약 100만 이다. 따라서 N^2 풀이가 가능하다고 생각했다. 2개의 배열을 가지고..

[백준 2836] 수상 택시 (C++)

2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 그리디인줄 알고 삽질을 오래 했다. 스위핑 문제였다. 시간이 녹았다 하지만 스위핑을 제대로 되새길 수 있었다! 역방향 이동거리 * 2 == 초록색으로 표시된 거리 * 2 -> 되돌아 가서 승객을 내려주기 + 되돌아 가기 전 위치로 복귀 ANSWER : M + 위 값들의 합 스위핑 문제임을 파악하고 좌표의 left, right 값을 잘 설정해주자. #include #include #include #include #include #define fasti ios_b..

[백준 4095] 최대 정사각형 (C++)

4095번: 최대 정사각형 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두 www.acmicpc.net 반례: 1 1 0 answer : 0 1 2 0 answer : 0 2 1 1 2 answer : 1 dp[r][c] : r,c를 오른쪽 아래 꼭짓점으로 가지는 정방 행렬의 크기. 현재 위치의 왼쪽, 위, 왼쪽 위 대각선의 dp값 중에서 가장 작은 값을 +1 한게 현재 위치의 dp값이 된다. dp[r][c] = min(dp[r-1][c-1], min(dp[r][c-1], dp[r-1][c])) + 1; ❗️주의사항 : answer를 반드시 ..