본문 바로가기
반응형

분류 전체보기424

C++ 프로그래머스 Lv2 요격 시스템 [C++] 프로그래머스 Lv2 요격 시스템 문제 설명A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다. A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다. A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에.. 2023. 9. 15.
C++ 프로그래머스 Lv1 달리기 경주 [C++] 프로그래머스 Lv1 달리기 경주 문제 설명 얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다. 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solut.. 2023. 9. 15.
C++ 자주 사용되는 문법 [C++] 자주 사용되는 문법 반복문 Forfor(초기식;조건식;증감식){ // 구현내용}초기식, 조건식, 증감식은 생략 가능생략 시 구현과정에서 빠져나올 수 있도록 해야한다. whilewhile(조건식){ // 구현 내용}조건식이 참일 경우 실행한다. do ~ whiledo{ // 구현 내용} while (조건식)조건식과 관계없이 최소 한 번은 실행 후 반복 조건을 검사한다.  선택switchswitch ( 기준값 ){ case 선택값: // 이 값일 때 구현 내용 break; case 선택값: // 이 값일 때 구현 내용 break; default: // 그 외 나머지}선택값을 차례대로 보면서 기준값에 해당하는 구현내용을 실행한다.break; 명령이 없을 경우 다음 case.. 2023. 9. 15.
Sort 퀵 정렬(Quick Sort) 알고리즘 [Sort] 퀵 정렬(Quick Sort) 알고리즘 퀵 정렬(Quick Sort) 알고리즘이란?찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 개발한 정렬 알고리즘이다다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하며, 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다.N개의 데이터를 정렬할 때, 최악의 경우에는 O(N^2)번의 비교를 수행하고, 평균적으로 O(N log N)번의 비교를 수행한다.매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다.퀵 정렬은 정렬을 위해 평균적으로 O(log N)만큼의 memory를 필요로한다. 최악의 경우 O(n)의 공간복잡도를 보인다.퀵 정렬.. 2023. 9. 14.
C++ BAEKJOON 2751번 : 수 정렬하기2 [C++] BAEKJOON 2751번 : 수 정렬하기2 백준온라인 2751번 수 정렬 문제 문제- N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력- 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.  - 둘째 줄부터 N개의 줄에는 수가 주어진다.  - 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다.  - 수는 중복되지 않는다.출력- 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입력 및 출력- input ex) 5 5 4 3 2 1 - output ex) 1 2 3 4 5 문제 풀이 입력 받는 수가 최대 1,000,000개로 크기가 크다. 저장 되는 영역(스택, 힙, 데이터)을 신경쓰도록한다.첫째 .. 2023. 9. 14.
Sort 병합 정렬(Merge Sort) 알고리즘 [Sort] 병합 정렬(Merge Sort) 알고리즘 병합정렬이란?병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 방식을 이용한다. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 병합하는 과정에서 재귀적으로 반복하며 풀어내는 것이 일반적이다.'존 폰 노이만(John von Neumann)'이 1945년에 개발데이터 분포도에 영향을 많이 받지 않아 시간복잡도가 O(NlogN)인 안정적인 정렬 방식에 속한다.두 개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 추가로 필요하다. 따라서 공간 복잡도는 O(N) 이다.다른 정렬 방법은 연결리스트에서 각 데이터.. 2023. 9. 13.
Sort 삽입 정렬(Insertion Sort) 알고리즘 [Sort] 삽입 정렬(Insertion Sort) 알고리즘 삽입 정렬은 두 번째 원소부터 시작하여 앞의 원소들을 비교하고, 삽입할 위치를 정한다. 삽입할 위치가 정해졌으면 대상 위치 부터 자신의 바로 앞 위치까지 있는 원소들을 한 칸씩 뒤로 옮겨 들어갈 자리를 만든 후 삽입해 정렬하는 알고리즘이다. 가나다 순으로 되어있는 책들 사이에 끼워 넣거나 순서대로 정렬할 필요가 있는 카드를 생각하면 이해가 쉽다. 아래는 삽입 정렬을 그림으로 표현한 것이다.1회차   - 2번째 원소 3을 Key로 두고 앞에 있는 5와 비교하고 자리를 바꾼다.2회차   - 3번째 원소 1을 Key로 설정하고 앞에있는 5와 3을 비교하고 뒤로 한 칸씩 밀어낸다.   - 비어있는 첫 번째 원소 자리에 1을 삽입한다.3회차   - 4번.. 2023. 9. 3.
의사 코드(Pseudo Code)(슈도 코드, 가짜 코드)란? 의사 코드(Pseudo Code)(슈도 코드, 가짜 코드)란? Pseudo(슈도, 수도)는 '가짜의', '모조의', '허위의', '의사의(비슷하여 분간하기 어려움)'의 뜻을 가지고 있다. 이처럼 의사 코드는 프로그램을 실제로 작성하기 전 실제 코드를 대략적으로 흉내내어 흐름을 파악하기 위한 용도로 작성한 코드를 말한다. 물론 이름의 뜻처럼 가짜 코드이기 때문에 실제 프로그래밍 툴에서 컴파일 되지 않는다. 자신이 이해하기 편한 자연어나 팀원들이 익숙한 언어를 모방하여 실행 가능성을 배제한 채 작성되었기 때문에 의사 코드라 한다. 예를 들어서 구구단을 출력하는 코드를 슈도코드로 작성하였을 때 다음과 같다. // 자연어에 익숙한 경우 반복 A는 2~9까지 반복 B는 2~9까지 출력 'A' * 'B' = A*B.. 2023. 9. 3.
Sort 버블 정렬(Bubble Sort) 알고리즘 [Sort] 버블 정렬(Bubble Sort) 알고리즘버블 정렬(Bubble Sort)이란 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 배열 A[N]이 있을 경우 배열의 원소 A[n]과 ~ A[n+1]을 순차적으로 비교하며 가장 큰 수를 맨 뒤로 이동하는 방법이다.가장 큰 자료가 맨 뒤로 이동하므로 맨 끝 원소는 검사 및 정렬에서 제외된다. 반복횟수마다 검사하는 원소가 줄어드는 이유이다. 5개의 원소 안에 {5, 3, 1, 4, 2} 의 원소가 들어가 있을 경우 버블 정렬은 아래 그림과 같다.1회차   - 5와 3을 비교 후 자리를 바꾼다.   - 5와 1을 비교 후 자리를 바꾼다.   - 5와 4를 비교 후 자리를 바꾼다.   - 5와 2를 비교 후 자리를 바꾼다.   - 마지막 자리수는 이.. 2023. 9. 3.
Sort 선택 정렬(Selection Sort) 알고리즘 [Sort] 선택 정렬(Selection Sort) 알고리즘 선택 정렬은 원리가 간단한 정렬 알고리즘 중 하나다.배열[A ··· n] 에서 가장 큰 원소를 마지막 원소와 자리를 바꾸거나, 가장 작은 원소를 제일 앞 원소와 자리를 바꾸는 것이다.자리 바꾸기가 완료되면 그 원소가 있는 자리는 신경쓰지 않아도 된다. 배열 { 3, 5, 1, 4, 2} 가 있을 때, 뒤에서 부터 오름차순 정렬하는 모습은 다음과 같다.*보통 프로그래밍 언어에서 인덱스는 0번 부터 시작한다.{ 3, 5, 1, 4, 2} 중 가장 큰 수 '5'를 찾는다. ('5'는 인덱스 1번에 있다.){ 3, 2, 1, 4, 5} '5'를 가장 뒤에 있는 '2'와 자리를 바꾼다. (1번 인덱스와 4번 인덱스 자리 바꿈){ 3, 2, 1, 4, 5.. 2023. 9. 2.
알고리즘(Algorithm)이란 알고리즘(Algorithm)이란 문제를 해결하기 위한 절차나 방법. 문제 해결 방법을 정의한 '일련의 단계적 절차'이자 어떠한 문제를 해결하기 위한 '동작들의 모임'이다. 컴퓨터가 따라 할 수 있도록 문제를 해결하는 절차나 방법을 자세히 설명하는 과정이다. 이를 자세히 설명하면 컴퓨터를 활용한 문제 해결 과정에서 주어진 문제를 해결하는 일련의 방법 또는 절차이며, 문제해결 방법을 순서대로, 절차대로 나열한 것이라고 볼 수 있다. 알고리즘의 유래 알고리즘은 9세기 페르시아(이란)의 과학자인 무함마드 이븐 무사 알-콰리즈미(al-Khwarizmi)의 이름을 라틴화한 단어이다. 그는 수학, 천문학, 지리학에 능통했으며, 많은 사람들이 그를 근대 수학의 아버지로 칭한다. 알고리즘(Algorithm)과 대수학(A.. 2023. 8. 30.
컴퓨팅적 사고 (Computational Thinking) 컴퓨팅적 사고 (Computational Thinking) 컴퓨팅적 사고란 란 단편적인 학습에서 벗어나 복합적 사고로 나가는 수단으로, 창의적 문제를 해결하는 핵심 능력으로 주목받고 있다. 컴퓨터의 해결 능력인 데이터 수집ㆍ분석, 표현, 문제 분해ㆍ추상화, 자동화 등을 사고에 적용시켜 여러 분야에서 문제 해결을 하는 데 사용한다. [네이버 지식백과] 컴퓨팅적 사고 (시사상식사전, pmg 지식엔진연구소) 컴퓨터(사람이나 기계)가 효과적으로 수행할 수 있도록 문제를 정의하고 그에 대한 답을 기술하는 것이 포함된 사고 과정 일체를 일컫는다. 정답이 하나가 아니라 여러가지일 수 있는 문제(Open-ended Problem)는 다양한 변수에 기반한 포괄적이며 유의미한 해답 도출이 필요한데, 컴퓨팅 사고를 통해서 .. 2023. 8. 29.
반응형

티스토리툴바