Algorithm

    Algorithm/Shortest Path

    최단경로 알고리즘 풀이법 이론

    다익스트라 알고리즘 한 출발노드에서 다른 노드들 까지의 최단거리를 구하는 알고리즘 1. 출발노드 설정 2. 최단거리 테이블 초기화 (자기 자신은 0, 다른 지점까지는 max) 3. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다. 5. 3,4번을 반복한다. 구현 코드 import sys input = sys.stdin.readline() INF = int(1e9) n, m = map(int, input().split()) start = int(input()) graph = [[] for i in range(n+1)] visited = [False] * (n+1) distance = [INF] * (n+1..

    [Goldman Sachs 인터뷰] 편집 거리
    Algorithm/Dynamic Programming

    [Goldman Sachs 인터뷰] 편집 거리

    초기 접근 글자 하나하나 마다 문자를 수정하는 경우의 수를 구하고 가장 작을때의 경우를 배열에 저장해둔다. 의 문제점 : 가장 작을때가 아니라 같을 때 다음 글자에서 어떤 경우였는지를 알아야한다. 그럼 2차원배열에 저장해야하는데 이 3가지 경우의 수를 어떻게 표현할까.. 해결 아이디어 주어진 단어 두개를 2차원 배열에 표시하면 위치에 따라 3가지 경우의 수로 나눌 수 있다. 예를들어 sunday, saturday 두 단어가 주어졌다고 가정해보자. 2차월 배열로 나타내면 아래와 같다. 들어가는 정보는 original 단어에서 new 단어로 바뀔때 최소편집거리를 써준다. 예를들어) dp[0][0] ~ dp[0][8] 까지는 0(아무것도 없는 상태에서) s, sa, sat, satu, satur, ... 로 ..

    [백준 18353] 병사 배치하기
    Algorithm/Dynamic Programming

    [백준 18353] 병사 배치하기

    문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자. 이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다. 병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 ..

    [백준 14501] 퇴사
    Algorithm/Dynamic Programming

    [백준 14501] 퇴사

    문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15..

    [FlipKart 인터뷰] 금광
    Algorithm/Dynamic Programming

    [FlipKart 인터뷰] 금광

    초기접근 점화식 세우는 과정은 어렵지 않았다. 각 단계는 전 단계에서 올 수 있는 경우중에 가장큰 수 + 해당 금광수 이다. 이것을 점화식으로 나타내면 d[i][j] = max(d[i-1][j-1], d[i][j-1], d[i+1][j-1]) + data[i][j] 이다. 여기서 가장 위쪽과 아래쪽은 전단계에서 오는 경우의 수가 1개가 적다. 이것을 따로 구현하는 것 보다 data와 d 위아래에 0을 채워놓으면 훨씬 더 구현하기 쉽다. 해결 아이디어 1. 점화식 : d[i][j] = max(d[i-1][j-1], d[i][j-1], d[i+1][j-1]) + data[i][j] 2. 쉽게 구현하기 : 위아래에 0을 채워놓으면 훨씬 더 구현하기 쉽다. 정답코드 tc = int(input()) for t i..

    Algorithm/Dynamic Programming

    다이나믹 프로그래밍 문제접근

    DP조건에 맞는지 확인하는 방법 1. 큰 문제를 작은문제로 나눌 수 있다. 2. 동일한 작은 문제를 반복적으로 해결한다. 처음에 딱 문제를 볼때 접근해야하는 과정 1. 그리디, 구현, 완전탐색인지 확인한다 2. 방법이 떠오르지 않으면 DP 조건을 확인해본다. 3. 재귀로 비효율적인 완전탐색을 구현해보고 4. 작은 문제로 큰 문제 해결이 가능하면 DP로 코드개선을 한다. 일반적인 코테의 DP문제는 기본유형으로 낸다. = 점화식만 세우면 구현은 쉽다.

    [카카오코테] 가사 검색
    Algorithm/Binary Search

    [카카오코테] 가사 검색

    문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다. 그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다. 가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 qu..

    Algorithm/Binary Search

    [백준 2110] 공유기 설치

    문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는..

    [Amazon 인터뷰] 고정점 찾기
    Algorithm/Binary Search

    [Amazon 인터뷰] 고정점 찾기

    초기접근 이진 탐색으로 data[mid] == mid 인지 확인해서 왼쪽, 오른쪽으로 나누려고 시도. 그런데 왼쪽, 오른쪽 나누는 기준을 모르겠음. 어떨때 왼쪽? 어떨때 오른쪽? data[mid-1] mid + 1 이면 오른쪽 으로 나눴음 그랬더니 mid가 0일때 무한루프에 빠짐. 반복문으로 이진탐색을 구현할때 내가 실수했던 점 while start mid 이면 오른쪽으로 풀면 끝 정답 코드 n = int(input()) data = list(map(int, input().split())) start = 0 end = n-1 result = -1 while start mid: end = mid-1 else: start = mid+1 print(resu..

    [Zoho 인터뷰] 특정 원소 개수 찾기
    Algorithm/Binary Search

    [Zoho 인터뷰] 특정 원소 개수 찾기

    풀이 python의 bisect를 이용하면 1분만에 풀 수 있지만, 이진탐색의 이해를 위해 이진탐색 메소드를 직접 구현해서 풀었다. bisect 이용 풀이 from bisect import bisect_left, bisect_right n, x = map(int, input().split()) arr = list(map(int, input().split())) left = bisect_left(arr, x) right = bisect_right(arr, x) result = right - left if result == 0: print("-1") else: print(result) 이진탐색 메소드 직접 구현 풀이 def first(data, target, start, end): if start > end..

티스토리툴바