Algorithm
-
[백준] [5585번] 거스름돈(C++)Algorithm/C++ 2020. 11. 10. 23:34
www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include using namespace std; int main() { int N; cin >> N; N = 1000 - N; int coin[10] = { 500, 100, 50, 10, 5, 1 }; int cnt = 0; for (int i = 0; i..
-
[백준][2667] 단지번호붙이기 (C++)Algorithm/C++ 2020. 1. 30. 20:06
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include #include #include using namespace std; int N, cnt;bool map[26][26], visit[26][26];int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};vector numOfhome; typedef struct{ int x, y;} pos;void bfs(int a, int b){ visit[a][b] = 1; // 방문 표시 cnt++; // 단지수 +1 int CntOfHome = 0;..
-
[백준][2178] 미로탐색 (C++)Algorithm/C++ 2020. 1. 20. 14:16
더보기 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS를 이용해 푼 미로탐색 문제입니다. BFS로 풀어야한다는 문제인 걸 알고 풀었지만 실제 코딩테스트에서는 어떤 방법으로 풀어야 하는 지 스스로 알아내야 하기 때문에 코딩테스트에서 이렇게 문제가 나왔을 때 쉽게 풀 수 있을지는 잘 모르겠네요.. 유형마다 반복 연습을 해서 딱 보면 어떻게 풀어야 하는지 알 수 있을 때까지 계속 연습해야 할 것 같습니다. 미로 탐색 성공 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 ..
-
[정렬] 기본 정렬 알고리즘 정리 (Python)Algorithm/파이썬 2020. 1. 14. 00:09
정렬 알고리즘은 주어진 리스트나 배열에서 사용자가 지정한 기준에 따라 정렬하는 알고리즘을 말한다. 알고리즘에 따라 O(N^2) 또는 O(NlogN) 으로 시간복잡도가 다양하다. 1. 선택 정렬 말 그대로 해당하는 값을 선택해서 맨 앞의 값과 위치를 바꿔주는 정렬이다. 오름차순으로 정렬할지 내림차순으로 정렬할 지에 따라 최소선택정렬(Min-Selection Sort)와 최대선택정렬(Max-Selection Sort)로 나뉘어진다. @ 알고리즘 구성 (최소선택정렬) 1) 정렬되지 않은 리스트의 맨 처음부터 가장 작은 값을 찾아준다. 2) 가장 작은 값을 찾은 뒤 맨 앞의 인덱스와 위치를 바꿔준다. 3) 다음 인덱스부터 1), 2)를 반복한다. 1 2 3 4 5 6 7 8 def selection_sort(a..
-
[백준][1920] 수 찾기 (Python)Algorithm/파이썬 2020. 1. 11. 16:29
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다. www.acmicpc.net C++로만 알고리즘을 공부하다가 이번 방학엔 파이썬 공부도 할 겸 알고리즘 기초 단계부터 시작할 계획입니다. C++ 위주로 알고리즘 공부를 했다보니 입력받는 거랑 타입 같은 게 많이 헷갈리네요. input() 함수는 str 타입으로 입력되기 때문에 꼭 int(input())으로 받아줘야 에..
-
[백준][1697] 숨바꼭질 (C++)Algorithm/C++ 2020. 1. 11. 06:12
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 예전에 푼 문제를 다시 풀어본건데 메인 함수에서 하는 것 보다는 함수를 따로 선언하는 것이 메모리와 시간을 덜 잡아먹는 것 같습니다. 또 ..
-
[백준][1260] DFS와 BFS (C++)Algorithm/C++ 2020. 1. 10. 19:55
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net 개인적으로 제일 어려워하는 종류인 BFS/DFS를 새로 공부하자는 의미에서 기본문제부터 다시 풀어봤습니다. 처음 알고리즘 공부 시작할 때는 기본 문제조차도 다른 사람의 풀이를 보지 않으면 풀지 못했는데 이제는 이 정도 문제는 따로 풀이를 보지 않아도 풀 수 있는 정도는 된 것 같아 조금..