티스토리

아기오구의 IT 여행일기

검색하기

블로그 홈

아기오구의 IT 여행일기

baby-ohgu.tistory.com/m

ohgu IT travel diary

구독자: 2

방명록 방문하기

주요 글 목록

[백준 13460] 구슬 탈출 2 (Python) https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제풀이 BFS로 해결할 수 있는데, 이때 전형적으로 2차원 배열로 탐색하는 것이 아니라 4차원 배열로 탐색해야 한다. (빨강구슬 x, y 파란구슬 x, y) 1. 큐에 (빨강구슬 x, 빨강구슬 y, 파랑구슬 x, 파랑구슬 y) 추가 2. BFS 를 통해 아직 탐색하지 않은 영역 탐색 - 벽이나 구멍을 만날 때 까지 특정 방향으로 계속 이동 (mo.. 공감수 0 댓글수 0 2022. 5. 3.
[백준 1918] 후위 표기식 (Python) (중위 표기식 -> 후위 표기식 변환 문제) https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 문제풀이 cmd : 입력값 stack : 괄호와 연산자를 저장할 stack list ans : 결과 list 스택을 이용해서 연산자의 우선순위를 결정해 결과 list에 넣는 방식으로 해결하였다. 1. A~Z 알파벳일 경우 ans에 바로 추가한다. 2. '(', '+', '-'. '*', '/' 연산자일 경우 stack에 추가한다. - '*' 나 '/' 일 경우, 연산자 우선순위에 의해서 .. 공감수 0 댓글수 0 2021. 10. 3.
[백준 15683] 감시 (Python) www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제풀이 N, M, board : 입력값 cctv, cctv_n : CCTV 좌표 리스트, CCTV 개수 ans : 최소 사각지대 개수 check : 방문 여부 확인 재귀를 이용해 모든 CCTV를 4방향 돌리면서 감시 가능 영역을 만들어보는 브루트포스 방식으로 해결할 수 있다. 1. CCTV 좌표 및 개수 세주기 2. 재귀를 이용해 모든 CCTV의 감시 영역 탐색하기 - CCTV 종류에 따라서 방향 .. 공감수 0 댓글수 1 2021. 2. 14.
[백준 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.
[백준 1194] 달이 차오른다, 가자. (Python) www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제풀이 N, M, board : 입력값 check : 특정 key를 가지고 방문 여부 체크 비트마스크를 이용한 BFS 문제였다. 평상시 비트마스크를 싫어하였는데 이 문제를 통해 조금은 친해(?)진 것 같다... 비트마스크를 활용한 풀이에 대한 설명은 아래 참고한 코드 URL 에 자세히 설명되어 있다. 1. '0' 부터 BFS 탐색 - 새롭게 이동할 곳이 '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.
[백준 15686] 치킨 배달 (Python) www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제풀이 N, M, board : 입력값 chicken : 치킨집 좌표 리스트 tmp_board : 치킨집이 없는 board (집과 빈 공간만 있는 2차원 리스트) dist : 치킨집을 기준으로 최단 이동 거리 Combination(조합) 으로 치킨집을 M개 선택하여 BFS를 통해 각 집까지의 거리를 탐색하는 방식으로 해결할 수 있다. 1. Combination을 통해 M개의 치킨집 선택하.. 공감수 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.
[백준 3190] 뱀 (Python) www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제풀이 N, K, L : 입력값 command : 명령 d : 방향 time : 현재 시간 cmd_idx : command 리스트의 원소 탐색을 위한 인덱스 특별한 알고리즘 필요없이 단순히 주어진 조건대로 잘 구현(?) 하기만 하면 해결할 수 있는 문제이다. 한 가지 주의할 것이, 사과가 없는 빈 공간으로 뱀의 머리가 이동할때, 몸 길이가 변하지 않는 것이다. 이 부분만 주의하면 문제없이 해결할 수 있다. board.. 공감수 0 댓글수 0 2021. 1. 27.
[백준 1939] 중량제한 (Python) www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 문제풀이 N, M : 입력값 adj_list : 섬간 인접리스트 start, end : 공장이 위치한 섬의 번호 mx, mn : 이분 탐색 범위 BFS와 이분 탐색을 활용한 문제였다. 처음 접해보는 유형이었고, 새로운 방식의 아이디어 및 풀이를 얻을 수 있는 문제였다. 1. 이분 탐색을 통해 가능한 중량을 찾는다. - BFS 탐색을 통해 start 섬에서 end .. 공감수 0 댓글수 0 2021. 1. 27.
[백준 2589] 보물섬 (Python) www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제풀이 N, M, board : 입력값 check : 특정 노드 방문 여부 dist : 특정 노드까지의 거리 q : BFS를 위한 deque 모든 육지에 대해서 BFS를 통해 갈 수 있는 최대 거리를 구해주면 쉽게 해결할 수 있다. 1. 특정 좌표가 육지라면 BFS 시작한다 - 해당 위치에서 상하좌우 중 육지이면서 아직 방문하지 않았다면 방문 2. 모든 육지에 대해 1의 과정을 반복한다 코드 import sys .. 공감수 0 댓글수 0 2021. 1. 25.
[백준 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.
[백준 9081] 단어 맞추기 (Python) www.acmicpc.net/problem/9081 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net 문제풀이 단순 구현문제로, next_permutation 함수를 이용하여 쉽게 해결할 수 있다. 코드 import sys def next_permutation(a): i = len(a) - 1 while i > 0 and a[i - 1] >= a[i]: i -= 1 if i = a[j]: j -= 1 a[i - 1], a[j] = a[j], a[i - 1] j = len(a) - 1 while i <.. 공감수 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.
[백준 11559] Puyo Puyo (Python) www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 문제풀이 BFS를 이용한 구현문제이다. 주어진 조건만 잘 구현하면 쉽게 해결할 수 있다. 1. 뿌요 탐색 및 뿌요 부수기 - 현재 위치에서 동일한 색상의 뿌요가 4개 이상일 경우 뿌요를 부신다. 2. 1의 과정에서 없앤 뿌요가 있으면 뿌요를 내려준다. - 없앤 뿌요가 없으면 더 이상 진행할 것이 없으므로 결과를 바로 출력한다. 코드 보면 쉽게(?) 이해할 수 있다. 코드 import s.. 공감수 0 댓글수 0 2021. 1. 22.
[백준 1360] 되돌리기 (Python) www.acmicpc.net/problem/1360 1360번: 되돌리기 첫째 줄에 명령의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 명령과 수행한 시간이 주어진다. 항상 시간이 오름차순으로 주어지고, type c에서 c는 알파벳 소문자, undo t에서 t는 1보다 크거나 같 www.acmicpc.net 문제풀이 N : 입력값 cmd, ch, t : 입력값 q : 현재까지의 시간과 타이핑한 텍스트 저장 리스트 [(시간, 텍스트)] now : 현재 텍스트 따로 알고리즘이 필요없는, 그냥 문제에서 요구한대로 구현만 하면 해결할 수 있는 문제이다. 몇몇 예외 테스트케이스만 조심하면 쉽게 해결할 수 있다. 1. cmd가 type일 경우 - 현재 텍스트(now)에 ch 추가 - q에 시간(t)과 텍스트(no.. 공감수 0 댓글수 0 2021. 1. 21.
[백준 16947] 서울 지하철 2호선 (Python) www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 문제풀이 N : 입력값 adj_list : 양뱡향 인접리스트 check : 노드 방문 여부 체크 dist : 최소 방문 거리 DFS를 통해 사이클을 찾고, BFS를 통해 특정 노드에서 사이클 까지의 거리를 계산하는 방식으로 해결할 수 있다. check를 통해 방문한 노드(check[x] = 1), 방문하지 않은 노드(check[x] = 0), 사이클에 속한 노드(check[x] = 2.. 공감수 2 댓글수 0 2021. 1. 20.
[백준 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.
[백준 20181] 꿈틀꿈틀 호석 애벌레 - 효율성 (Python) www.acmicpc.net/problem/20181 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 문제풀이 N, K, arr : 입력값 dp : i번째 까지의 최대 탈피 에너지 lmax : 애벌레가 먹기 시작하는 구간에서 지금까지 얻었던 최대 탈피 에너지 tmp : 현재 만족도 left, right : 투 포인터 굉장히 까다로운 문제였다. 현재 만족도에 대해서 투포인터를 진행하면서 탈피에너지에 대한 정보도 저장해야 한다. 따라서 투포인터(Two-Pointer)와 DP(Dynamic Pr.. 공감수 0 댓글수 0 2021. 1. 9.
[백준 3151] 합이 0 (Python) www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 문제풀이 N, arr : 입력값 left, right : 투 포인터 goal : 특정 1개의 원소를 선택하고, 그 수의 음수값 mx_idx : 정렬 후 arr[right]와 동일한 수를 가진 원소의 최소 인덱스 세 용액 문제의 응용이라고 생각한다. 알고나면 어렵지 않은 문제인데, 저 알기까지의 과정이 너무 고통스러웠다 ㅠㅠ.. 특정 1개의 원소를 선택 후, 투 포인터(Two-Pointer)를 통해서 세 원소의 합이 .. 공감수 0 댓글수 0 2021. 1. 8.
[백준 10025] 게으른 백곰 (Python) www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 문제풀이 N, K, arr : 입력값 left, right : 양동이가 위치한 가장 좌측과 우측 start, end : 투 포인터 now : 현재 얼음의 양 양동이의 가장 좌측과 우측을 미리 구하여 해당 범위 안에서 투 포인터(Two-Pointer)를 통해 얼음의 최대 양을 구하는 방식으로 해결하였다. 1. 입력을 받으면서 양동이의 가장 좌측과 우측(left, right)을 구한다. 2. 투 포인터를 통해 얼음의 양을 갱신한다. - .. 공감수 0 댓글수 1 2021. 1. 6.
[백준 1253] 좋다 (Python) www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제풀이 N, arr : 입력값 left, right : 투 포인터 tmp : i 번째 원소를 제외한 arr 리스트 괜히 어렵게 생각하려다 해결하는데 오래걸렸다. 단순하게 특정한 1개의 원소를 골라서, 해당 원소를 제외한 리스트에서 투 포인터(Two-Pointer)를 통해 두 원소의 합이 선택한 원소와 같은지 비교하는 방식으로 해결할 수 있다. 1. arr 리스트를 정렬한다. 2. 0부터 N - 1 까지 반복문을 통해 특정 원소(arr[i.. 공감수 0 댓글수 0 2021. 1. 5.
[백준 15831] 준표의 조약돌 (Python) www.acmicpc.net/problem/15831 15831번: 준표의 조약돌 첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조 www.acmicpc.net 문제풀이 N, B, W, arr : 입력값 w_cnt, b_cnt : 현재 수열에서 W와 B의 개수 q : 현재 수열 다른 투 포인터(Two-Pointer) 문제와 큰 차이 없는 문제였지만, 예외 케이스를 처리해줘야 하는 문제였다. 6 0 0 BBBBBB 위와 같은 테스트케이스에서 q(현재 수열)에 들어갈 수 있는 값이 존재하지 않는데, q.popleft() 하기 떄문에 런타임 에러가 났다. 1. .. 공감수 0 댓글수 0 2021. 1. 5.
[백준 20366] 같이 눈사람 만들래? (Python) www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 문제풀이 N, arr : 입력값 left, right : 투 포인터 tmp : 두 눈사람의 키 차이 세 용액 문제에서 조금 더 나아가서 네 용액(?) 문제인 것 같다. 미리 두개의 원소를 지정하고, 해당 두 원소 사이에서 투 포인터(Two-Pointer)를 통해 두 눈사람의 키 차이의 최소값을 구하는 것을 반복하면서 해결할 수 있다. 1. 배열 arr를 정렬해준다. (원본 배열의 .. 공감수 2 댓글수 0 2021. 1. 5.

문의안내

티스토리
로그인
고객센터

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