본문 바로가기

알고리즘

 (43)
백준 알고리즘 중급 - 브루트 포스(문제2) * 숫자 재배치 (low) : 두 정수 a, b가 주어지고 a에 포함된 숫자를 섞어서 새로운 수 c를 만든다고 할 때 b보다 작거나 같으면서 가장 큰 c값을 구하는 문제다. www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보� www.acmicpc.net #include #include #include using namespace std; int main() { string a; int b; int ans = -1; cin >> a >> b; sort(a.begin(), ..
[삼성 SW 역량 테스트 기출] 뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net - Dummy라는 도스 게임이라고 한다. 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀이 늘어난다. 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. - 맵은 N*N (2 n >> k; int x, y; for (int i = 0; i > x >> y; map[x][y] = true; } cin >> l; int s; char d; for (int i = 0; i > s >> d; dir...
[삼성 SW 역량 테스트 기출] 2048(Easy) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net - 이것도 강의 들으면서 풀었던 문제인데, 한번 더 풀어봤다. 확실히 모범 답안을 보고 정리하고 넘어가면 직접 짠 게 아니라 기억에 많이 남지가 않는다. 처음부터 차근차근 짜면서 복습하고 넘어갈 수 있는 기회였다. - - 보드의 크기는 N*N이고 N은 20이하의 자연수다. 그리 큰 수가 아니니 오버를 걱정할 필요는 없겠다. - 주요 규칙을 정리하면, 한번 이동할 때 전체 블록을 상,하,좌,우 중 하나로 전부 이동시킨다. 같은 값을 갖는..
[삼성 SW 역량 테스트 기출] 구슬 탈출 2 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net - 강의 들으면서 풀었던 문제인데, 풀이가 너무 복잡해서 이해를 제대로 못 하고 넘어갔다. 이걸 시작으로 여기저기서 찾아볼 수 있는 코딩 테스트 기출 문제를 하루에 1~2개씩 풀어볼까 한다. - - 세로, 가로 크기인 N, M의 범위가 3이상 10이하다. 오버 걱정은 안 해도 될듯 하다. - 보드 정보는 벽(#), 빈칸(.), 빨간 공(R), 파란 공(B), 구멍(O)으로 이루어져 있다. - 게임의 목표는 빨간 공..
백준 알고리즘 중급 - 브루트 포스(문제) 쭉쭉 풀어보자. * 차량 번호판 1 (mid) : 조건을 만족하는 차량 번호판 개수를 구하는 문제다. 16968번: 차량 번호판 1 00부터 99까지 총 100가지 중에서 00, 11, 22, 33, 44, 55, 66, 77, 88, 99가 불가능하다. www.acmicpc.net - 같은 글자가 두 번 연속해서 나타나면 안 된다는 조건은, 무조건 그 앞의 숫자랑만 다르면 되는 거니까 맨 앞에는 n, 그 다음부터는 쭉 n-1이라고 보면 된다. #include #include #include using namespace std; int main() { int ans = 1; string num; cin >> num; int cC = 0, cD = 0; int ch = 26, d = 10; for (int..
백준 알고리즘 중급 - 이분 탐색 (연습) 하나 정리해둘 것 : 최댓값의 최솟값, 최솟값의 최댓값을 구하라고 하면 이분 탐색이라고 보면 된다. 중급 1 마지막 강의다. 여기까지 정리하고, 당분간은 자소서 쓰기 바쁠 것 같다. 정리 시작! - * 기타 레슨 (mid) : 가능한 블루레이의 길이 중 최소를 구하는 문제다. 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경�� www.acmicpc.net - n개의 레슨을 m개의 블루레이에 저장하려고 한다. 구하려는 최댓값의 최솟값은 블루레이의 크기다. - left는 레슨 중 가장 긴 값을 넣는다. 그러면 모든 레슨을 하나씩 담을 수 있을 거다..
백준 알고리즘 중급 - 이분 탐색 이분 탐색에 대해 ARABOJA - * 이분 탐색 (binary serach) : 어떤 기준을 가지고 yes or no 판별을 반복하여 답을 구하는 방법이다. - 가능한 정답의 최솟값 (left), 최댓값 (right), yes or no 판별 함수가 필요하고 조건에 따라 값이 더 커지거나 작아진다. - 어느정도의 포맷이 있어서 좀 적응하면 문제의 해결의 틀은 비교적 쉽게 잡힌다. 바로 예제 풀어보자. * 수 이어 쓰기 (mid) : n까지 수를 이어서 썼을 때, k번째 수가 뭔지 찾는 문제다. 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.ne..
백준 알고리즘 중급 - 정렬 기본 중에 기본이 되는 알고리즘. 그만큼 중요하다. 중요하고 자주 사용되는 만큼, 대부분의 정렬 함수는 C++에서 표준 함수로 제공한다. 하지만 정렬 자체로는 그리 의미 있는 문제가 많이 없어서 간단하게 중요한 개념 정리하고, 풀면서 조금 헷갈렸던 문제를 꼽아 정리했다. 정리 시작! - * 정렬 (Sorting) : 리스트에 담긴 자료를 어떠한 순서로 나열하는 것. 선택, 버블, 삽입, 퀵, 힙, 병합 등 다양한 정렬 알고리즘이 있는데.. 그냥 빠른 걸 사용하면 된다. 확장성을 가지려면 O(nlogn)이 걸리는 정렬을 사용해야 한다. 보통 STL로 제공되는 sort 함수를 사용하는데, 이는 퀵 정렬을 기반으로 한다. - 기본값은 오름차순이지만, 여러 값을 기준으로 정렬하고 싶으면 함수를 따로 만들면 된다..

티스토리툴바