티스토리

아기오구의 IT 여행일기

검색하기

블로그 홈

아기오구의 IT 여행일기

baby-ohgu.tistory.com/m

ohgu IT travel diary

구독자: 2

방명록 방문하기

주요 글 목록

[백준 1461] 도서관 (Python) www.acmicpc.net/problem/1461 1461번: 도서관 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치 www.acmicpc.net 문제풀이 N, M, arr : 입력값 negative, positive : 음수, 양수 리스트 distance : 책의 원래 위치까지 가야하는 최소 걸음 수 리스트 음수와 양수를 나누고, 절대값이 큰 것부터 M개씩 나눈 후, 그 중 절대값이 가장 큰 수 만큼 움직이면 된다. 가장 절대값이 큰 거리의 경우는 돌아오지 않아야 하는 예외를 처리해주어야 한다. 1. 음수, 양수로 나누기 - 절대값이 큰.. 공감수 0 댓글수 0 2021. 2. 10.
[백준 19639] 배틀로얄 (Python) www.acmicpc.net/problem/19639 19639번: 배틀로얄 첫 번째 줄에 X, Y, M (0 ≤ X, Y ≤ 100,000, 2 ≤ M ≤ 100,000)이 주어진다. M은 짝수다. 다음 X개의 줄에는 i번째 사람과 싸웠을 때 잃게 되는 체력이 주어진다. 이 수는 0 이상 M / 2 이하의 정수이다. www.acmicpc.net 문제풀이 X, Y, M : 입력값 damage : 싸웠을 때 잃게 되는 체력 heal : 아이템을 먹었을 때 얻게 되는 체력 max_M : 초기 M 현재 체력(M) 이 초기 M (max_M) // 2 이하일 경우 포션을 먹고, max_M // 2 초과일 경우 적들과 싸우는 방식의 그리디 알고리즘으로 해결할 수 있다. 1. 현재 M 값 확인하기 - M max_M .. 공감수 0 댓글수 0 2021. 2. 5.
[백준 4889] 안정적인 문자열 (Python) www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net 문제풀이 stack을 이용해 안정적이지 않은 경우 ans를 증가하는 방식으로 해결할 수 있다. 1. 현재 문자가 '{' 이면 stack에 append하기 2. 현재 문자가 '}' 이면 stack 에서 pop하기 - stack 이 비어있을 경우 안정적이지 않은 경우이므로 ans 증가 - 이 경우 안정적이지 않은 '}' 를 바꿔줘야 하므로 '{'를 stack에 append 3. stack 이 남아있을 경우, s.. 공감수 0 댓글수 0 2021. 2. 5.
[백준 2258] 정육점 (Python) www.acmicpc.net/problem/2258 2258번: 정육점 첫째 줄에 두 정수 N(1≤N≤100,000), M(1≤M≤2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나타내는 www.acmicpc.net 문제풀이 N, M : 입력값 arr : (가격, 무게) 리스트 weight : 현재까지의 무게 same : 가격이 동일한 고기일 경우, 해당 가격만큼 결과에 더해주기 위한 변수 실버1 문제인데, 생각보다 많이 까다로운 그리디 알고리즘 문제였다. 처음에 우선순위 큐를 이용해 해결하려 하였는데, 계속 틀렸습니다를 받아서 결국 정답코드를 참고하였다. 생각보다 단순하게 생각하면 쉽게 해결할.. 공감수 1 댓글수 0 2021. 2. 4.
[백준 1041] 주사위 (Python) www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 문제풀이 N, arr : 입력값 ans : 보이는 5면 합의 최소값 min_lists : 1, 2, 3 면의 주사위의 최소값 개인적으로 굉장히 어려운 문제였다 ㅠㅠ.. 주사위와 같은 기하적인 문제 생각하는 것이 너무 어렵다... 만들어지는 완성체는 큐브 모양인데, 큐브에서 각각의 블록이 보일 수 있는 면은 1, 2, 3 개 중 하나이다. 면이 1개 보이는 블록 개수 : 4 * (N - 2.. 공감수 0 댓글수 0 2021. 1. 30.
[백준 1263] 시간 관리 (Python) www.acmicpc.net/problem/1263 1263번: 시간 관리 첫째 줄에 일의 수 N이 입력되고 다음 N(1≤N≤1,000)개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 Ti(1≤Ti≤1,000)와 Si(1≤Si≤1,000,000)가 입력된다. www.acmicpc.net 문제풀이 N : 입력값 arr : i번째 작업의 (완료시간, 작업이 걸리는 시간) 작업의 완료 시간을 기준으로 가장 늦게 완료해도 되는 작업부터 시작해서 다른 일들의 작업 시간을 탐색하면서 시작 시간을 갱신하는 그리디 알고리즘으로 해결할 수 있다. 1. 작업의 완료 시간을 기준으로 역순으로 정렬하기 2. 첫 번째 작업의 최대 시작 시간을 시작으로 나머지 작업들 확인하기 - i번째 일을 끝마쳐야 하는 시간이 현재 시간보.. 공감수 0 댓글수 0 2021. 1. 30.
[백준 1715] 카드 정렬하기 (Python) www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제풀이 N : 입력값 hq : 우선순위 큐 우선순위 큐를 이용해 가장 적은 두 수를 빼가면서 정답(ans)에 더해주면 된다. 어렵지 않은 그리디 알고리즘 문제이다. 1. 우선순위 큐에 입력하기 2. hq의 크기가 1이 될때까지 hq 안의 가장 작은 두 수를 빼면서 ans에 더해준다. - 더한 수를 다시 hq에 넣어준다. 코드 import sys import heapq if __name__ == .. 공감수 0 댓글수 0 2021. 1. 28.
[백준 1744] 수 묶기 (Python) www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제풀이 N, arr : 입력값 minus_cnt, plus_cnt, zero_cnt : 음수, 양수, 0 개수 그리디 알고리즘 문제인데, 극강의 하드코딩으로 해결하였다... 분명히 더 효율적인 방법이 많이 존재할 것이다. 예외 테스트케이스를 생각하면서 짜다보니 코드가 길어졌고, 결국 하드코딩이 되어버렸다...ㅠㅠ 1. 음수, 양수, 0 개수 세주기 2. 음수 계산하기 - 음수 개수가 짝수일 경우 짝지어서 곱.. 공감수 0 댓글수 0 2021. 1. 22.
[백준 5002] 도어맨 (Python) www.acmicpc.net/problem/5002 5002번: 도어맨 첫째 줄에 정인이가 기억할 수 있는 가장 큰 차이 X 현재 차례 사람 입장 - 그렇지 않을 경우, 다음 사람을 먼저 입장 시켜보기 => 남여 차이가 N보다 작아진다면 다음 사람 먼저 입장, 그렇지 않으면 종료 3. 1-2 과정을 반복한다. 코드 import sys if __name__ == '__main__': N = int(input()) arr = list(map(str, sys.stdin.readline().rstrip())) m_cnt, w_cnt = 0, 0 ans = 0 for i in range(len(arr)): # 남자 여자 차이가 N보다 작을 경우에는 바로 증가 if abs(m_cnt - w_cnt) < N: if .. 공감수 0 댓글수 0 2021. 1. 22.
[백준 1202] 보석 도둑 (Python) www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제풀이 N, K : 입력값 arr, bag : 보석 정보, 가방 무게 idx : arr 리스트 인덱스 백준 2109 순회강연 문제풀이와 유사한 문제이다. 우선순위 큐를 이용해서 현재 가방 무게에서 가능한 가장 큰 값어치의 보석을 더하는 그리디 알고리즘 방식으로 해결할 수 있다. 1. 보석 정보 및 가방 무게 정렬하기 2. 각 가방에 대해서, 현재 가.. 공감수 0 댓글수 0 2021. 1. 22.
[백준 2109] 순회강연 (Python) www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 문제풀이 N, arr : 입력값 hq : 우선순위 큐 idx : arr 리스트의 인덱스 우선순위큐를 이용한 그리디 알고리즘 문제이다. 가능한 가장 큰 시간인 10000일 부터 하나씩 내려오면서 해당 날에 가능한 가장 큰 돈을 더하는 방식으로 해결할 수 있다. 1. arr 리스트에서 d를 기준으로 역순으로 정렬하기 2. 가능한 가장 큰 시간인 10000일부터 1일까지 하나씩 줄.. 공감수 0 댓글수 0 2021. 1. 22.
[백준 17615] 볼 모으기 (Python) www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 문제풀이 N, arr : 입력값 red, blue : N에서 'R', 'B' 의 개수 ans : 최소 이동 횟수 cnt : 좌측, 우측의 연속된 색상의 개수 생각보다 까다로운(?) 문제였다. 그리디(Greedy) 알고리즘 문제로, 가장 좌측에서 연속된 색상의 개수, 가장 우측에서 연속된 색상의 개수, 더 적은 색상의 개수를 구하고 이 중 최소값을 출력해야 한다. 1. 각 색상의 개수.. 공감수 0 댓글수 0 2021. 1. 19.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.