본문 바로가기

전체 글

[파이썬][백준 14501][그리디] 퇴사 - 컴도리돌이 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 과정 1. 걸리는 일수(t)와 현재 일수(i)의 합이 n을 넘어가면 안되기 때문에 t+i가 n을 넘어가면 현재 일수보다 앞에 있는 일수의 값을 갖고 온다. 2. n을 넘어가지 않으면 현재 일수(i)보다 앞에 있는 일수(i+1)와 i+t 일수에 p를 더한 값과 비교해서 큰 값을 할당해 준다. 풀이 코드 import sys; input = sys.stdin.readline n = int(input()) arr = [list(map(int,input().split())) for _ in range(n)] dp = [0] * (n+ 1) for i in range(n-1,-1,-1) : t,p = ar.. 더보기
[파이썬][백준 1082][DP][그리디] 방 번호 - 컴도리돌이 1082번: 방 번호 스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해 www.acmicpc.net 풀이 방법 처음에는 아무 생각 없이 dfs로 5분만에 풀었다. 하지만 다음 테스트 케이스에서 바로 다이나믹 프로그래밍을 전환.. 10 1 1 1 1 1 1 1 1 1 1 50 1. n의 값만큼 가격 p를 입력 받고, dp의 크기를 입력 받은 m+1 만큼 할당해준다(음의 값으로). 2.가격 p를 담고 있는 room의 배열의 마지막 인덱스부터 시작하였다. 마지막 인덱스(방번호)에 해당하는 가격이 x라고 정의할 때, 반복문으로 x 부터 m+1 만큼 dp[현재 요금] = m.. 더보기
[파이썬][백준 2493][스택] 탑 - 컴도리돌이 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이 과정 아마도 스택 문제에서 괄호 문제 다음으로 많이 나오는 스택 문제 유형인 거 같다. 해당 유형을 처음 접하시는 분들은 일단은 머릿속에 배열의 순서를 생각하면서 카피하시면 왜 스택으로 사용하는지 이해가 갈 것이다. (아님 말고~) 1. 스택처럼 사용할 q라는 배열 안에 입력받은 값의 마지막 값과 인덱스를 각각 넣어준다. 그리고 출력할 answer도 따로 입력받은 n의 크기만큼 할당해준다. 2. n-2 번째 인덱스부터 첫 번째 인덱스까지 검사를 시작한다... 더보기
[파이썬][백준 2504][문자열] 괄호의 값 - 컴도리돌이 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 풀이 방법 1. 알고리즘 분류는 스택으로 되어있었지만 해당 문제를 문자열로 해결하고 싶어서 스택을 이용하지 않았다. 2. '(' 과 ')'의 각각의 개수가 다를 경우 또는 '[' 과 ']'의 각각의 개수가 다를 경우 0을 반환해주었다. (올바른 괄호 x) 3. '()' 는 2, '[]'는 3이기에 해당 값들을 replace를 통해서 '+2','+3'으로 바꿔주었다. 4. 3번을 처리해주고 나머지 '(' ,')'은 각각 '+(', ')*2'로 처리해주었다. 5... 더보기
[파이썬][백준 13460][BFS] 구슬 탈출 2 - 컴도리돌이 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 방법 1. 일단 알고리즘은 BFS를 사용하였다. 2. 큐에는 빨간색 공의 좌표(rx, ry)와 파란색의 공의 좌표(bx, by) 그리고 이동 횟수를 포함하고 있다. 3. 이동 횟수가 10이 넘어가면 break 시키고 -1 값을 반환해주었다. 4. 방문 표시는 빨간색의 공과 파란색의 공을 str으로 변환해주어서 dict에 True로 삽입하여 방문 표시를 체크하였다. 5. 상하좌우 4개의 방향으로 move 함수를.. 더보기
[c++][백준 22856][그래프탐색] 트리 순회 - 컴도리돌이 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 풀이 과정 해당 문제는 중회 순회를 하면서 이동 횟수를 출력을 해야 한다. 그래서 기본 적인 중회 순회 알고리즘에서 전체 이동 횟수 * 2에서 루트 노드에서 오른쪽 노드의 이동 횟수를 뺀 값을 출력하면 된다. 문제는 map 함수를 이용해서 부모 노드가 갖고 있는 자식 노드를 pair를 사용해서 왼쪽 자식 노드, 오른쪽 자식 노드를 표현하였다. 탐색 함수 dfs(int, bool) 탐색을 할 때는 루프 노드부터 시작하고, 해당 노드의 값이 -1일 경우 반환시킨다... 더보기
[c++][백준 21939][multiset] 문제 추천 시스템 Version 1 - 컴도리돌이 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 해당 문제는 multiset을 이용해서 풀었다. multiset을 값을 삽입할 때 작은 수부터 정렬되어서 삽입이 되는 특징이 있고, 삭제도 해당 값만 안다면 쉽게 삭제도 할 수 있기에 multiset을 이용해서 문제를 풀었다. 먼저 입력을 받을 때 문제 번호와 난이도 순으로 받는다. 나는 해당 값을 {난이도, 문제 번호} 순으로 multiset 함수에 집어넣었다. 그리고 나중에 삭제를 할 때 해당 값을 온전히 받아야 하기에 map 함.. 더보기
[c++][백준 21940][플로이드-와샬] 가운데에서 만나기 - 컴도리돌이 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 해당 문제는 플로이드 와샬로 해결하였다. 일단 플로이드-와샬이 뭔지 알아야 한다. 플로이드-와샬이란 모든 최단 경로를 구하는 방법이다. 플로이드-와샬로 문제 푸는 과정 문제를 해결하기 위한 setting 1. 크기가 n+1이 정방 2차원 배열을 사용하였고, 해당 2차원 배열의 모든 값을 생각보다 큰 수를 입력해서 넣었다. 2. 문제에서 제공하는 경로에 대한 값을 넣어 줬다. 2차원 배열[출발][도착] = 시간 3. 자기 자신으로 가는 것은 없다. 2차원 배열[i][i] = 0 4. 플로이드-와샬 2차원 배열[출발.. 더보기
728x90

티스토리툴바