https://husk321.tistory.com/363 [C++] C++ sort는 어떤 알고리즘을 사용할까 서론 '리스트는 어떤 정렬 알고리즘을 사용하나요?' 사실 algorithm 헤더에 있는 sort는 어떤 알고리즘을 사용하는가에 대한 이야기는 많이 있었습니다. 그런데 리스트의 경우 리스트 내부 함수로 so husk321.tistory.com 2개의 원소를 비교하는 정렬 stl이용하기 https://stormpy.tistory.com/344 [C++] List 에서 pair로 된 데이터 찾기 list를 사용하다가 두 개의 데이터를 담아야 해서 pair를 사용했다. 찾을 때는 통상 first로 찾았는데, 이는 사실 map을 이용하는 편이 훨씬 편하다. list에서 pair를 사용하여 둘 다 만족하는..

1. 개념 간단한 순열과 조합은 기본적인 조건문과 반복문으로 출력할 수 있다. N개의 숫자 중에서 M개를 뽑아 순열, 조합하는 경우를 구해보자. 예를 들어 1~5까지 숫자 중에서 2개를 순열, 중복순열, 조합, 중복조합으로 뽑는다고 해보자. 참고로, 순열은 순서의 개념이 포함되므로 모든 숫자들을 나열하는 경우이고, 조합은 순서의 개념이 없으므로 출력되는 숫자들은 오름차순, 중복조합의 경우 비내림차순이 된다. 2. 구현 코드로 보면 다음과 같다. 순열(P) //순열 #include using namespace std; int check[6]; int main(void) { //ex) P(5, 3) for (int i = 1; i

1. 문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 중복을 허락하여 해당 동전을 만들 수 있는 경우이므로 자연수 분할, 즉 중복 조합문제이다. 2. 풀이 아이디어(시행착오) 동전 n개로 k원을 만들 수 있는경우의 수를 구하는 문제이다. 언뜻 보기엔 일반적인 DFS로 재귀를 이용한 top - down방식으로 풀 생각이 들 수 있다. 예들 들어 1, 2원짜리 동전을 가지고 4원을 만드는 경우 3원(4 - 1원)에 1원을 더한 것과 2원(4 -..

1. 문제 https://www.acmicpc.net/problem/28323 28323번: 불안정한 수열 $N$개의 자연수가 좌우 일렬로 놓여 있다. 왼쪽에서 $i$ ($1 \le i \le N$)번째에 놓여 있는 자연수는 $A_i$다. 여러분은 이 중 몇 개의 자연수를 원하는 만큼 고를 수 있다. 단, 아무 자연수도 고르지 않 www.acmicpc.net 2023년 정보올림피아드 초등부 1번 문제이다. 2. 풀이 문제에서 정의한 불안정안 수열이란 이웃한 두 숫자의 합이 모두 홀수인 수열을 말한다. 자연수의 배열이 주어졌을 때 최대 몇개의 숫자로 불안정한 수열을 만들 수 있는지 구하는 문제이다. 불안정한(이웃한 두 수의 합이 모두 홀수인) 수열을 만들려면 수열을 탐색하며 이웃한 두 수의 합이 짝수가 되..

1. 문제 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 num[i]; lottery(0, 0); cout

1. 괄호쌍의 유효성 괄호쌍의 유효성이란 열린괄호' ( '와 닫힌 괄호' ) '가 서로 순서와 짝이 맞게 이루어져있는지 판단해주는 방법이다. 일반적으로 괄호쌍을 다룰 때에 소괄호' ( '가 주로 판단대상이지만 중괄호' { '나 대괄호' [ '로 확장하여 판단하기도 한다. 괄호쌍이 유효한 경우 ( ) ( ( ) ) ( [ ] ) 괄호쌍이 유효하지 않은 경우 ) ( { ( } ) { } ) 2. stack을 이용한 괄호쌍 유효성 검사하기 알고리즘 그러면 어떻게 이를 판단할 수 있을까? 위에서 괄호쌍이 유요하지 않은 경우는 괄호의 짝이나 순서 또는 개수가 맞지 않는다는 것을 확인할 수 있다. 데이터가 입력되었을 때 현재까지 입력된 상태를 유지하고 제일 마지막에 입력된 값과 비교해야 함을 느낄 수 있다. 따라서..

BFS와 DFS의 관계 인접행렬 형태의 BFS 문제 입니다. 이 문제는 DFS로는 해결되지 않습니다. 꼭 BFS로 해결해야 합니다. 모든 DFS 문제는 BFS로 해결할 수 있습니다. 하지만 BFS문제는 DFS로 해결하지 못하는 경우도 있습니다. 바로 이 문제처럼 최소의 칸 수를 출력해야 하는 문제가 그렇습니다.