GGT 블로그

리스트

• 

  2021 카카오 공채 - 합승 택시 요금 [문제] 지점의 개수 n, 출발지점을 나타내는 s, A의 도착지점을 나타내는 a, B의 도착지점을 나타내는 b, 지점 사이의 예상 택시요금을 나타내는 fares가 매개변수로 주어집니다. 이때, A, B 두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 return 하도록 solution 함수를 완성해 주세요.만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 됩니다. 해설 무지와 어피치가 시작지점(S)로 부터 각각의 집(A, B)에 도착할 수 있는 최소 금액을 찾는 문제 여기서 아예 1)합승을 하지 않을수도, 2)중간부터 따로 갈 수도, 3)아예 한 집에 들렸다 갈 수도 있다. 이와 같은 상황을 .. 2021.09.20

• 

  백준 - 13305 주유소 이번 문제는 주유소 문제로 각 도시마다 기름 값이 다른 주유소가 존재하고 우리는 모든 도시를 이동하기 위한 최소 비용을 구해야 한다. 다른건 제쳐두고 기본적인 것만 생각해보면 결국 1. 당장 다른 도시로 가기 위해서는 기름이 필요 2. 도시를 거치며 더 싼 주유소가 나오기 전 까지는 가장 저렴한 주유소에서 왕창 주유하고 가면 된다. 이러한 로직은 결국 도시를 하나씩 거치면서 이제까지 만난 기름의 최소값 만을 저장하며 순차적으로 총 가격에 더해주면 된다. 이러한 풀이는 그리디 알고리즘으로 현재까지 만난 주유소 중 기름 값이 가장 싼 주유소에서 주유하면 전체 주유 비용의 최소 값을 구할 수 있다는 개념이다. 풀이 def run(): N = int(input()) length_lst = list(map(int.. 2021.09.15

• 

  백준 - 16928 뱀과 사다리 게임 이번 문제는 '뱀과 사다리 게임'이라는 문제인데 해당 게임은 어렸을 때 몇 번 해본 기억이 난다. 아래에서 맨 꼭대기로 올라가는 문제인데 중간 중간 사다리나 뱀을 타고 올라가기도 내려가기도 했던 게임 여기서 우리는 1~6의 값을 가진 주사위를 최소 몇 번 던져서 도착 지점에 갈 수 있는지 구해야 한다. 그리고 어떤 발판은 사다리로 더 멀리 있는 지점에 도달할 수 있고 어떤 발판은 뱀으로 다시 내려오기도 한다. 어떠한 경로를 최소 단계로 도달한다? -> BFS일 것이라고 생각했다. DFS의 경우에는 불가능한 수로 너무 깊게 빠질 수 있으므로 최소 단계를 구하는 데는 적합하지 않다. + 깊이에 따라 스택 오버플로가 발생할 수도 있고 또한 단순히 위 게임의 그림을 보고 발판을 10 X 10의 2차원 배열로 선.. 2021.09.15

• 

  [시작하세요 도커/쿠버네티스] Dockerfile 작성하기 Dockerfile 작성하기 개발한 애플리케이션을 간단히 컨테이너화하기 위해 도커는 'build' 명령어를 지원합니다. 도커 이미지를 생성하기 위해 필요한 일련의 작업들을 Dockerfile에 기록하면 도커는 빌드 명령어를 통해 이를 읽고 이미지를 생성합니다. Dockerfile의 장점 Dockerfile을 사용하면 직접 컨테이너를 생성하고 애플리케이션 세팅 후 직접 이미지로 커밋해야 하는 번거로움을 덜 수 있음 깃과 같은 개발 도구를 통해 빌드 및 배포의 자동화가 가능함 명시적으로 필요한 패키지나 여러 명령어를 명확히 파악할 수 있음 Dockerfile 작성법 Dockerfile은 개발자가 직접 컨테이너를 생성하고 변경사항 적용 후 이미지로 커밋하는 작업을 대신해줍니다. 따라서 위 컨테이너에서 수행해야.. 2021.09.12

• 

  프로그래머스 - 짝지어 제거하기 문제 이해 입력값으로 들어온 문자열 중 인접한 두 글자씩 짝지어 제거하는 문제 해당 문제를 봤을 때 그냥 계속 포문으로 반복 검사한다면 O(n^2)이 나올 수 있기 때문에 주의해야 한다. 따라서 이 문제를 더 효율적으로 풀기 위해서는 다른 방법을 생각해볼 필요가 있는데 스택을 이용하면 쉽고 빠르게 해결할 수 있다. for문으로 문자열을 이터레이션하며 스택의 top과 비교하며 다음과 같은 로직을 수행한다. 같을 경우 : 스택에 pop() 다를 경우 : 스택에 push() -> 파이썬 list에서는 append()를 이용 다음과 같이 구현할 경우 문자열 길이만큼 이터레이션 하기 때문에 O(n)으로 풀이할 수 있으며 해당 로직이 끝난 후 스택에 데이터가 남아있는지를 체크해 1, 0을 알맞게 넣어주면 된다. 해.. 2021.09.11

• 

  프로그래머스 - 단어 변환 간만에 풀어본 알고리즘 문제 사실 오랜만에 풀었는데 다른 서치없이 원큐에 맞춰서 기분좋아서 올리는 포스팅 begin -> target으로 단어를 최소 몇 단계로 변환 가능한지 / 혹은 불가능한지 확인하는 문제이고 단어는 words 사전에 등록되어 있는 단어로만 바꿀 수 있으며 단계 당 한 글자 씩만 바꿀 수 있다. 예시만 보더라도 이미 변환을 거쳤던 단어로 다시 가게 될 경우가 존재하므로 거쳤는 단어인지 확인 필요하며 DFS로 구현할 경우 일단 가능하지 않은 경우로 너무 깊게 빠질 수가 있으므로 BFS로 구현 해답 from collections import deque def check_diff(a, b): cnt = 0 for c_a, c_b in zip(a, b): if c_a != c_b: cnt +.. 2021.09.07