판교의 메타몽

문제 링크 : www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 이 문제는 시행착오를 많이 거쳤다. 첫 번째 실수는 다음과 같다. (1) 무작정 스택으로 구현하고 메모리 초과 나기 #include #include #include #include using namespace std; string s = "", temp = "", temp2=""; stack st; int main(void) { ios_base::sync_with_stdio(false); c..

The link : leetcode.com/problems/surrounded-regions/ Surrounded Regions - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제는 다음과 같다. 1. 4방위가 X로 둘러쌓인 O를 X로 전환한다. 2. 아래 예시 같은 경우에도 4방위가 X로 둘러쌓인것이 인정된다. 3. 그러므로 테두리에 해당되는 영역은 O,X에 관계없이 전환이 불가능하다. 4. 테두리와 4방위로 이어진 영역 또한 마찬가지다. 문제 풀이는 다음..

링크 : www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 예전에 Union & Find 알고리즘과 관련하여 유사 문제로 풀어본 경험이 있는 문제다. 문제 해석이 난해할 수 있는데, 한 줄로 요약하면 2가지 색으로 서로 연결된 노드끼리 겹치지 않게 칠할수 있는가를 묻는 문제이다. 문제 풀이는 다음과 같다. 1. 방향성이 정해지지 않은 노드, 즉 양방향 노드이다. 때문에 1번과 3번이 연결되어있으면 3번과 1번도 연결되어있다는 뜻이므로, 배열[1]에..

링크 : www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 풀이는 다음과 같다. 1. N+1일이 퇴사일이라는 점을 기억하자. 2. 백트래킹 - DFS를 통해 모든 경로를 구한다. 경로를 구하는 방법은 다음과 같다. (1) 현재 날짜에서 업무 날짜를 더한 값이 퇴사일을 초과하지 않으면 돈을 누적하여 dfs를 진행한다. (2) 현재 날짜의 다음날이 퇴사일을 초과하지 않으면, 해당일부터 또다시 새로운 dfs를 진행한다. #include #include #include using namespace std; int n, res, a, b = 0; vector v; vector ans(16, 0); v..

The link : leetcode.com/problems/letter-combinations-of-a-phone-number/ Letter Combinations of a Phone Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제는 다음과 같다. 1. 사진과 같은 전화기가 주어지며, 2번~9번 사이의 수가 최대 길이 4를 넘지 않을만큼 주어진다. 단, 주어지는 값은 문자열이다. 2. 다이얼 패드로 가능한 조합들을 출력하라. 예시는 다음과 같..

링크 : www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 그다지 어렵지 않지만, 좌표를 받는 부분에서 반복적으로 실수를 냈다. #include #include #include using namespace std; int m = 0, n = 0, k = 0, my = 0, mx = 0 ,width = 0; bool ch[102][102] = { false, }; int yy[4] = { 0,1,0,-1 }; int xx[4] = { 1,0,..

링크 : programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 분류 : 깊이/너비 우선 탐색 (DFS/BFS) 이 문제는 제한사항들 중에서 서로 충돌하는 포인트가 있다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return합니다. 주어진 항공권은 모두 사용해야 합니다. 이 두 조건을 동시에 고려하지 않고 문제를 풀면 아래와 같은 예시에서 충돌이 발생한다. 입력값 : [["ICN", "AAA"], ["AAA", "CCC"], [..

링크 : programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있�� programmers.co.kr 분류 : 깊이/너비 우선 탐색 (DFS/BFS) 이 문제는 배열, 혹은 벡터를 넘겨줄때 Call by value가 아닌 Call by reference로 넘겨줘야한다. 깊이 생각하지 않고 코드를 작성하다가 무작정 Call by value로 적어낸 덕에 탈락을 맞이했고, 곰곰이 생각한 후에 Call by value로 벡터를 넘긴 탓에 v[x][x]=0이라는 값..

링크 : www.acmicpc.net/status?user_id=shuhu_01&problem_id=2573&from_mine=1 채점 현황 www.acmicpc.net 문제의 풀이는 다음과 같다. (1) 배열 arr에 값을 입력한다. (2) 배열 arr의 각 위치에 위 / 아래 / 좌 / 우의 값이 0인 갯수만큼 마이너스 한 값을 배열 v에 옮겨준다. (melt 함수 참고) * 배열을 이중으로 만들지 않고 순차적으로 하나하나 값을 계산해주면 다음과 같은 실수를 겪게된다. 1 -> 0 3 3 2 주변의 '0'의 값만큼 제외해주는 계산으로 1의 값이 0으로 되고, 그대로 다음 배열의 값으로 넘어갈경우 0 1 -> 0 3 -> 0 0 3 2 3의 값이 0으로 변경되어버린다. 원래 옳바른 계산은 위쪽 / 오른..

링크 : www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 문제의 풀이는 다음과 같다. (1) 배열을 2개 만든다. 하나는 값을 입력받을 값(arr), 다른 하나는 방문 여부를 파악하고 동시에 토마토가 익을 날짜를 누적할 배열(check)이다. (2) 배열에 값을 넣는다. 이때 check(방문여부를 파악하는 배열)는 모두 -1로 채워넣는다. (3) 배열에 입력된 값이 '1'일 경우(즉, 익은 토마토이다), 해당 배열의 쌍을 큐에 넣어주고 ch..