B_log

문제 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] ..

문제 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) -..

문제 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..

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

문제 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] ..

문제 app.codility.com/programmers/lessons/7-stacks_and_queues/fish/ Fish coding task - Learn to Code - Codility N voracious fish are moving along a river. Calculate how many fish are alive. app.codility.com 문제 상황 - 물고기의 크기 리스트와 방향 리스트가 주어진다. 큰 물고기가 작은 물고기를 잡아먹고 최종적으로 살아남은 물고기의 수를 카운팅한다. 해결 전략 - 전체 물고기를 순회하며 주어진 조건을 연산한다. 상행 물고기들을 모을 스택을 만든다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def solu..

문제 leetcode.com/problems/3sum/ 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 상황 - 세수의 합이 0이 되는 케이스를 찾는다. 해결 전략 - Brute Force로 모든 경우를 순회하며 가능성을 찾으면 되지만 O(N^3)로 일반적 조건에서 속도 이슈가 발생할 수 밖에 없다. - 투포인터를 활용해 한 요소를 기준으로 두 요소를 더해 그 합이 0보다 크면 줄이고, 0보다 작으면 키우는 방향으로 포인터를 이동시킨다. - 이를..

문제 - 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. - 입력 => [0,1,0,2,1,0,1,3,2,1,2,1] - 출력 => 6 문제 상황 - 높이와 너비 모든 공간을 체크하면 O(N^2)로 풀이가 가능하지만 O(N)으로 속도를 줄일 수 있다. 해결 전략 - 크게 투포인터 방식과 스택을 이용한 방식이 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def solution(heights:list) -> int: left, right = 0, len(heights)-1 leftmax, rightmax = 0, 0 water = 0 # 총 물의 양 # index left가 right보다 왼쪽에 있을 동안 반복 while left