1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 2. 문제 풀이today, terms, privacies 를 받아서 오늘 처리해야 할 개인정보 번호를 오름차순으로 answer에 저장해야 한다. 숫자 요소가 전부 string으로 들어오기 때문에 약간 까다롭다. 그리고 날짜를 어떻게 구분해야 할지 고민했는데, 전체 날짜를 '일'로 환산해서 오늘 날짜와 비교해서 기간이 지났는지 구분했다. #include #include #include #include using namespace std..
PS
1. 문제https://www.acmicpc.net/problem/14502 2. 문제 풀이이 문제는 지도를 순회하면서 바이러스가 퍼지지 않은 안전영역의 최대 크기를 구해야 한다. 여기에서 바이러스가 최소한으로 퍼지도록 벽을 총 3개만! 놓을 수 있다. 그래서 지도에서 0인 구역을 찾고 벽을 세운 다음(1로 처리), 3개의 벽을 다 세우고 나면 bfs를 통해서 안전구역의 개수를 구한다. 그래서 0인 구역을 찾을 때는 완전탐색, 바이러스가 퍼지고 난 후 안전구역을 찾을 때는 BFS를 사용해야 한다. 마지막으로 안전구역의 최대값을 구해주면 된다.#include #include #include using namespace std;int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, 1,..
1. 문제https://www.acmicpc.net/problem/1753 이 문제는 시작점 k부터 나머지 간선까지 최단 경로를 구하는 문제다. 정점과 간선의 개수는 1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000로 아주 큰 숫자다. 이를 주의해서 풀이해야 한다. 2. 문제 풀이처음에는 다익스트라 알고리즘을 사용해서, 2차원 벡터 weight에 각각의 방향 그래프를 초기화하고, distance를 업데이트하는 방식을 사용했다. 이렇게 하니까 메모리 초과가 떴다. 그 이유는 위에선 언급한 것처럼, 정점과 간선의 개수가 너무 많은데, 불필요하게 weight를 (n+1) * (n+1) 크기를 갖도록 설정해 희소행렬이 되어버렸다. #include #include #include #define INF 99..
1. 문제https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 2. 문제 풀이이 문제는 입력받은 숫자를 검사해서 최대 이익을 구해야 한다. 단, 하루에 하나만 구매할 수 있고 매매..
1. 문제https://www.acmicpc.net/problem/5427 2. 문제 풀이이 문제는 불이 매초마다 번질 때, 상근이가 몇 초만에 건물을 탈출 할 수 있는지 출력해야 한다. 불은 벽으로 번질 수 없으며 상근이는 벽을 통과하지 못한다. 상근이는 불이 옮겨진 칸이나 이제 불이 옮겨질 칸으로 이동할 수도 없다. 불이 상근이의 위치에 옮겨짐과 동시에 상근이가 다른 칸으로 이동할 수는 있다. 불도 매초마다 이동하고 상근이도 매초마다 이동할 수 있기 때문에 각각 BFS를 구현해야 한다. 그래서 상근이의 위치인 '@'이 입력으로 들어오는 경우와 불의 위치인 '*'이 입력으로 들어오는 경우, 각각의 큐에 push 한다. 불이 먼저 이동한 후에, 상근이가 이동해야 한다.불이 확산되는 BFS에서는 현재 fi..
1. 문제https://www.acmicpc.net/problem/1697 2. 문제 풀이수빈이와 동생의 위치를 입력받아서 동생의 위치까지 가는데 걸리는 시간을 출력하는 문제다.수빈이의 위치가 X라고 할 때, 1초만에걸어가면 X-1 혹은 X+1 만큼 갈 수 있다.순간이동하면 X * 2 만큼 갈 수 있다. 이때 1초에 이동할 수 있는 모든 경우의 수를 q에 넣고 하나씩 탐색하며 visited된 상태인지만 확인해주면 된다.#include #include using namespace std;queue > q;int visited[100001] = {0,};int main() { int n, k; cin >> n >> k; q.push(pair (n, 0)); visited[n] = 1;..
1. 문제https://www.acmicpc.net/problem/2573 2. 문제 풀이문제의 핵심은 다음과 같다.빙산과 바다 데이터를 2차원 배열로 입력받는다.바다에 많이 접한 빙산일 수록 높이가 더 빨리 줄어든다.1년마다 빙산의 높이가 줄어든다.덩어리가 2개 이상으로 분리되는 최초의 시간을 출력한다. 처음에는 BFS를 1번 돌면서 0에 맞닿아 있는 수만큼 값을 빼주었더니, 0이 되어버린 경우까지 포함되어서 BFS를 두 번 도는 방법을 택했다. 할 일은 다음과 같이 2가지로 나눌 수 있다.컴포넌트 개수 세기주변의 바다(0) 개수만큼 높이 낮추기컴포넌트를 세는 BFS, 주변의 바다 개수만큼 빼주는 BFS를 구현해보자. 먼저 컴포넌트를 세는 건 일반 BFS처럼 방문처리하고 q에서 하나씩 읽어오면 된다...
1. 문제https://www.acmicpc.net/problem/7569 2. 문제 접근문제를 요약하면 다음과 같다. 위, 아래, 오른쪽, 왼쪽, 앞, 뒤 총 6방향을 탐색해야 한다.익은 토마토는 익지 않은 토마토에 영향을 준다.한 상자에 들어있는 토마토가 모두 익는데까지 걸리는 기간을 출력한다.만약 배열에 저장될 때부터 모든 토마토가 익은 상태면 0, 모든 토마토가 익지 않은 상태면 -1을 출력한다. 이를 기반으로 문제를 풀어보자. 입력될 때부터 익은 토마토라면 q에 위치를 저장한다. 그리고 익은 토마토 위치에서부터 bfs 탐색을 시작하고, 만약 익지 않은 토마토가 인접해있다면 1로 바꾸어주고 tmp에 push 한다. 이때 tmp는 입력된 이후, 다른 토마토에 의해 익은 토마토가 된 것의 위치를..
1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 2. 문제 해석이 문제는 주어진 숫자를 적절히 더하거나 빼서 target를 맞추는 경우의 수를 구하는 문제이다. 예를 들어, [1, 1, 1, 1, 1] 이라는 배열이 주어졌을 때, 각각을 더하거나 뺄 수 있으므로 자연스럽게 트리 구조를 떠올릴 수 있다. 그래서 재귀적인 방법을 사용해 트리를 순회해 최종 리프 노드의 값이 target과 같으면 answer++ 해주면 된다. #include #..
1. 문제 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 2. 문제 접근 문제를 이해하다보니 BFS로 풀면 되겠다고 답이 나왔다. 그래서, BFS 코드를 구현했더니 틀렸다. 문제를 제대로 안봤으니까. 결론적으로 1부터 5까지 각 숫자에 도달할 때까지 거리를 구하면 80%는 해결이다. 예시의 그래프는 아래와 같이 표현할 수 있다. 1부터 예시를 들면, 1은 2까지 [1-3-2]로 2단계, 3까지 ..
