Algorithm Problem/Python

[python] 백준 - 1105. 팔

🤔문제 해결 수가 20억이기 때문에 하나씩 하기에는 시간초과가 발생한다. 숫자의 범위가 주어지고, 8의 '최소' 개수를 구하라고 했다. 그러므로 각 자리수를 비교해보기로 했다. 먼저 자리수가 다른 경우에는 8의 최소 개수가 0이 된다. - 자리수가 다르면 각 자리의 수를 범위 내에서 아무거나 선택할 수 있기 때문에 자리수가 같은 경우 첫번째 자리부터 마지막으로 순차적으로 비교해본다. 각 자리가 서로 같은 8인 경우 최소 8 개수의 +1, 그리고 다음 자리 비교 각 자리가 서로 다른 경우 +0, 그리고 끝 - 뒤 자리의 숫자는 비교할 필요가 없다. 💻소스 코드 L, R = input().split() # 두 수의 자리수가 다른 경우 8이 들어가는 횟수는 최소 0이 나온다. answer = 0 if len(..

[python] 백준 - 13023. ABCDE

🤔문제 해결 문제는 이어져있는 친구가 4명인지 물어보는 것... ( 헷갈렸다 ) 기본적인 DFS 문제이다. 중간에 조건을 줘서 잘 멈춰주기만 한다면 시간초과는 해결될 것이다. 💻소스 코드 import sys def dfs(current, cnt): global answer if answer == 1: # 답을 이미 찾았다면 dfs 멈추기 return if cnt == 5: # 답 찾았을 때 (친구가 4명) answer = 1 return visited[current] = 1 for neighbor in adj[current]: if not visited[neighbor]: dfs(neighbor, cnt + 1) visited[current] = 0 input = sys.stdin.readline ans..

[python] 백준 - 2615. 오목

🤔문제 해결 6목은 안된다. 답을 출력할 때, 왼쪽 우선, 위쪽 우선 이므로 바둑돌을 기준으로 우상, 우, 우하, 하 이렇게 4방향만 고려해줬다. 먼저 바둑돌 하나를 선택하고 이 바둑돌이 끝에서 시작하는지 or 끝이 아니라면 내가 체크할 방향의 반대방향으로 상대 바둑돌이 없는지 육목 방지 위의 조건에 맞다면 내가 정한 방향으로 탐색하며 같은 색의 바둑돌을 계속 찾음 상대 바둑돌을 만나거나 바둑판 밖으로 나가면 내가 찾은 바둑돌의 개수를 체크 바둑돌을 4개 더 찾았으면 성공 아니면 실패 💻소스 코드 import sys input = sys.stdin.readline LENGTH = 19 board = [list(map(int, input().split(" "))) for _ in range(19)] # 우..

[python] 백준 - 1052. 물병

🤔문제 해결 S1 | 이진법 물의 양이 1, 2, 4, 8, 16, ... 이렇게 증가하므로 이진수처럼 생겼다. 같은 수를 더하면 다음 수 하나가 나온다. 이진수로 보면 ex) 100 + 100 = 1000 예시로 설명해보자면 N = 11 일 때 물병: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 물병합: 2, 2, 2, 2, 2, 1 물병합: 4, 4, 2, 1 물병합: 8, 2, 1 물병은 결국 3개가 된다. 11을 이진수로 바꾸면 1011 이다. 결국 1의 개수가 다 합쳤을 때의 물병의 개수가 된다. 그럼 1의 개수를 줄이고 싶으면 이진수 덧셈을 이용한다. 1011(11) + 0001(1) => 1100(12) 1100(12) + 0100(4) => 10000(16) 🚀 이진수를 잘 이..

[python] 프로그래머스 - 이진 변환 반복하기(월간 코드 챌린지 시즌1)

🤔문제 해결 '0'이 제거된 갯수도 필요하기 때문에 '0'의 개수를 저장 s의 길이에서 0의 개수를 빼주면 '1'로 구성된 s의 길이가 나옴 그 길이를 2진법으로 표현 1-3 반복 💨 아마 월코챌 1번 문제였던거 같다. 💻소스 코드 def solution(s): cnt, removed_zero_cnt = 0, 0 while s != '1': # 1. x의 모든 0을 제거한다. zero_cnt = s.count('0') # 2. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꾼다. s = bin(len(s) - zero_cnt)[2:] cnt += 1 removed_zero_cnt += zero_cnt return [cnt, removed_zero_cnt] 📕문제 확인 출처: 프로그..

[python] 프로그래머스 - 다단계 칫솔 판매(2021 Dev-Matching: 웹 백엔드 개발자(상반기))

🤔문제 해결 판매원을 키, 추천인과 수익을 밸류로 하는 딕셔너리를 만든다. (enroll, referral) 칫솔을 판매한 사람을 선택하고, 추천인과 수익을 계속 나눈다. 💨 보통 이렇게 하면 마지막 3개의 케이스에서 시간초과가 발생한다. 그 이유는 수익을 더 이상 나눌 수 없는 상태여도 추천인을 따라서 0원의 수익을 나눠 갖는 척을 하기 때문 따라서 더 이상 수익을 나눌 수 없는 상황이 되면 반복문을 멈춰준다. 💻소스 코드 def solution(enroll, referral, seller, amount): answer = [] multistages = {'-': ['', 0]} for e, r in zip(enroll, referral): multistages[e] = [r, 0] for s, a i..