세상을 바꾸는 데이터

① 문제 링크 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net ② 알고리즘 분류 그래프 이론, 그래프 탐색, 깊이 우선 탐색 ③ ★문제풀이 Point★ - N(인원수)의 범위가 2000이 최대이므로 방문 표시를 2001개 만들기 - dfs를 돌리며 조건(5명의 친구 관계가 성립)에 맞는지 확인 ④ 풀이 이 문제는 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력하는 문제이다. 문제에서 캠프에 있을 수 있는 명수 N가 최대 2000이므로 방문 표시 visited를 2001개 지정해준다. 친구 관계를 나타내는 리스트 rela..

① 문제 링크 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net ② 알고리즘 분류 구현, 시물레이션 ③ ★문제풀이 Point★ 1. 문제에서 요구하는 내용 그대로 충실히 코드 구현하기 2. 공기청정기 바람 이동은 파이썬의 swap(변수 바꾸기) 이용하기 ④ 풀이 이 문제는 방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구하는 문제이다. 문제에서 요구하는 대로 먼저 미세먼지의 확산 함수(dust_diffusio..

문제 링크: https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 ★문제풀이 Point★ 1. 계속해서 이동하는 벽을 어떻게 추가하고 삭제하는지 고민 필요(set, pop, appendleft) 2. 캐릭터가 이동한 다음, 벽이 이동하는 순서로 진행 3. 너비 우선 탐색(bfs)으로 구현 풀이 과정: 이 문제는 욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보는..

문제 링크: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 유형: 브루트포스 알고리즘, 백트래킹, 다이나믹 프로그래밍 풀이 과정: 이 문제는 다이나믹 프로그래밍(DP)으로 풀 수도 있지만 아직 개념이 잡혀있지 않아 DFS를 이용해 풀어보았다. 특정한 수(n)가 주어지면 n을 1, 2, 3만을 이용해 표현해야하고 가능한 모든 경우의 수를 도출해내는 것이 목표다. 간단하게 DFS를 이용해 풀 수 있다. 더한 값(sum)이 구하는 값(num) 보다 크다면 return, 같다면 개수(count)에 1을 추가해주면 된다. 여기서 DFS 개념을 ..

문제 링크: https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 풀이 유형: 브루트포스 알고리즘, 백트래킹 풀이 과정: 이 문제는 전에 풀었던 연산자 끼워놓기의 반대 문제이다. 연산자 끼워놓기의 풀이는 다음 포스트를 참고하자. https://data-flower.tistory.com/72 [백준 14888번] 연산자 끼워넣기 - 파이썬 문제 링크: https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의..

문제 링크: https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 유형: 브루트포스 알고리즘, 백트래킹, 깊이 우선 탐색, 너비 우선 탐색 풀이 과정: 이 문제의 풀이 과정은 2가지가 있다. ★ 첫 번째 방법은 필자가 풀은 방법인 순열 라이브러리와 BFS를 이용한 방법이다. 먼저 연산자의 기호들을 차례대로 받아 순열을 이용해 가능한 모든 경우의 수를 계산하여 큐에 삽입한다. (예를 들어 '..

문제 링크: https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백준 14502번 연구소 문제는 삼성 SW 역량테스트 기출문제이다. 풀이 유형: 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 구현 풀이 과정: 이 문제는 벽을 3개 설치하는 모든 경우의 수를 다 계산해야 한다. 전체 맵의 크기가 최대 8 x 8이므로, 벽을 설치할 수 있는 최악의 경우 64C3이다. 이는 100,000보다 작은 수이므로, 모든 경우의 수를 고려해도 제한 시간..

문제 링크: https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 유형: 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제의 핵심 포인트는 모든 도로의 거리가 1이라는 점이다. 모든 간선의 비용이 동일할 때는 너비 우선 탐색(BFS)을 이용하여 최단 거리를 찾을 수 있다. 먼저 특정한 도시 X를 시작점으로 BFS를 수행하여 모든 도시까..