본문 바로가기

코딩테스트 문제풀이/beakjoon64

[Google 인터뷰] 못생긴 수 [Google 인터뷰] 못생긴 수 다이나믹 해당문제는 설명이 잘되어 있는 https://leeyeongeol.github.io/%EC%9D%B4%EC%BD%94%ED%85%8C/%EC%9D%B4%EC%BD%94%ED%85%8C-%EB%AA%BB%EC%83%9D%EA%B8%B4-%EC%88%98/ 를 참고하여 작성하였음 [문제] [과정] 이 문제는 가능한 못생긴 수를 앞에서부터 하나씩 찾는 방법으로 해결할 수 있다. 못생긴 수들은 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …]와 같이 끊임없이 존재한다. 이때 못생긴 수에 2, 3 혹은 5를 곱한 수 또한 ‘못생긴 수’에 해당한다는 점이 포인트이다. 2의 배수 변수, 3의 배수 변수, 5의 배수 변수에 대하여 각각 ‘가장 작은 못생긴.. 2022. 6. 29.

[백준] 18353 병사 배치하기 백준 18353번 병사 배치하기 다이나믹 / 가장 긴 증가하는 부분 수열 O(nlogn) [문제] 고려해야 할 부분은 항상 전투력이 높은 병사순으로 내림차순 이라는 것 배치 과정에서 특정한 위치에 있는 병사를 열외시켜서 남아있는 병사의 수가 최대가 되도록 하는 것 [과정] '가장 긴 증가하는 부분 수열(LIS)'을 이용해서 풀이 내림차순을 요구하는 문제이기 때문에 점화식의 부등호 방향을 바꾸어주면 됨 dp는 모두 1로 초기화 하고 입력받은 병사들의 전투력을 저장 점화식: 모든 0 soldiers[i] dp의 최댓값 -> 가장 긴 내림차순 부분 수열의 길이 전체 병사의 수인 N에서 빼주기 [소스코드] # 병사 배치하기 n = int(input()) data = list(map(int, input().spl.. 2022. 6. 29.

[백준] 14501 퇴사 백준 14501번 퇴사 다이나믹 프로그래밍 / 브루트포스 [문제] 실버3문제였지만 다이나믹이 개인적으로 꽤 까다로운 것 같다. 이 부분에서 핵심이 되는 부분은 상담 시간이 n을 초과하는지 비교하는 부분과 금액(p)값의 최댓값이 되도록 갱신하는 부분이다. [과정] 우선 거리비교를 위해서 역순으로 비교를 해야한다. dp라는 새로운 1차원 배열을 생성하여 역순으로 진행했을 때 dp[i]에 금액의 최댓값이 저장된다. 1차원 배열(dp)를 n만큼 거리0으로 초기화 역순으로 반복문 진행 dp[i]에 '현재 위치의 금액 + 현재 필요한 시간을 뺀 dp[i]의 값'과 이전의 dp[i]값 중 최솟값을 저장 dp의 첫번째 원소를 출력 [소스코드] # 퇴사 n = int(input()) data = [] for i in r.. 2022. 6. 29.

[백준] 11404 플로이드 백준 11404번 플로이드 그래프 이론 / 플로이드 워셜 [문제] 모든 도시의 최단거리 출력문제이므로 한점에서 이동하는 다익스트라보다는 플로이드 워셜이 더 알맞다. 입출력 예시) '1 4 1'과 '1 4 2'가 서로 경로가 겹치는 것이 보인다. 해당 경우에 거리비용이 더 작은 것으로 갱신하는 작업이 별도로 필요하다. [과정] 플로이드 알고리즘은 약간 dfs/bfs + dp 문제인 것 같다. 점화식을 사용해서 2중 반복문을 사용하면 다익스트라보다 쉽게 구현할 수 있다. 거리 2차원 배열(graph)을 최대값(1e9)로 초기화 2중 반복문으로 자기자신의 경로는 0으로 초기화 간선정보를 저장 해당 그래프 좌표의 거리비용과 모든 경우의 수의 거리비용 중 최솟값으로 해당 좌표의 거리비용(graph[a][b])을 .. 2022. 6. 29.

[백준] 1932 정수 삼각형 [백준] 1932번 정수 삼각형 다이나믹 프로그래밍 [문제] 저번주에 풀었던 '금광'문제와 매우 유사함 삼각형 모양이라는것을 확인하고 하나의 좌표에서 위의 왼쪽과 위의 오른쪽을 비교하여 더 큰것을 더하면 됨 [과정] 우선 그림을 보자. 1의 기준에서는 왼쪽이 3이고 오른쪽이 8임 하지만 8의 기준에서는 왼쪽이 없고 오른쪽이 3임 이와 같이 0의 기준에서는 왼쪽이 8이고 오른쪽이 없음 각 위치에서 한칸 위의 값(왼,우)를 비교하여 해당 값을 갱신하면 됨! 정수 삼각형 입력 값을 2차원 배열로 저장 1번째 줄부터 윗 칸과 비교를 하기 위해 1번부터 n번까지 반복문 실행 삼각형 특성상 아랫칸은 윗칸보다 1이 크므로 i+1만큼 반복문 실행 왼쪽 비교 -> 첫번째 인덱스이면 left값은 0으로 초기화 왼쪽 비교 .. 2022. 6. 21.

[Flipkart] 금광 [Flipkart] 금광 다이나믹 프로그래밍 풀이 깃허브: https://github.com/tpqls0327/Algorithm/tree/master/Interviews [문제] n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요. [입력 조건] 1. 첫째 줄에 테스트 케이스 T가 입력됩니다. (1 2022. 6. 19.

[백준] 2110 공유기 설치 백준 2110번 공유기 설치 이분 탐색 / 매개 변수 탐색 [문제] 좀 어려웠던 문제 해당 알고리즘을 떠올리는 방법이 어려웠다. 풀이시간도 50분으로 길던것이 이해가 갔다. 시간 더 필요할듯..ㅋㅋ '해당 풀이는 답지를 참고하였음' '가장 인접한 두 공유기 사이의 거리를 최대로 하는 값'을 구하기 [과정] 데이터 정렬(오름차순) 수행 이진탐색 수행 임의로 mid값((start + end) // 2)을 가장 인접한 두 공유기 사이로 설정 해당 mid값만큼 이동하며 공유기 설치 만약 공유기 설치 개수가 c개 이상이 되면 현재 공유기 설치 개수 저장 후 '가능한 최소 거리'를 1 증가 만약 c개의 공유기를 설치 할 수 없다면 '가능한 최대 거리'를 1 감소 결과(result) 출력 한줄 정리 - gap(mid.. 2022. 6. 17.

[Amazon 인터뷰] 고정점 찾기 [Amazon 인터뷰] 고정점 찾기 이진 탐색 [문제] 선형탐색이 아닌 이진탐색으로 푸는 문제 문제가 이미 오름차순으로 정렬되어 있기에 그대로 탐색을 진행하면 됨. 고정점은 최대 1개만 존재함을 체크 -> 발견 즉시 반복문을 나오게 됨 [과정] 시작점과 끝점을 저장 반복문 실행 시작점의 값과 해당 인덱스의 데이터 값이 같은지 확인 같다면 break 끝점의 값과 해당 인덱스의 데이터 값이 같은지 확인 같다면 break 결과출력 [소스코드] # 고정점 찾기 2022-06-13 from bisect import bisect_left, bisect_right n = int(input()) data = list(map(int, input().split())) result = '' for i in range(n):.. 2022. 6. 17.

이전 1 2 3 4 5 6 7 8 다음

티스토리툴바