네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 풀이 과정 import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] q = deque() graph = [] for i in range(m): graph.append(list(..

1. 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 2. 풀이 과정 방법1) deque 라이브러리 활용하기 from collections import deque n, m = map(int, input().split()) miro = [list(map(int, input())) for _ in range(n)] dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] #BFS => 최단 거리 def bfs(graph): q = deque() q.append((..

1. 문제 https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 2. 풀이 과정 1~n까지의 합 = n(n+1)/2 이므로 n(n+1)/2 ≤ (입력값)을 만족하는 n의 최댓값을 구하면 된다. n(n+1)/2 ≤ (입력값) => n(n+1) ≤ 2*(입력값)이다.여기서 n(n+1)은 n*n < n(n+1) < (n+1)(n+1)을 만족한다. 모든 항에 루트를 씌우면, n < ${(n(n+1))}^.5$ < n+1이 된다. int형으로 바꾸면 소수점을 버리니 n을 반환할 수 있으며, ${(n(n+1))}^.5$ ≤ 2*(입력값)이므로 n+1을 반환할 수도 있다. 따라서..

1. 문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 2. 풀이 과정 방법1) (물건의 무게)/(로프의 수) ≤ (로프가 견딜 수 있는 무게) = (물건의 무게) ≤ (로프가 견딜 수 있는 무게)*(로프의 수) n = int(input()) rope = [int(input()) for _ in range(n)] rope.sort(reverse=True) result = 0 for i in range(n): #로프 최소 무게 * 개수

1. 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 2. 풀이 과정 주어진 식에서 빼기가 있다면 괄호를 묶어 뒤에 나오는 모든 수를 빼기 연산으로 만들 수 있다. 따라서 식의 값을 최소로 만드는 방법은 식에서 처음 나오는 빼기 뒤의 수들을 모두 뺄셈 연산을 수행해주면 된다. 예) 50+10-30+10+20-30+10 = 50+10-(30+10+20)-(30+10) 으로 묶어보면 분배 법칙을 통해 '-'를 다 적용해줄 수 있다. s ..

1. 문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 2. 풀이 과정 n, k = map(int, input().split()) cost = [int(input()) for i in range(n)][::-1] result = 0 for i in cost: result += k//i; k = k%i print(result)

1. Brute force 브루트 포스는 "완전 탐색 알고리즘"이다. 모든 경우를 다 살펴보고 결과를 도출하기 때문에 100% 정확도를 가진다. 모든 경우를 본다는 것은 해가 존재할 것이라 예상되는 영역 전체를 살펴보는 것으로 기본적인 방법은 아래와 같다. 1) 선형 구조 : 순차 탐색 탐색(Searching) 1. 탐색이란? 탐색은 '데이터를 찾는 방법'을 말한다. 여기서는 '어떻게 찾을까'와 '효율적인 탐색을 위해 어떤 방식으로 데이터를 저장할까'를 고민해야 한다. 정렬과 탐색은 정수를 기준으로 한 yerinpy73.tistory.com 2) 비선형 구조 : 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 그래프(Graph) 1. 그래프 그래프는 정점과 간선으로 구성되어 있다. 그래프는 방향성이 ..

1. 그래프 그래프는 정점과 간선으로 구성되어 있다. 그래프는 방향성이 없는 '무방향 그래프'와 방향성이 있는 '방향그래프'로 나눠볼 수 있다. '각각 정점에서 다른 모든 정점을 연결한 그래프'를 '완전 그래프'라고 하며 아래 두 그래프가 이에 해당한다. 2. 그래프 구현방법 1) 인접 행렬(adjacent matrix) 기반 그래프 2차원 배열을 이용한다. 2) 인접 리스트(adjacent list) 기반 그래프 연결 리스트를 활용하여 그래프를 표현한다. 3. 그래프의 탐색 1. 깊이 우선 탐색 (DFS : Depth First Search) 자신과 연결된 노드들 중 내용이 전달 안 된 하나를 먼저 선택해서 그 사람과 연결된 노드들에게 내용을 다 전달하면, 다음 하나를 또 선택한다. 백트래킹이라고도 하..

1. 테이블 저장되는 데이터가 key & value가 한 쌍을 이룬다. 키는 서로 다른 데이터를 구별하기 위해 사용되므로 중복되어서는 안 된다. #include typedef struct data{ int number; //사람의 고유번호 = key값 int name; //데이터 }Data; int main(void){ Data arr[100]; Data person; int n; //데이터 넣기 scanf("%d %d", &(person.number), &(person.name)); arr[person.number] = person; //데이터 찾기 printf("확인하고 싶은 사람의 고유번호 입력: "); scanf("%d", &n); person = arr[n]; printf("나이 %d, 이름 %..

1. 탐색이란? 탐색은 '데이터를 찾는 방법'을 말한다. 여기서는 '어떻게 찾을까'와 '효율적인 탐색을 위해 어떤 방식으로 데이터를 저장할까'를 고민해야 한다. 정렬과 탐색은 정수를 기준으로 한다. 탐색할 데이터의 종류가 무엇이든 탐색 자체의 알고리즘에 대해서만 집중하기 위함이다. 따라서 데이터는 아래와 같이 구성한다. typedef struct item{ int searchKey; Data searchData;//Data : 원하는 데이터 type 적으면 됨 }Item; 2. 순차 탐색 - 단순하게 배열 처음부터 내가 찾는 값이 있는지 살펴본다. - 정렬되지 않은 배열을 대상으로 함 - O(n) 3. 이진 탐색 - 배열의 중앙에 위치한 데이터와 비교해서 그 데이터보다 작으면 왼쪽 구역에서의 중앙값과 또..