본문 바로가기

알고리즘4

백준 32291번 - x와 x+1의 차이(증명 포함, C++) 문제백준, 실버 1, https://www.acmicpc.net/problem/32291풀이 날짜: 2025.4.15.풀이 시간: 10:49~11:32(43분)사용 언어: C++문제 해설해당 문제는 (x+1)의 자신을 제외한 약수를 구하는 문제이다.우선, 그에 도달하는 과정을 살펴보자.예제 1의 출력을 보면, x = 998일 때 x+1의 자신을 제외한 약수 1, 3, 9, 27, 37, 111, 333이 정답이 된다.이를 보고 출력이 되는 모든 양의 정수 k는 (x+1)의 약수라고 가설을 세울 수 있다.왜 k는 반드시 (x+1)의 약수인가?가설을 세웠으니 증명해 보자.다만 고등학생 때 배웠던 귀류법을 가지고 야매로 증명했다 보니, 정확하지 않을 수 있다는 점 양해 바란다. 잘못된 점이 있다면 지적해주면 .. 2025. 4. 15.
백준 1311번 - 할 일 정하기 1 문제백준, 골드 1, https://www.acmicpc.net/problem/1311풀이 날짜: 2025.1.29.풀이 시간: 15:17~16:30, 안 돼서 GPT 킴, 17:28에 DFS 방식으로 해결(총 2시간 11분)알고리즘 분류: 비트필드를 이용한 다이나믹 프로그래밍사용 언어: C++문제 해설해당 문제는 비트필드를 이용한 다이나믹 프로그래밍을 활용하는 문제이다.문제의 정답을 탐색할 때 탐욕법이나 다른 방법을 사용할 수 없으므로, 완전 탐색으로 모든 경우의 수를 측정해야 한다. 그런데 4명의 사람이 순차적으로 1-2-3-4번 일을 맡는 경우와 2-1-3-4번 일을 맡는 경우, 뒤의 3-4번 일의 비용을 계산할 땐 중복 계산이 발생하게 된다.이러한 중복 계산을 피하려면 상태를 저장하는 비트필드 기.. 2025. 1. 29.
랜덤 미로 생성 알고리즘 정리 이전 포스팅에서는 경어체를 사용했지만 긴 글을 쓰기에는 불편해서 낮춤말로 쓰려고 합니다. 이 점 양해 바랍니다. 동아리에서 미로에 관한 이야기를 하다가 동아리 선배가 미로를 생성하는 데에는 많은 알고리즘이 있다고 이야기했다. 나는 또 그런 이야기를 들으면 못 참는 성격이라서 직접 자료를 찾아보니, 당장 인터넷에만 해도 무려 한글(!) 미로 생성 알고리즘도 많아 놀라웠다. 참고할 만한 자료도 적당히 있어서 가볍게 공부하기에 적당한 주제인 데다가 도전 욕구를 자극하는 소재였다. 그래서 간단하게 유니티를 랜덤 미로 생성을 만들어보기로 했다. http://www.jamisbuck.org/mazes/ Maze Algorithms Maze Algorithms If you're interested in maze al.. 2020. 9. 8.
초심자를 위한 알고리즘과 자료구조 1편 - 알고리즘 - 해당 글은 비전공자 혹은 개발 초심자를 대상으로 하는 글입니다. 다소 비전문적이고 구어체에 가까운 표현이 등장하더라도 양해 부탁드립니다. - 수학적으로 엄밀하지 않은 정의를 포함하고 있습니다. 알고리즘이라는 단어는 누구나 한 번쯤 들어보셨을 겁니다. 컴퓨터 과학 관련 전공을 하신 분이나 개발 분야에서 일하시던 분은 물론이고, 유튜브를 즐겨보는 사람이라면 흔히들 "유튜브 알고리즘의 선택을 받았다"는 식의 드립으로 이야기합니다. 유튜브에서 이해할 수 없는 맞춤 동영상이 올라올 때 그런 말을 합니다. 내가 안 보던 분야의 동영상이 올라오기도 하고, 갑자기 한 번도 들어본 적도 없는 언어의 제목도 간혹 보입니다. 신기하게도 저는 동영상의 썸네일만 보고도 신기해서 곧잘 들어가곤 합니다. 그럴 때면 제가 유튜브.. 2020. 8. 18.

티스토리툴바