본문 바로가기

전체 글81

[이것이 코딩 테스트다] 못생긴 수 - 다이나믹 프로그래밍 문제못생긴 수란 오직 2, 3, 5 만을 소인수로 가지는 수를 의미합니다.1은 못생긴 수라고 가정합니다.이때 n 번째 못생긴 수를 찾는 프로그램을 작성하십시오. 입력 조건첫 째 줄에 n이 입력됩니다.(1 출력 조건n 번째 못생긴 수를 출력합니다.해결 과정첫번째 아이디어이다.1, 2, 3, 4, ..., n 순으로 탐색한다. 다시 말하면 1부터 n까지 선형탐색을 한다. 현재 위치의 수를 소인수분해해서 못생긴 수인지 파악하는 방법이다.하지만 소인수분해를 계산해야하는 시간적 번거로움이 생긴다.2, 3, 5로 나머지가 0이 아닐 때까지 나누는 함수를 만드는 것은 금방이다. 하지만 991번째 못생긴 수 부터 1000번째 못생긴 수를 보면, 소인수분해 계산에서 시간초과에 걸릴 수 있다고 생각했다.* [ ..., 5.. 2024. 9. 7.
[이것이 코딩 테스트다] 효율적인 화폐 구성 - 다이나믹 프로그래밍 이 문제는 대학교 1학년 때 공부했던 이산수학에서 다룬 문제여서 금방 풀 수 있었다.그때 문제도 마찬가지로 2와 3의 화폐로 모든 화폐를 표현할 수 있냐는 문제였던 것 같다.2, 3, 2+2, 2+3, 3+3, ... 1 이하의 정수를 제외한 모든 화폐를 표현할 수 있었다. 문제의 입력 조건으로는 최대 입력이 100이라서 O(n^2) 으로도 충분하다. 그래서 2중 for문을 채택했다. 최소 화폐 단위가 2, 3, 7이라고 가정하자. 그러면a[i]를 위 화폐 단위로 만들 수 있을 때, a[i](최소 화폐 개수)는 min(a[i], a[i - 2]+1, a[i - 3]+1, a[i - 7]+1) 이다.이것은 이해를 돕기위해 세운 약간 어거지(?) 점화식이다. 실제로는 각 화폐 단위를 하나 씩만 비교하여 따진.. 2024. 9. 6.
[S3] 백준 1463 - 1로 만들기(Python) https://www.acmicpc.net/problem/1463 풀이👀1부터 X까지 반복문으로 1회 순환한다.i (1에 대해서 dp[i]라 할 때, dp[i]는 1에서 출발하여 주어진 조건을 만족하며 i를 만들기 위해 필요한 연산 최소 횟수이다.그러면dp[i]는 (dp[i-1], dp[i//2], dp[i//3], dp[i//5]) 중에서 최솟값을 찾은 다음, +1을 한 값으로 결정난다.코드💻# 1로 만들기X = int(input())dp = [10**7] * (X+1)dp[1] = 0for i in range(2, X+1): dp[i] = dp[i-1] + 1 if i%2 == 0: dp[i] = min(dp[i//2] + 1, dp[i]) if i%3 == 0: .. 2024. 9. 5.
[이것이 코딩 테스트다] 1로 만들기 - 다이나믹 프로그래밍 백준 1로 만들기와 같은 유형의 문제다.X에서 1로 만들기 방법이다. X에서 1로 한 번 순회한다.현재 위치 i (1에서 연산가능한 모든 숫자에 최소 연산 횟수를 기록한다.i가 1이 될 때까지 위 과정을 반복한다.# 1로 만들기X = int(input())dp = [10**8] * (X+1)dp[X] = 0for i in range(X, 0, -1): dp[i-1] = min(dp[i]+1, dp[i-1]) if i%2 == 0: dp[i//2] = min(dp[i]+1, dp[i//2]) if i%3 == 0: dp[i//3] = min(dp[i] + 1, dp[i//3]) if i%5 == 0: dp[i//5] = min(dp[i] + 1, .. 2024. 9. 5.
리그오브레전드 팀 빌딩 프로그램 *완성이라고 하기엔 흠이 많은 프로그램입니다.문제 정의롤 사설 경기에서 플레이어들의 정보를 바탕으로 균형 잡힌 팀을 자동으로 구성해주는 프로그램입니다. 로직 설명플레이어들의 정보를 수집합니다. 플레이어의 정보에는 [닉네임, 랭크 티어, 주 포지션, 서브 포지션들] 이 있습니다.포지션별로 플레이어들을 분류합니다. 인원이 적은 포지션부터 우선적으로 배정합니다.배정되지 않은 플레이어들은 랜덤하게 남은 포지션에 할당합니다.코드 원문은 깃허브에서 확인할 수 있습니다.# main.pydef build_team(): # 포지션을 담을 리스트 positions = defaultdict(list) # 각 포지션에 해당하는 플레이어들을 담기 위한 딕셔너리, 기본값은 빈 리스트 for lane in tot.. 2024. 9. 4.
키워드 : keyword 키워드 : 컴퓨터 프로그램용으로 고정된 예약어이자 식별자로 사용할 수 없는 단어 2024. 6. 8.
[HTML/Javascript] 자바스크립트로 HTML의 요소에 자식 요소 추가하기 자바스크립트로 HTML 요소에 자식 요소를 추가할 수 있다.부모요소.appendChild(자식으로 넣을 요소)버튼을 누르는 등의 이벤트가 발생했을 때, 새로운 요소를 추가함으로써 사용자에게 새로운 정보를 보여줄 수 있을 것 같다.const parent = document.getElementById("parent_element");const childElement = document.createElement("div");childElement.innerText = "요소가 새로 추가됐습니다!"parent.appendChild(childElement);다양한 활용 예시알림 메시지 표시사용자가 버튼을 눌렀을 때 화면에 알림 메시지를 표시하는 기능새로운 입력 폼 추가사용자가 버튼을 눌렀을 때 새로운 입력 포을 .. 2024. 6. 8.
[HTML/Javascript] 🖱️클릭 이벤트 처리 하는 방법 이나 나 무엇이든, html로 표현하여 웹에 보여지는 것들은 '클릭 이벤트'를 처리할 수 있다.이벤트리스너 설정하기(addEventListener)*HTML*Javascriptdocument.getElementById('id 이름').addEventListener('click', 실행할 함수);ex) document.getElementById('cell1').addEventListener('click', colorCilckedLocation)document.getElementById('cell1').addEventListener('click', colorCilckedLocation) 코드에서 함수 뒤에 괄호로 매개변수를 주지 않는 이유는 함수의 참조를 전달하기 위해서이다.괄호를 붙이면 함수가 즉시 실행되.. 2024. 6. 1.

티스토리툴바