개발 · 컴퓨터공학/알고리즘

백준 1090 체커 파이썬 문제풀이 (python 완전탐색)

문제 보러가기 백준 체커 파이썬 문제풀이체커 게임은 익숙하지 않은데, 체스판처럼 흑백 격자판에서 이루어지는 게임이다.  체커 말은 상하좌우로 움직이며 겹치는게 가능하다고 한다. 말의 좌표가 하나씩 들어오는데 그 값은 1,000,000 이하라고 한다.즉 여기서 100배를 더하면 1억 즉 1초가 되는데, 그것보다 적게 연산하라는 뜻이다. 출력하는 값으로는 k번째 수가 k개의 체커가 같은 칸에 모일 수 있는 최소 움직임 수라고 한다.즉 체커가 특정 좌표까지 이동해야하는 수가 있고1개만 모이는 경우부터 모든 체커말이 모이는 경우 필요한 이동 수를 구하는 문제이다. 상당히 난해한데.. 바로 생각나는 접근 법은 각 체커의 이동횟수를 적어놓는 표를 만들어서 겹쳐져야 하는 말들의 이동횟수 총합이 가장 작은 값을 찾아내..

2024. 9. 4. 07:48

개발 · 컴퓨터공학/알고리즘

백준 2503 숫자야구 파이썬 문제풀이 (python 완전탐색)

백준 문제 보러가기 백준 2503 숫자야구 파이썬 문제풀이숫자 야구를 해보신 분들도 있겠지만, 저는 코딩을 통해 처음 알게된 게임이다. 서로 다른 숫자 세 자리 수를 생각하고, 이를 물어보면자리수마다 정답이면 스트라이크, 숫자는 맞으나 위치가 틀리면 볼로 세서 알려준다. 324가 정답이라면 241은 0 스트라이크 2볼이고924는 2 스트라이크 0볼인 셈이다. 질문을 n번 주면 정답으로 나올 수 있는 게 몇 가지인지 출력하면 된다. 질문한 숫자에서 스트라이크가 몇 개고, 볼이 몇 개고 하는 것으로 케이스를 나누어 추정하는 방법도 있겠지만,제한 시간을 먼저 보자. 1초이다. 나올 수 있는 전체 가짓수는? 9*8*7 = 504개이다.질문은 최대 100번 할 수 있으니, 질문 하나에 대해 모든 수를 생각해보면 ..

2024. 8. 6. 09:00

개발 · 컴퓨터공학/알고리즘

백준 19532 연립방정식 파이썬 문제풀이 (python 완전탐색, 수학은 비대면강의입니다)

백준 19532 문제 보러가기  백준 19532 연립방정식 문제 풀이위 연립 방정식에서 x,y를 계산하는 방법에 대한 문제이다. a,b,c,d,e,f 가 주어지면 x,y를 구하면 된다. 범위가 -999~999 이므로 하나씩 넣어보면 될 것 같다.즉 0~999까지 1000개인데 음의 수까지 하면 약 2000개이다.  x,y 각각 가능성이 2000개씩이면 총 경우의 수는 2000*2000 = 4,000,000 인가제한시간이 1초이므로 시간이 부족하진 않다. a,b,c,d,e,f = map(int,(input()).split())for x in range(-999,999+1): for y in range(-999,999+1): if a * x + b * y == c and d * x + e ..

2024. 8. 5. 09:00

개발 · 컴퓨터공학/알고리즘

백준 14568 사탕 파이썬 문제풀이 (python 완전탐색, 2017 연세대학교 프로그래밍 경시대회)

백준 14568 문제 보러가기 백준 14568 사탕 문제 사탕을 나누는 문제이다. 세 명이 사탕을 나누어 받는데 다음 조건을 고려한다.남는 사탕은 없어야 한다.남규는 영훈이보다 2개 이상 많은 사탕을 가져야 한다.셋 중 사탕을 0개 받는 사람은 없어야 한다.택희가 받는 사탕의 수는 홀수개가 되어서는 안 된다.단순히 생각하자.삼중 반복문으로 하나씩 케이스를 돌려 보면서 다음 조건을 모두 만족하는 경우를 찾아서 카운트를 세는 거다.  사탕의 개수 N은 100이 최대이고, 삼중으로 반복해도 1,000,000 이므로 1초가 안된다.  candy = int(input())cnt = 0for a in range(1, candy-2 + 1): # taqui for b in range(1, candy-2 + 1)..

2024. 8. 3. 09:00

개발 · 컴퓨터공학/알고리즘

백준 1816 암호키 파이썬 문제풀이 [python 완전탐색]

백준 1816 문제 보러가기 백준 1816 암호키n = int(input())for i in range(n): s = int(input()) if s 먼저 입력을 받고 크기 확인부터 하자. 몇 년만의 알고리즘이라 소수 판별법을 까먹었다. 대표적인 에라토스테네스의 체 방법은 너무 큰 숫자에서는 시간낭비이다. 일단 input 숫자의 범위는 \(10^{12}\)에서 \(10^{18}\) 까지이다.시간을 생각해보면 에라토스테네스의 체는 O(n log(log n))으로 어려울 것 같다는 생각이 드는데.. 소수는 결국 어떤로 나누어지는지 확인을 해야하고 아무리 확인해도 제곱근보다 큰 경우까지 볼 필요는 없다.즉 범위가 \(10^{18}\)이면 확인해야하는 숫자는 \(10^9\) 까지. 1,000,000,..

2024. 7. 31. 09:00