세상을 바꾸는 데이터

문제 링크: https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 유형: 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 다이나믹 프로그래밍(DP)로 풀지 않고 딕셔너리를 이용한 bfs로 풀었다. bfs 대부분의 문제는 방문 표시를 가능한 전체 인덱스 수만큼 만들어서 해결하는데, 이 문제는 다르다. 이 문제는 현재 이모티콘의 개수와 클립보드에 있는 이모티콘 개수 2가지를 이용해 bfs로 풀어야 한다. 방문..

문제 링크: https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 숨바꼭질 문제를 응용한 문제로서 난이도가 조금 높아졌다. 기본 숨바꼭질 문제는 다음 링크를 참조하자. https://data-flower.tistory.com/78 [백준 1697번] 숨바꼭질 - 파이썬 문제 링크: https://www.acmicpc.net/problem..

문제 링크: https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 1차원상의 좌표에서 수빈이가 동생을 만나기 위한 최소 시간을 도출하는 것이다. 먼저 모든 좌표(100000개)를 0으로 초기화한 리스트를 만든다. 여기에 BFS를 실행하여 특정 위치를 방문하면, 방문한 시간을 표시해준다. deque을 이용해 큐를 사용하여 풀어보자. 풀이 코드: ..

문제 링크: 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/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 유형: 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 너비 우선 탐색(BFS)을 이용하여 해결할 수 있다. 이 문제의 포인트는 바이러스가 낮은 번호부터 증식한다는 점이다. 이는 정렬을 이용하자. 낮은 번호부터 증식하므로, 초기에 큐에 원소를 삽입할 때는 낮은 바이러스의 번호부터 삽입한다. 이후에 BFS를 수행하여 방문하지..

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