반응형 알고리즘12 [알고리즘c++] 삽입 정렬(Insertion Sort) 삽입 정렬 요약 카드를 정렬하는 방법과 유사하다 새로운 카드를 기존의 정렬된 카드 사이 올바른 자리를 찾아서 삽입하는 방식이다. 새로 삽입될 카드의 수 만큼 반복하여 정렬 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하며, 자신의 위치를 찾아서 삽입하여 정렬을 완성하는 알고리즘 매 순서 마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다. 삽입 정렬 알고리즘 두 번째 자료부터 시작하여 앞의 자료들과 비교하여 삽입할 위치를 지정한 후 삽입 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기.. 2022. 11. 21. c++ 백준 9086 문자열 문자열 알고리즘 분류 구현 문자열 https://www.acmicpc.net/problem/9086 9086번: 문자열 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 한 줄에 하나의 문자열이 주어진다. 문자열은 알파벳 A~Z 대문자로 이루어지며 알파벳 사이에 공백은 없으 www.acmicpc.net 문제 문자열을 입력으로 주면 문자열의 첫 글자와 마지막 글자를 출력하는 프로그램을 작성하시오. 입력 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 한 줄에 하나의 문자열이 주어진다. 문자열은 알파벳 A~Z 대문자로 이루어지며 알파벳 사이에 공백은 없으며 문자열의 길이는 1000보다 작다. 출력 각 테스트 케이스.. 2022. 9. 25. c++ 백준 10178 할로윈의 사탕 할로윈의 사탕 알고리즘 분류 수학 사칙연산 https://www.acmicpc.net/problem/10178 10178번: 할로윈의 사탕 할로윈데이에 한신이네는 아부지가 사탕을 나눠주신다. 하지만 한신이의 형제들은 서로 사이가 좋지않아 서른이 넘어서도 사탕을 공정하게 나누어 주지 않으면 서로 싸움이 난다. 매년 할로윈 www.acmicpc.net 문제 할로윈데이에 한신이네는 아부지가 사탕을 나눠주신다. 하지만 한신이의 형제들은 서로 사이가 좋지않아 서른이 넘어서도 사탕을 공정하게 나누어 주지 않으면 서로 싸움이 난다. 매년 할로윈데이때마다 아부지는 사탕을 자식들에게 최대한 많은 사탕을 나누어 주시기 원하며 자신에게는 몇개가 남게되는지에 알고 싶어 하신다. 이런 아부지를 도와서 형제간의 싸움을 막아보자... 2022. 9. 24. 백준 10250 ACM 호텔 언어 : C++ 문제 https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 풀이 회고 쉬운 문제임에도 불구하고 너무 쉽게 가려하다가 실수를 했다. 급할수록 돌아가라는 말도 있는것처럼 너무 빨리가려고 하면 오히려 실수를 유발할 수 있다. 앞으로는 돌다리도 두들겨 보고 건너는 습관을 들여야겠다. 2022. 7. 13. 백준 11866 요세푸스 문제 0 문제 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 풀이 회고 큐를 활용한 알고리즘으로 문제를 해결 하였고 처음 제출 했을때는 K가 1일때를 고려 안해주고 또 i % K ==0이 아니라 i == K일때로 해주어 시간 초과가 나왔었다. K가 1일때는 고려하고 조건문을 수정하니 정답이 되었다. 알고리즘을 해결했다고 생각하고 섣부르게 제출했다가 종종 시간 초과나 확인 못한 조건 때문에 오답처리 되곤 하는데 그 점을 주의 하면서 차분하게 문제 푸는 습관을 들여야겠다. 2022. 7. 12. 백준 10828 문제 링크 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 이 문제는 stack을 구현하는 문제로 stack을 구현하기 위해 vector를 사용하였다. int 형 변수를 선언해 명령의 수를 입력 받았고 vector를 선언해 스택을 관리하였다. 회고 c언어 자료구조에서 배웠던 stack을 c++에서 vector를 사용해 구현해보니까 스택의 동작 원리를 안다면 누구나 쉽게 풀 수 있는 문제였다. 혹시나 하는 마음에 자료구조를 이제.. 2022. 7. 9. 백준 10989 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 구현 언어 : c++ 입력: 출력: 카운팅 정렬을 활용해서 정렬이 잘 된것을 확인 할 수 있다. 2022. 7. 8. 백준 1225 https://www.acmicpc.net/problem/1225 1225번: 이상한 곱셈 첫째 줄에 A와 B가 주어진다. 주어지는 두 수는 모두 10,000자리를 넘지 않는 음이 아닌 정수이다. 수가 0인 경우에는 0만 주어지며, 그 외의 경우 수는 0으로 시작하지 않는다. www.acmicpc.net 풀이 2022. 7. 6. 백준 2460 https://www.acmicpc.net/problem/2460 2460번: 지능형 기차 2 최근에 개발된 지능형 기차가 1번역(출발역)부터 10번역(종착역)까지 10개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. www.acmicpc.net 풀이 2022. 6. 23. 백준 2455 https://www.acmicpc.net/problem/2455 2455번: 지능형 기차 최근에 개발된 지능형 기차가 1번역(출발역)부터 4번역(종착역)까지 4개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. www.acmicpc.net 풀이 2022. 6. 23. 자료 구조 자료 구조 자료구조란 무엇인가? 자료구조 : 프로그램이란 데이터를 표현 및 저장하는 것이다. 알고리즘 : 표현된 데이터를 처리하는 것이다. -알고리즘은 자료 구조에 의존적이다. 자료구조 분류 선형 자료구조 : 리스트, 스택, 큐 비선형 자료구조 : 트리, 그래프 알고리즘의 성능분석 방법 시간 복잡도 : 얼마나 빠른지를 비교 공간 복잡도 : 얼마나 메모리를 적게 쓰는지 비교 *빅-오 표기법 : 데이터의 수의 증가에 따른 연산횟수의 증가 형태를 표현한 것 대표적인 빅오 -O(1) 상수형 빅-오 -O(log n) 로그형 빅-오 -O(n) 선형 빅-오 -O(nlog n) 선형로그형 빅-오 -O(n^2) 데이터의 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘 -O(n^3) 데이터의 수의 세제곱에 해당하는 연산.. 2022. 5. 29. 백준 1181 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 2022. 5. 24. 이전 1 다음 반응형
