본문 바로가기

전체 글

BaekJoon 10989 수 정렬하기 3 2019. 1. 12. Link https://www.acmicpc.net/problem/10989 소스결과 1136 KB / 2444 ms 출처 Backjoon 언어 C 분류 정렬 설명 개수가 많아서 시간제한이 3초다, 근데 메모리는 고작 8 MB 배열을 전부 저장하게 되면 메모리는 견디지 못한다. 메모리가 넉넉했더라면 Quick Sort로 구현 해도 정답이 되겠지만 위 문제는 Quick Sort로 구현하는게 아니다. 중복되는 수가 존재하기 때문에 그 수의 개수만 알고 있으면 되고, 그 수를 순서대로 출력하는 Counting Sort를 구현하는 문제이다. 다른 Sorting과는 다르게 중복 되는 값이 존재하는 경우에 사용하는 Sorting 방법이다. 주 핵심은 중복되는 값의 개수를 저장하는 것이다. 알고리즘 1. 값을 입력 ..
BaekJoon 1026 보물 2019. 1. 12. Link https://www.acmicpc.net/problem/1026 소스결과 1988 KB / 0 ms 출처 Backjoon 언어 C++ 17 분류 정렬 설명 S 의 값을 최소로 만들어야 하는 문제 위 공식을 통해 최소로 만들기 위해서는 a는 오름차순으로, b는 내림차순으로 정렬하면 된다. 문제에서는 재배열 하면 안된다고 쓰여 있지만 정답과는 관련이 없기에 정렬 해주자 알고리즘 1. a와 b를 입력 받는다. 2. a를 오름차순 정렬한다. 3. b를 내림 차순 정렬한다. 4. 각 위치의 값을 곱해 전부 더한다. 5. 출력 소스코드 #include using namespace std; int main() { int n; int a[50]; int b[50]; int sum = 0; cin >> n; ..
BaekJoon 2580 스도쿠 2019. 1. 11. Link https://www.acmicpc.net/problem/2580 소스결과 1988 KB / 104 ms 출처 Backjoon, 한국정보올림피아드 시,도 지역본선 초등부, 중등부 언어 C++ 17 설명 두뇌 회전으로 많이 푸는 스도쿠를 백트래킹을 이용해서 정답을 찾는 문제 스도쿠의 규칙인 가로, 세로, 박스 안에는 1 ~ 9 까지 단 1개씩만 들어가야 한다. 를 만족시키기만 하면 된다. 가로에서 필요한 값과 세로에서 필요한 값, 박스에서 필요한 값으로 나누어서 세 개 에서 전부 필요한 값만 사용하면 된다. 스도쿠 규칙만 안다면 크게 어렵지는 않았다. 어렵지는 않지만 그래도 한번에 통과하니 뿌-듯 알고리즘 1. 스도쿠 배열을 입력 받으면서 빈 칸의 위치 따로 저장한다. 2. 저장한 빈칸의 위치를 ..
BaekJoon 1759 암호만들기 2019. 1. 11. Link https://www.acmicpc.net/problem/1759 소스결과 1988 KB / 0 ms 출처 Backjoon 언어 C++ 17 설명 조금 간단한 백트래킹 0과 1로 이루어진 순열을 만들어 낸다 라고 생각하면 편하다. 모음이 1개 이상 , 자음이 2개 이상일 경우에만 출력하도록 조건을 걸면 된다. 알고리즘 1. 알파벳을 입력받아 - 'a'를 한뒤 사용할 수 있는 알파벳을 식별하는 배열에 넣는다. 2. 현재 알파벳을 사용 했으면 알파벳을 식별하는 배열의 값을 false로 바꾼후 함수를 재귀 호출한다. 3. 위치를 나타내는 pos가 암호의 길이 l 이 될때까지 반복 한다. 소스코드 #include using namespace std; int l, c; bool alpha[26]; cha..
BaekJoon 1966 프린터큐 2019. 1. 10. Link https://www.acmicpc.net/problem/1966 소스결과 1984KB / 0 ms 출처 Backjoon, NWERC 2006 F번 언어 C++ 17 분류 시뮬레이션(Simulation) 연관검색어 백준 1966 C++, BOJ 1966 C++, C++ BOJ 1966 설명 ' 우선순위 ' 가 포함된 큐 이다. 말 그대로 우선순위 큐를 이용하는 문제다. Max Heap을 이용하면 쉽게 풀리는 문제다. 이번 문제는 Max Heap을 이용하지 않고 문제 자체에 충실하게 구현했다. 무한루프를 사용하지 않고 만들고 싶었지만 최근 결과를 보니 거의다 무한루프를 사용.. 정답률도 높고 하니 한번쯤은 무한루프를 사용해도 괜찮다 생각해서 사용했다. 알고리즘 1. 개수, 목표 번호, 우선순위를 ..
BaekJoon 1094 막대기 2019. 1. 10. Link https://www.acmicpc.net/problem/1094 소스결과 1984 KB / 0 ms 출처 Backjoon 언어 C++ 17 분류 수학, 시뮬레이션(Simulation) 연관검색어 백준 1094, BOJ 1094 C++, C++ 1094 설명 자르고 붙이고 자르고 붙이고 반복문을 통해 구현을 하는 내용이다. 라고 생각할 수도 있지만 위 문제의 분류에는 수학이 포함되어있다. 문제 설명대로 풀면 합을 계산하고 현재 가장 작은 막대기를 계산하고 해야 하지만 위 문제는 2진법에 관한 문제이다. 23의 경우 2진법으로는 16 + 4 + 2 + 1의 합으로 10111 이고 여기서 1의 개수는 4개이다 64나 32 같은 경우는 1000000 과 100000 이므로 1의 개수는 1이다. 따라서..
BaekJoon 2455 지능형 기차 2019. 1. 10. Link https://www.acmicpc.net/problem/2455 소스결과 1984KB 0ms 출처 Backjoon, 한국정보올림피아드 시,도 본선 지역본선 2011 초등부 1번 언어 C++ 17 연관 검색어 백준 2455 C++, BOJ 2455 C++, C++ 2455 설명 탄사람 - 내린 사람으로 계산하면 아마 틀리지 않을까? 8개의 입력 으로 되어 있으니 탈 때 내릴 때 구분해서 만들자 알고리즘 1. 내릴 때 탈 때 를 구분해 현재 인원수에 + 또는 - 를 한다. 2. 현재 최대 인원수랑 비교해서 최대 인원수를 갱신한다. 3. 출력 소스코드 #include using namespace std; int main() { int max = 0; int sum = 0; for (int i = 0..
BaekJoon 1213 팰린드롬 만들기 2019. 1. 10. Link https://www.acmicpc.net/problem/1213 소스결과 1988KB / 0 ms 출처 Backjoon 언어 C++ 17 분류 브루트포스(Brute Force), 정렬(Sorting) 연관 검색어 1213 C++, BOJ 1213 C++ 설명 주어진 단어를 팰린드롬으로 바꿀 수 있는지에 대한 문제 팰린드롬이란 ? 위키백과 - 회문(Palindrome) 백준 문제 종류가 브루트포스이지만 풀고나서 채점결과를 보니 막상 그렇게 구현한사람은 찾기 힘들다. 정렬로 보면 Counting Sort에 속하기는 하지만 실질적으로 정렬을 하지는 않으니 정렬도 애매하다고 생각된다. 길이가 홀수인 경우, 짝수인 경우로 분류해서 해결하고 불가능한 경우가 명확하기 때문에 불가능한 경우를 제한다면 정답은..

티스토리툴바