공부방/Today I Learned 39

[TIL] 프로그래머스 - 전화번호 목록 / 위장 (feat. reduce)

[주절주절] 면접 통보 받았다! 휴 기술 면접이 포함되어 있어서 프로그래머스 고득점 kit로 유형 쭉 다시 보고 가볼 계획이다 [Today I Learned] # 프로그래머스 - 전화번호 목록 문제 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119박준영 : 97 674 223지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. @so..

[TIL] 백준 - 덩치 / 빗물

[주절주절] SQLD 공부하고~ 알고리즘 풀고~ 야구 보고~ 인터뷰 준비하고~ (인터뷰 확정 메일은 아직 못받은게 함정 뭐야 얼른 알려줘요) [Today I Learned] # 백준 - 덩치 문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크..

[TIL] 백준 - 그룹 단어 체커 / 피보나치 수 5 / 전쟁 - 전투

[Today I Learned] # 백준 - 그룹 단어 체커 문제 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. @solution.py # 그룹 단어 체커 words = [input() for _ in range(int(input()))] answer = 0 for word in words: group = True alphabet = {} for idx in ran..

[TIL] 백준 - 연산자 끼워넣기

[Today I Learned] # 백준 - 연산자 끼워넣기 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오. @solution.py DFS 방향성은 금방 캐치 했는데, 전달하는 인수를 컨트롤하는데 애를 먹었다. 비슷한 문제를 풀 때 항상 겪는 문제 : / 다른 사람들 코드를 참고해 코드..

[TIL] 다이나믹 프로그래밍 (동적 계획법, DP) / 이코테 - 금광, 병사 배치하기

[Today I Learned] 어제에 이어서 다이나믹 프로그래밍을 계속 공부했다. # 이코테 - 금광 문제 n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요. @solution.py 생각의 흐름은 다음과 같았다. 1. 각 칸에서 최선의 선택을 한다고 그것이 항상 최선의 결과를 가져오지는 않음 ( != 그리디 알고리즘..

[TIL] 다이나믹 프로그래밍 (동적 계획법, DP) / 이코테 - 개미 전사, 1로 만들기, 효율적인 화폐 구성

[주절주절] 자기소개서 써야해서 + 엄마, 아빠가 싱가포르 놀러오셔서 멈춰버린 알고리즘 공부.. 다행히 지난주 금요일에 있었던 코테는 무난무난하게 치렀다. 그래도 알고리즘 공부는 계속해볼 예정. 앞으로 뭐하고 살지~ [Today I Learned] # 다이나믹 프로그래밍 - 메모리를 적절히 사용하여 수행 시간 효율성을 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장해 다시 계산하지 않도록 - 일반적으로 탑다운, 보텀업, 두 가지 방식으로 구성 - 동적 계획법이라고도 부르나 별 다른 의미 X - 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용 가능 ㄴ 1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 ..

[TIL] DFS & BFS 특집! | 프로그래머스 - 네트워크 / 백준 - 바이러스 / 프로그래머스 - 타겟 넘버 / 백준 - 숨바꼭질

[Today I Learned] 대충 DFS와 BFS를 뽀개보겠다는 의지를 담은 제목. # 프로그래머스 - 네트워크 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다..

[TIL] 프로그래머스 - 주식 가격 / Leetcode - Trapping Rain Water 😣

[Today I Learned] # 프로그래머스 - 주식 가격 문제 설명 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. @solution.py 스택 써서 매뉴얼 하게 푸는 건 금방 캐치했는데, 코드로 세팅하기까지가 오래 걸렸던 문제 : / def solution(prices): prices = [(p,i) for i,p in enumerate(prices)] stack = [] answer = [0] * len(prices) # stack for ..

[TIL] 프로그래머스 - 다리를 지나는 트럭 / 프로그래머스 - 프린터

[Today I Learned] # 프로그래머스 - 다리를 지나는 트럭 문제 설명 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다. @solution.py 문제를 잘 읽자! 다리를 '정해진 순'으로 건너는건데 내가 최적의 순까지 찾아야..

[TIL] 프로그래머스 - 입국심사 / 코테에 활용할 수 있는 Pythonic한 코드 조각 / 당분간 계획

[Today I Learned] # 프로그래머스 - 입국심사 문제 설명 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록..