분류 전체보기

문제 : https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 어떤 문제인가? 문제는 특별히 어렵지 않았다. N x N 표에 있는 숫자들 중 N번째로 큰 수를 출력하면 끝이다. 접근 방법 처음에는 문제의 메모리 제한과 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 조건 때문에 표의 일부분만 뽑은 그룹에서 N번째 큰 수를 찾으려고 했다. 그렇게 벡터를 사용해서 구현을 했고 테스트케이스는 통과해서 제출했지만 오답이었다. int n; cin >> n; int..

문제 : https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 어떤 문제인가? 요구사항은 간단하다. 1. 책의 개수 N이 주어진다 -> N번 입력을 받는다. 2. 입력받은 책의 이름과 판매 수량을 저장한다. 3. 가장 많이 팔린 책의 제목을 출력한다. 접근 방법 먼저 책의 이름과 판매 수량을 저장할 자료구조가 필요했다. vector book; 큰 고민 없이 pair와 vector를 사용해 책의 이름, 판매수량을 저장할 수 있었다. string..

스택이란? 스택은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 스택은 입구와 출구가 같은 선형 구조이다. 따라서 가장 먼저 입구에 들어간 자료가 가장 늦게 출구로 나갈 수 있다. 프링글스 통을 생각하면 이해가 쉽다. 처음 프링글스 통이 채워질 때 가장 먼저 들어간 프링글스가 가장 마지막에 우리들의 손에 집혀 입으로 들어온다. 이를 후입 선출(또는 LIFO, last in first out) 구조라고 한다. 스택에서의 접근은 항상 마지막 원소에서만 일어난다. => 제일 위에 있는 프링글스를 잡는다. 이 마지막 원소를 top이라고 한다. 스택의 탐색 앞서 포스팅한 배열과 연결 리스트가 자료구조를 구현하는 기본적인 방법이다. 보통 스택의 탐색을 top함수라고 한..

문제 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 어떠한 그래프에 대한 깊이 우선 탐색과 너비 우선 탐색 결과를 각각 출력하면 되는 문제이다. 주의해야 할 점은 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문한다는 것이다. 따라서 그래프를 sort함수를 통해 오름차순으로 정렬해줘야 한다. 입력받은 v부터 dfs를 실행한 결과를 출력하고 그래프를 다시 초기 상태로 돌려놔 bfs..

문제 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 깊이 우선 탐색 알고리즘을 사용하면 아주 쉽게 풀 수 있는 문제다. 1번 컴퓨터와 연결된 컴퓨터에 대해서만 탐색을 하면 된다. #include #include using namespace std; bool visited[101]; vector graph[101]; int cnt=0; void dfs(int x){ cnt++; visited[x]=true; for(int i : graph[x])..

문제 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 금액의 최소 화폐 개수를 세는 문제인 5585번과는 약간 다르다. 5585번은 일단 모든 화폐가 서로 배수이고 약수인 관계이기 때문에 무작정 나눠도 되지만, 이 문제 같은 경우는 설탕을 서로 배수나 약수가 아닌 5kg, 3kg으로 정확히 나눠야 한다. 그리디 알고리즘을 통해 설탕을 가장 적은 개수의 봉지로 배달하려면 3kg보다 5kg으로 나누어 떨어지는 것이 좋다. 따라서, 입력받은 설탕의 무게가 ..

문제 : https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 아주 기초적이고 대표적인 그리디 알고리즘의 예시 #include using namespace std; int coin[] = {500, 100 ,50, 10, 5, 1}; int main(){ int money; cin >> money; int realMoney = 1000 - money; int cnt=0; for(int i=0; i

문제 : https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 로프들이 병렬로 연결되어 무게를 들 때 로프들 중 가장 작은 무게를 들 수 있는 로프가 들 수 있는 무게가 병렬로 연결된 로프들이 각각 들어야 할 무게가 되는 것이 핵심이다. 1. 로프들이 들 수 있는 무게의 정보를 저장할 벡터 rope를 선언하고 문제의 요구에 맞게 입력을 받는다. 2. rope를 sort함수를 사용해 내림차순으로 정렬해준다. 3. 병렬로 연결된 로프들이 들어 ..

이번 포스팅에선 배열 (Array)에 대해 살펴볼 것이다. 저번 포스팅에서 필요할 때마다 메모리를 할당받아 데이터를 저장하는 방법인 연결 리스트(Linked List)를 다뤘으니 이번 포스팅에선 미리 메모리를 확보한 다음 연속된 공간에 저장하는 방법인 배열에 대해 알아보자. 배열은 자료구조를 배우기 이전에도 컴퓨터 과학을 공부했다면 다 들어봤을 만한 기초적이고 중요한 것이다. 배열이란? 배열(array)은 같은 타입의 변수들로 이루어진 유한 집합으로 정의된다. 배열을 구성하는 각각의 값을 배열 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 한다. 배열은 같은 종류의 데이터를 많이 다뤄야 하는 경우에 사용할 수 있는 가장 기본적인 자료구조이다. 배열의 탐색 배열은..

이번 포스팅에선 연결 리스트(Linked List)에 대해 살펴볼 것이다. 먼저 데이터를 삽입하는 방법은 두 가지가 있다. 1. 필요할때마다 메모리를 할당받아 데이터를 저장하는 방법. 2. 미리 메모리를 확보한 다음 연속된 공간에 저장하는 방법. 여기서 1번이 연결리스트의 데이터 삽입 방식이다. 연결 리스트는 낭비되는 데이터는 없지만 연관된 데이터끼리 연결 짓는 것이 필수적이고 중요하다. 연결 리스트란? 연결 리스트는 두 개의 필드로 이루어진 node가 기본 단위이다. node는 데이터를 저장하는 데이터 필드와 다음 노드를 가리키는 링크 필드로 구성된다. node는 서로 다른 데이터 타입을 하나로 묶으므로 class에 해당된다. 따라서 링크필드에 해당하는 것은 class 포인터이다. 이를 노드형 포인터라..