코딩테스트

문제https://www.acmicpc.net/problem/2979 문제 접근예제 1을 기준으로 문제를 확인해보자. 1대 주차 -> 한대 당 5원2대 주차 -> 한대 당 3원3대 주차 -> 한대 당 1원 트럭이 주차장에 있는 시간들을 모두 계산해보면, 아래 이미지와 같다.  이렇게 3대의 주차 시간을 모두 고려하면, 위와 같이 주차장에 현재 몇 대가 있는지 알 수 있다.  이 과정을 어떻게할지 고민하다가, 최대 시간이 길지 않아(100) 그냥 배열로 만들어, 주차장에 몇 대가 있는지 판단하기로 하였다. 1. res 배열을 100개의 0배열로 만든다. 이 배열은 각 분 당 주차장에 차가 몇 대 있는지 나타내는 배열이다. res = [0] * 100 2. 주차장에 있는 시간을 순회하며, 차가 주차장에 있는..

문제https://www.acmicpc.net/problem/13305 문제 접근전체 주유소 이용 가격을 최소화하기 위해서는 가장 싼 곳에서 가장 많이 구매하여 가장 많이 이동해야한다. 주유소의 기름 가격을 순회하며, 가장 싼 곳의 주유소를 찾고, 해당 주유소의 가격이 가장 싸다면 도시를 이동할 만큼의 기름을 구매한다. 만약, 해당 주유소의 가격이 최소 금액보다 싸지 않다면 최소 금액의 주유소에서 최대한 많이 구매하도록 한다.  # 도시의 개수N = int(input())# 인접한 두 도시를 연결하는 도로의 길이를 왼쪽부터 제공length = list(map(int, input().split()))# 주요소의 리터당 가격price = list(map(int, input().split()))answer =..

문제 https://www.acmicpc.net/problem/1541 문제 접근문제의 입력은 총 3가지 이다. 예제 1의 경우55-50+40 을 55-(50+40)으로 묶으면 원하는 출력값인 -35가 도출된다.  예제 2의 경우, 10+20+30+40을 괄호없이 그냥 더하면 원하는 출력값인 100이 도출된다.  예제 3의 경우에도 2와 같다.  즉, '-' 뒤에 이어지는 '+' 연산을 모두 괄호로 묶어, 가장 큰 값을 뺄셈하게 되면 값이 작아지게 된다.  풀이 방법55-50+40을 예로 들자. 1. 먼저, '-' 를 기준으로 값을 나눈다. '55', '50+40' 2. '+' 기호가 있는 값은 덧셈 연산을 수행하고, '+' 기호가 없으면 그냥 정수로 변환한다.  3. 2에서 구한 값을 sum_list에..

문제https://www.acmicpc.net/problem/11399 문제는 길지만, 요약하자면 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하면 되는 것이다.  풀이import sys# 문제 입력받기N = int(input())lines = list(map(int, sys.stdin.readline().split()))lines.sort()sum_list = [0]# 누적합 구하기for line in lines: tmp = line + sum_list[-1] sum_list.append(tmp) print(sum(sum_list)) 먼저, 인출 시간이 적은 사람 순으로 정렬을 한 후, 각 사람마다 걸리는 시간을 합한다. 즉, 입력이 3 1 4 3 2 로 주어질 때, 1 2..

문제 설명https://www.acmicpc.net/problem/1931 그리디 알고리즘에 관한 문제이다.  문제 접근문제는 각 회의가 겹치지 않게 하면서 가장 많은 회의의 개수를 찾는 것이다. 어떻게 해야할까? 1. 회의 시작 시간을 기준으로 가장 빠른 회의 선택: 이 경우 회의 시작 시간은 빠르지만, 진행 시간이 길다면 다른 회의를 선택하지 못하므로 옳지 않다. ex) (0, 10) 과 (1, 2), (2, 4) 가 있으면, (0, 10)은 좋지 않은 선택지이다.  2. 회의 진행 시간이 짧은 기준으로 선택: 회의 진행 시간에 따라 정렬을 하면, 시작시간과 종료시간이 뒤죽박죽된다. ex) (0, 3), (1, 5), (2, 3) -> (2, 3), (0, 3), (1, 5) 3. 회의 종료 시간을 ..

이번에는 시뮬레이션과 완전 탐색에 중점을 둔 구현 문제에 대해 알아보겠습니다.  구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정  (사실상 모든 문제가 구현 문제라고 생각할 수 있습니다;^^)그러나 일반적으로 구현 유형의 문제는 문제에서 요구하는 내용이 구현에 초점이 맞춰있거나, 구현이 어려운 문제를 의미합니다. 즉, 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭합니다. 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제적절한 라이브러리를 찾아서 사용해야 하는 문제이러한 구현 문제의 경우, 다양한 라이브러리를 익히는 등 많은 연습이 필요한 문제입니다. 행렬은 파..

그리디 알고리즘이란? 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.  그리디 알고리즘은 한국어로 탐욕법이라고 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구하는데요, 그리디 알고리즘의 해법은 그 정당성 분석이 중요합니다. 즉, 단순히 가장 좋아 보이는 것을 반복적으로 선택하는 것만으로도 최적의 해를 구할 수 있는지를 검토하는 것이 필요합니다.   아래와 같은 예시 문제가 있습니다. 루트 노드(5)부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶을 때, 최적의 해는 무엇인가요? 직관적으로 확인할 수 있듯이, 5 -> 7 -> 9로 이동하면 노트..

문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/161989 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  처음 시도한 풀이## 틀린 풀이def solution(n, m, section): answer = 0 # 페인트가 칠해진 구역은 1로, 페인트가 벗겨진 구역은 0으로 지정 wall = [1] * n for i in section: wall[i-1] = 0 # wall 안에 0이 있으면 페인트질 반복 while wall.count(0) >..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/176963 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 def solution(name, yearning, photo): # photo의 길이만큼 기본 answer 배열 생성 answer = [0] * len(photo) # 인물과 추억 점수로 딕셔너리 생성 score_dic = dict(zip(name, yearning)) for p in range(len(photo)): # 각 사진 중 정보가 있는 인물에 대해 추억점수를 더함..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/120921 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 처음 풀이(틀림) def solution(A, B): answer = 0 # B에서 A 첫번째 글자는 어디에 위치하는가? idx = B.index(A[0]) # B에서 A의 첫 번째 글자부터 문자열과 그 전의 문자열을 합쳐서 A와 같으면 idx 값을 answer로 if (B[idx:] + B[:idx]) == A: answer = idx else: answer = -1 ret..