본문 바로가기

알고리즘

 (82)
[백준] 2108번 통계학 C++ 문제풀이 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 풀이 이 문제 풀 때 어려웠던 점은 산술평균과 최빈값을 구하는 과정이었던 것 같다. 산술 평균의 경우에는 float로 바꾼 후 연산하고 cmath의 round를 이용해 값을 구했다. 최빈값 같은 경우에는 숫자가 나온 횟수를 저장하는 cnt배열을 만들어 숫자를 저장한 후 값들을 비교해 최빈값을 구했다. 소스 코드 #include #include #include #include using namespace s..
[백준] 1339번 단어 수학 C++ 문제풀이 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제 풀이 맨 처음에는 자릿수마다의 알파벳을 저장해 완탐형식으로 하려 했는데 잘되지 않았다. 그래서 알파벳 별로 자릿수들의 합을 이용해 문제를 해결했다 예를 들어 1번 예시인 AAA, AAA 인 경우에는 alpha[0] = 222가 들어가는 형식이다. 아무튼 이런 방법으로 합이 큰 값들부터 정렬해서 9부터 차례로 곱해주었다. 소스코드 #include #include #include #incl..
[백준] 9663번 N-Queen C++ 문제풀이 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 백트래킹을 이용해 문제를 해결했다. Promising 이란 함수를 만들어서 체스판에 놓여진 위치가 유망한지 아닌지를 판단했다. Promising에서는 같은 column인지, 같은 대각에 있는지를 확인했다 같은 행인것을 확인 안 한 것은 행마다 하나의 Queen을 놓는 식으로 코드를 작성해 같은 행인지에 대해서는 확인할 필요가 없다. 알고리즘 수업때 배운 내용이여서 큰 문제 없이 코드를 작성했다. 소스코..
[백준] 1713번 후보 추천하기 C++ 문제풀이 https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 문제 풀이 추천인을 담은 배열과 추천수를 저장하는 배열을 만든 후, 추천인을 담은 배열의 크기가 N보다 커지면 추천수 배열을 검색해 추천수가 가장 적은 학생을 제거하는 방식으로 코드를 작성했다. 사실 이런식으로 푸는게 맞나 싶다 ㅋㅋ... 소스코드 #include #include #include using namespace std; vector rec; // 추천인을 담은 배열 int r..
[백준] 3055번 탈출 C++ 문제풀이 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 풀이 DFS를 자료구조 Queue를 이용해 구현했다. '고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다'는 조건을 고려해 -> 물을 먼저 이동한 후 고슴도치를 이동시켰다. 따라서 위를 위해 2가지의 Queue를 만들었는데, 하나는 물 좌표 큐이고 하나는 고슴도치 좌표를 저장한 큐이다. "."인 곳에 대해서만 이동할 수 있는 걸로 코드를 작성했다. 소스코드 #include #include ; #inclu..
[백준] 3425번 고스택 C++ 문제풀이 https://www.acmicpc.net/problem/3425 문제 풀이 몇가지 문제의 주의점을 설정하고 문제를 풀었다. 1) 모든 수행이 종료됐을 때 스택에 저장되어 있는 숫자가 1개가 아니라면, "ERROR"를 출력 -> cnt라는 변수를 통해 해결 2) DIV와 MOD계산에서 +와 - 부호를 잘 확인 -> 첫 번째, 두 번째 숫자의 부호를 확인 3) 연산 시 배열의 크기를 주의 4) 조건에 맞지 않으면 바로 중단 후 "ERROR"출력 구현 문제인 만큼 코드가 너무 길다. 처음에는 int를 이용해 풀었는데, IntegerOverflow 에러가 나와서 long long을 이용해 문제를 해결했다. 소스코드 #include #include #include using namespace std; typed..
[백준] 1920번 수 찾기 C++ 문제 풀이 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 풀이 처음에는 algorithm의 sort()랑 find()를 이용해 답을 구하려 했는데 역시나 시간초과가 나왔다. sort() 와 BinarySearch를 이용해서 풀려고 했는데 또 시간초과가 나왔다. 결국 MergeSort와 BinarySearch를 직접 구현해 문제를 해결하였다. 소스코드 #include #include #include u..
[백준] 2164번 카드2 C++ 문제 풀이 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 풀이 자료구조 Queue를 이용해서 해결했다. 한 번의 반복에서 하나의 값은 바로 pop해주고, 다음 값은 push를 해준 후 pop을 했다. 소스코드 #include #include using namespace std; queue que; int main() { int N; cin >> N; for (int i = 1; i 1) { que.pop(); que.push(que.front())..

티스토리툴바