본문 바로가기

분류 전체보기411

[C++] 백준 15650번 : N과 M (2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 이전 문제와 다른 점이 고른 수열이 오름차순이기 때문에 구현한 DFS에 추가적인 조건을 넣는다. 조건(1) : 벡터 v의 사이즈가 0이면 비교 없이 그냥 바로 값을 대입한다. 조건(2) : v의 사이즈가 0이 아니면 이전 값과 추가할 값을 비교해서 값을 대입한다. 이전 idx의 값이 추가할 값보다 크다면 다음으로 넘어간다. 느낀점 더 나은 코드의 구현을 위해서 다른 분들의 코드를 검색.. 2021. 5. 23.
[C++] 백준 15649번 : N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 1. 1부터 N까지 자연수 중 중복 없이 M개 고른 수열을 구현하기 위해 visited 배열을 이용해 중복의 여부를 체크한다. 2. dfs함수를 이용해서 모든 경우를 확인한다. DFS (Depth-First Search) : 깊이 우선 탐색 Root 노드에서 다음 branch로 넘어가기 전에 해당 분기를 완벽하게 탐사하는 방법 - 모든 노드를 확인할 때 유용 어떤 노드를 방문했는지 체.. 2021. 5. 22.
[C] 백준 18870번 : 좌표 압축 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 풀이 1. 값들을 n회 입력받는다. 일반 배열과 정렬시킬 배열을 위해 또 다른 배열에 같이 저장한다. 이 때, 정렬된 배열은 나중에 값을 비교하는데 쓰인다. 2. qsort를 통해서 배열을 정렬하고 unique로 다시 재정렬 및 인덱스를 리턴한다. 3. 일반 배열(arr)과 중복 없이 정렬된 배열(sort)을 비교하여 일반 배열의 값들이 몇번.. 2021. 5. 21.
[C] 백준 10814번 : 나이순 정렬 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 문제 접근 1. 구조체를 정의한다. 구조체는 파이썬의 dictionary와 비슷한 타입으로 만든다. 2. 합병정렬을 이용한다. 이 때, 나이만 비교하는데 나이가 같다면 앞에 오는 순서를 그대로 이어 받는다. 느낀점 계속된 합병정렬을 응용하는 문제이다. 이전의 문제와 다른 점이라면 stable sort 와 in-place sort의 개념을 잡은 계기가 되었다는 점이다. stable sort : 중복된 값.. 2021. 5. 18.
[C] 백준 1181번 : 단어 정렬 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 접근 1. 구조체를 정의해서 입력받는 단어들의 스펠링과 길이를 배열에 저장한다. 2. 합병정렬을 이용해 배열을 정렬한다. 3. 정렬된 배열들을 출력할 때 다음에 오는 단어와 같다면 출력하지 않는다. 느낀점 정렬 파트의 문제이다 보니까 합병정렬과 셸 정렬에 대해서 확실하게 구현할 수 있게 되었다. 사실상 이전 문제와 크게 다를게 없다고 생각했다. 하지만 String에 대한 복습이 확.. 2021. 5. 17.
[C] 백준 11651번 : 좌표 정렬하기2 https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 문제 접근 https://codinghejow.tistory.com/30 동일하다. 느낀점 사실 이전 문제에서 아주 조금만 수정하면 되는 코드이다. 코드 #include typedef struct { int x; int y; }point; point arr[100001]; point sorted[100001]; void merge(point.. 2021. 5. 16.

티스토리툴바