본문 바로가기
728x90

분류 전체보기230

BOJ(c++) / 백준 2146 : 다리 만들기 백준 2146 : 다리 만들기 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 문제 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 위의 그림에서 색.. 2021. 10. 26.
BOJ(C++) / 백준 16234 : 인구 이동 백준 16234 : 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 .. 2021. 10. 26.
정렬 알고리즘(C++) / 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 알고리즘이다. k번째 반복 후의 결과 배열은 앞쪽 k+1 항목이 정렬된 상태이다. 두번째 인덱스부터 시작하여 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 선택 정렬과 유사하지만 더 효율적인 정렬 알고리즘이다. 시간 복잡도 & 공간 복잡도 시간 복잡도 : O(n^2) 공간 복잡도 : O(n) 최선의 경우 O(n)이라는 시간 복잡도를 가지지만 최악의 기준으로는 O(n^2)의 복잡도를 가진다. 최선의 경우는 대부분의 원소가 이미 정렬되어 있는 경우를 말한다. 안정 정렬이다. 버블 정렬이나 선택 정렬과 같은 시간 복잡도를 가지.. 2021. 10. 22.
정렬알고리즘(C++) / 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort) 버블정렬은 가장 쉽고 코드가 단순한 정렬 알고리즘이다. 두 값을 비교하여 정렬하며 이동한다. 하지만 시간복잡도가 느려 실제로는 잘 사용되지 않는다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블 정렬이란 이름이 붙여졌다. 양방향으로 번갈아 수행하면 칵테일 정렬이다. 시간 복잡도 & 공간 복잡도 시간 복잡도 : O(n^2) 공간 복잡도 : O(n) 코드(C++) - 백준 2750 /2750 버블정렬 #include using namespace std; int main() { //입력 int N; cin >> N; int arr[1001]; int num; for (int i = 0; i > num; arr[i] = n.. 2021. 10. 22.
정렬알고리즘(C++) / 선택정렬(Selection Sort) 선택 정렬(Selection Sort) 선택 정렬은 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 해당 순서 뒤에 주어진 리스트 중에 최솟값을 찾아 해당 해당 순서에 위치한 값과 교체한다. 애니메이션으로 선택 정렬 알고리즘을 쉽게 이해할 수 있다. 시간 복잡도 & 공간 복잡도 시간 복잡도 : O(n^2) 공간 복잡도 : O(n) 장점 버블 정렬(bubble sort)과 마찬가지로 알고리즘이 단순하다. 정렬을 위한 비교 횟수는 많지만, 버블 정렬에 비해 실제로 교환하는 횟수가 적으므로 버블 정렬보다 항상 우수하다. 배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. 제자리 정렬이다. 단점 탐색 횟수가 많고 시간 복잡도가 크다. 불안정 정렬이다. (불안정 정렬 : 정렬 후 원래의 순서.. 2021. 10. 22.
BOJ(C++) / 백준 2468 : 안전 영역 백준 2468 : 안전 영역 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 코드 //c++스터디 1주차(BFS/DFS) 2468 안전 영역 #include #include #include #include #include using namespace std; int N = 0; int board[101][101] = { 0, }; int visited[101][101] = { 0, }; int next_i[4] = { 1,0,-1,0 }, next_j.. 2021. 10. 22.
BOJ(C++) / 백준 1956 : 운동 백준 1956 : 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제 V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자. 당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다... 2021. 10. 21.
BOJ(C++) / 백준 2776 : 암기왕 백준 2776 : 암기왕 https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 문제 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정.. 2021. 10. 20.
BOJ(C++) / 백준 2670 : 연속부분최대곱 백준 2670 : 연속 부분 최대곱 https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 문제 N개의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면, 색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다. 입력 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그다음 줄부터 N개의 수가 한 줄에 하나씩 들.. 2021. 10. 18.
BOJ(C++) / 백준 16401 : 과자 나눠주기 백준 16401 : 과자 나눠주기 https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN www.acmicpc.net 문제 명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다. 조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다. 그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리.. 2021. 10. 14.
BOJ(C++) / 백준 2458 : 키 순서 백준 2458 : 키 순서 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생.. 2021. 10. 10.
BOJ(C++) / 백준 2457 : 공주님의 정원 백준 2457 : 공주님의 정원 https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 문제 오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다. 총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있.. 2021. 10. 10.

티스토리툴바