백준 알고리즘 - 체스판 다시 칠하기 (Brute Force) [Python]

문제 www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 상황 - 체스판 색깔이 백, 흑이 반복되어야 하는데 8이상, 50이하 길이의 판이 주어질 때 최소의 색칠로 8 by 8 체스판을 만들 경우의 최소 색칠 수를 반환한다. 해결 전략 - 우선 시작 행, 시작 열을 입력 했을 때 8 by 8 판에 해야 할 색칠의 수를 반환하는 함수를 만들고, 판의 가장 왼쪽 가장 위의 지점을 이동시키며 모든 경우를 탐색한다. 코드 1 2 3 4 5 6 7 8 9 1..
알고리즘 학습/백준 알고리즘 2021. 1. 11. 22:46
프로그래머스 - 점프와 순간 이동 (Summer/Winter Coding(~2018)) [Python]

문제 programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 문제 상황 - 연료를 사용하여 점프를 하거나, 연료 사용없이 지금까지 이동해온 거리만큼 순간이동을 하여 움직이는데 목표점을 정확히 도착하는데 최소의 연료로 도착할 때 연료 소비량을 계산한다. 해결 전략 - 최대한 2배가 되는 것을 활용해야 하고 점프를 최소화 해야한다. 역으로 생각하여 2배로 이동하는 것을 최대로 활용하기 위해 주어진 n을 2로 나..
알고리즘 학습/프로그래머스 2021. 1. 10. 18:46
프로그래머스 - 예상 대진표 (2017 팁스타운) [Python]

문제 programmers.co.kr/learn/courses/30/lessons/12985 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 문제 상황 - 1번부터 n번까지 사람이 게임을 진행한다고 할 때 a, b는 모든 게임에서 이긴다는 조건으로 게임을 진행한다. a와 b가 만날 때까지 진행된 게임의 수를 계산한다. 해결 전략 - 주어진 수를 2로 나누며 같아질 때까지 반복하여 그 횟수를 출력한다. 코드 1 2 3 4 5 6 7 8 9 def solution(n,a,b): cnt =..
알고리즘 학습/프로그래머스 2021. 1. 10. 14:07
프로그래머스 - 다트 게임 (2018 KAKAO BLIND RECRUITMENT) [Python]

문제 programmers.co.kr/learn/courses/30/lessons/17682 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 문제 상황 - 3번의 다트 게임을 시행하는데 총 점수를 계산한다. 점수 계산법은 S,D,T와 #, * 를 활용한다. 해결 전략 - 정규 표현식을 사용하면 편할 수 있을 것 같지만 문제의 난이도가 낮아 단순한 문자열 탐색으로 가능하다. 문자열을 순회하며 게임 하나의 케이스로 판별하는 조건을 정의하여 게임의 점수를 계산해 나간다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 def get_score(dart:str) -> int: if dart[-1] ..
알고리즘 학습/프로그래머스 2021. 1. 10. 13:29
프로그래머스 - 이진 변환 반복하기 (월간 코드 챌린지 시즌1) [Python]

문제 programmers.co.kr/learn/courses/30/lessons/70129 코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr 문제 상황 - 문자열을 순회하며 1의 개수를 이진수로 반환하는 작업을 반복하며 입력된 수가 "1"이 될 때까지 반복된 횟수와 연산 과정에서 삭제된 0의 개수를 출력한다. 해결 전략 - 1의 개수를 2진 변환 해주는 함수를 작성하고, 이 연산을 반복하며 횟수와 삭제된 0의 개수를 출력한다. 여기서 0의 개수는 입력된 전체 길이에서 연산 될 1의 개수를 빼주면 된다.(0의 개수를 구하기 위한 새로운 메모리 할당 필요 x) 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def binary_transition(x: str) -..
알고리즘 학습/프로그래머스 2021. 1. 8. 09:27
프로그래머스 - 스킬트리 (Summer/Winter Coding(~2018)) [Python]

문제 programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 문제 상황 - 입력받은 문자열은 중복되지 않는 대문자 알파벳이며, 이 알파벳은 반드시 순서를 지켜야한다. skill_trees에서 가능한 스킬트리의 개수를 출력한다. 해결 전략 - 기본적으로 후보군을 순회하며 스킬트리에 있는 스킬인지 확인한다. 스킬트리에 없는 것이라면 넘어가고, 스킬트리에 있는 것이면 첫번째 요소와 비교하여 첫번째 요소와 다르면 후보에서 탈락된다. 만약 첫번째 요소와 같으면 그 요소를 삭제하고 다음으로 넘어간다. 모두 통과하면 정답 수를 하나 늘린다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 from col..
알고리즘 학습/프로그래머스 2021. 1. 7. 22:40
프로그래머스 - 멀쩡한 사각형 (Summer/Winter Coding(2019)) [Python]

문제 programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 문제 상황 - 가로 Wcm, 세로 Hcm인 종이를 대각선으로 잘라 단위 사각형으로 잘라 쓸 수 없는 부분을 전체에서 제거한다. 해결 전략 - 전체에서 대각선이 지나가는 사각형을 빼야하고, 결국 반복되는 구조이므로 최소 비율이 몇번 반복되는지 찾아야한다. 이를 위해 GCD(최대 공약수) 개념이 필요하다. 예시의 8cm, 12cm의 경우 비율이 2..
알고리즘 학습/프로그래머스 2021. 1. 7. 13:17
[파이썬 알고리즘 인터뷰] - 7장 p.193 (Leet Code 238번)

문제 leetcode.com/problems/product-of-array-except-self/ 문제 상황 - 배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력한다. - 나눗셈을 하지 않고 O(N)에 해결한다. 해결 전략 - 두가지 방향으로 곱을 쌓아 나가 연산한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 from typing import List class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: result = [] temp = 1 for i in range(len(nums)): result.append(temp) temp *= nums[i] ..
알고리즘 학습/파이썬 알고리즘 인터뷰 2021. 1. 5. 20:57
1 ··· 17 18 19 20 21 22 23 ··· 39