인프라 엔지니어가 꾸는 꿈

문제 링크 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net Test Case 문제 풀이 우선 입력은 줄구분 할필요 없이 그냥 list 한줄씩 입력을 받으면 된다. 그리고 for문을 통해서 각 케이스를 나눈 뒤, index 값을 고려해서 반복문을 만들어준다 i 의 범위 1~n, j 의 범위 0~i+1 인것은 각 인덱스의 최소,최대값을 생각하면 쉽게 범위를 잡을 수 있다. 마지막으로 정답 출력은 마지막줄에서 제일 큰 dp 배열의 값이 되므로 dp[n-1]의 값을 출력하면 된다. 여태까지 알고리즘 공부하고 풀이하던 방식을..

문제 링크 n × m 크기의 금광이 있다. 금광은 1 × 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하라 Test Case 입력 2 3 4 1 3 3 2 2 1 4 1 0 6 4 7 4 4 1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2 출력 19 16 문제 풀이 m 개 간격으로 입력을 받은 list를 나누서 dp 배열에 저장한다. 그 뒤에 반복문으로 각 세로줄을 검토..

문제 링크 https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net Test Case 문제 풀이 0에서1 1에서0 으로 전환되는 횟수를 카운트 한 뒤 그 횟수를 2로 나눈 값이 답이 된다. 문제를 알고 풀었다기보다 입력값을 여러 개를 넣다보니 나오는 값에서 답을 도출해낼 수 있었다. Source Code import sys input = sys.stdin.readline data = input().rstrip() ans = 1 for i in range..

문제 링크 각 자리가 숫자 0부터 9로 이루어진 문자열 S가 주어졌을 때, 숫자 사이에 'X' 혹은 '+' 연산을 넣어 만들어질 수 있는 가장 큰 수를 구하시오. Test Case 입력 02984 출력 576 입력 567 출력 210 문제 풀이 0이나 1일때는 더하고 아니면 곱하기를 하면서 예외처리 해주면 끝 Source Code import sys input = sys.stdin.readline #ValueError: invalid literal for int() with base 10: '\n' data = input().rstrip() ans = int(data[0]) length = len(data) for i in range(1,length): if ans

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr Test Case 문제 풀이 처음에 그냥 무지성으로 반복문 돌려가면서 음식 하나씩 먹다가 정답을 구하는식으로 풀었다가 효율성에서 걸렸다. 이코테 책에서 난이도 1이라고 하길래 쉽게 풀리나 했는데 역시나 틀렸다. 문제풀이는 우선순위큐를 사용해서 정렬 한 뒤 각 음식마다 남은 양을 하나씩 먹어치우는게 아니라 한 cycle씩 먹어서 최대한 빨리 답을 도출하는 것이다. 여기서 말하는 cycle 은 while문의 조건인데, 남은 음식들을 하나씩 다 먹는 것, 그러니까 첫번째 음식 부터 마지막 음식까지 먹게되는 시간을 의미하고 그 c..

문제 링크 모험가 N명이 있다. 각 모험가를 대상으로 공포도를 측정했다. 공포도가 X인 모험가는 반드시 X명 이상으로 구성해야 여행을 떠날 수 있을 때, 최대 몇개의 모험가 그룹을 만들 수 있는지를 구하시오 N = 5, 공포도 = 2 3 1 2 2 일 때, 최대 그룹수는 2 그룹이다. Test Case 입력 5 2 3 1 2 2 출력 2 문제 풀이 알고리즘 재시작. 그리디부터 다시 시작해보련다. 한 세달밖에 안지났는데도 꽤 많이 까먹어서 당황스럽다. 스터디로 시작하는거니 이번에는 꼭 완주하기. 문제는 별다를건 없고, 조건문, 반복문 잘 써서 머리굴려서 풀면 된다. Source Code import sys input = sys.stdin.readline n = int(input()) data = list(..

문제 링크 동빈이는 숨바꼭질을 한다. 1번 헛간으로부터 최단 거리가 가장 먼 헛간에 숨는다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요. N과 M 이 주어진다. (2

문제 링크 화성 탐사 기계가 존재하는 공간은 N x N 2차원 공간이며 각각의 칸을 지나기 위한 비용이 존재한다. 가장 왼쪽 칸에서 가장 오른쪽 아래 칸인 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요. Test Case 입력 3 3 5 5 4 3 9 1 3 2 7 5 3 7 2 0 1 2 8 0 9 1 1 2 1 8 1 9 8 9 2 0 3 6 5 1 5 7 9 0 5 1 1 5 3 4 1 2 1 6 5 3 0 7 6 1 6 8 5 1 1 7 8 3 2 3 9 4 0 7 6 4 1 5 8 3 2 4 8 3 7 4 8 4 8 3 4 출력 20 19 36 문제 풀이 기존에 이코테 책에서 나오던 다익스트라 스타일이 아닌 문제. 기존에 풀던 다익스트라 문제는 노드1에서 노드2로 가는 비용을 주어지..

문제 링크 선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있다. 학생 N명의 성적은 모두 다른데 다음은 6명의 학생에 대하여 6번만 성적을 비교한 결과다. 1번 학생 → 5번 학생 3 → 4 4 → 2 4 → 6 5 → 2 5 → 4 A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 한다. 위에 제시된 정보를 유추해서 순위를 정확히 알 수 있는 학생도 있고, 알 수 없는 학생도 있다. 정리하면 4번 학생보다 성적이 낮은 학생은 3명이고, 성적이 높은 학생은 2명이므로 4번 학생의 성적 순위를 정확히 알 수 있지만 다른 학생은 정확한 순위를 알 수 없다. 학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 몇명인지..

문제 링크 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Test Case 문제 풀이 모든 점에서 모든 점으로 가는 최소값을 구하는 문제. 문제를 읽고 제목을 보지않더라도 바로 플로이드 문제인걸 알아야한다. 그닥 특이점은 없지만 문제 마지막줄에 '시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.' 라는 점과 예제에서 3 -> 4 정보가 두개라는 점에서 graph[a][b] = min(graph[a][b], c) 만 신경쓰면 된다..