개발자 퉁이리

https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 자료 구조 세그먼트 트리 분할 정복 스택 ⊙ 문제 접근 과정 왼쪽부터 차례대로 검색해준다. 스택에 최솟값을 넣어주고 그 값이랑 비교했을 때, pop을 하며 최댓값을 찾아가면 된다. 고민하다가 코드로 구현이 힘들어 인터넷을 활용한 문제다. ⊙ 문제 풀이 from collections..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 자료 구조 스택 ⊙ 문제 접근 과정 힌트를 보고 이해했다. 만약 문제가 이해하기 힘들면 힌트를 바로 보자. 힌트: 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, pu..

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 자료 구조 큐 ⊙ 문제 접근 과정 우선 큐를 하나 만들어주어 거기에 1부터 N까지 수를 넣어준다. 그리고 입력받은 K가 되기 전까지 요소를 빼서 뒤로 넘겨주고, K가 되면 K를 result 배열에 넣어준다. 그렇게 q가 빌 때까지 반복한다. 그리고 형식에 맞추어서 출력만 해주면 된다. ⊙ 문제 풀이 from collections import deque N, K = map(int, input().split()) q =..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 자기 자신을 선택하면 혼자 팀을 구성할 수 있고, 원을 이루어 모든 사람이 선택되면 모든 학생들이 동일한 팀을 꾸릴 수 있다. 즉, 조건은 사이클이다. 사이클이 생기면 팀이 생기는데 사이클 판별을 dfs로 해주었다. ⊙ 문제 풀이 import sys sys.setrecursionli..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 빨간 구슬의 좌표와 파란 구슬의 좌표를 담을 변수를 설정해준다. 그리고 현재 빨간 구슬의 좌표와 파란 구슬의 좌표를 찾아내어 변수에 저장해주고 큐에 추가한다. 그리고 bfs를 돌려준다. 10번 이상으로 움직였을 시는 멈추고..

https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 기하학 다각형의 넓이 ⊙ 문제 접근 과정 학창 시절 수학 시간에 배웠던 '신발끈 공식' 신발끈 공식을 사용하면 바로 풀 수 있다. 🔎 신발끈 공식이란? 적색 화살표가 지나는 원소들의 곱의 합에서 한 청색 화살표가 지나는 원소들의 곱이 합을 빼어 절댓값을 취하면 된다. 사진에 보면 x는 x좌표이고 y는 y좌표를 말한다. 한 가지 주의해야 할 점은 마지막에 첫 번째 ..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 위상 정렬 ⊙ 문제 접근 과정 기본적으로 위상 정렬 알고리즘을 사용한다. 이 문제에서는 순서 입력을 아래와 같이 입력받는데 이 부분만 처리해주면 바로 풀린다. 가수의 수 -> 가수 순서 예를 들어 예제와 같이 3 1 4 3이 들어오면 가수의 수는 3이고 순서는 1 4 3이다. 그래서 나는 이것을 list로..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 bfs를 돌려서 그림의 총 개수와 가장 넓은 그림을 찾아내면 된다. bfs를 돌릴 때, 내장 count는 그림의 넓이다. 그 값과 기존에 저장된 큰 그림의 넓이와 비교해서 더 큰 값을 max에 저장해준다. 이때 방문을 했는지 안 했는지 알기 위해 visited 리스트..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 자료 구조 시뮬레이션 덱 큐 ⊙ 문제 접근 과정 뱀의 머리와 꼬리를 알기 위해서 큐를 사용한다. 아래에 왜 큐를 사용해야 하는지 설명하겠다. 만약 다음 칸에 사과가 있다면 뱀의 길이는 증가한다. 사과가 존재하지 않으면 뱀의 길이는 유지된다. 그렇다는 말은 사과가 존재하면 뱀의 꼬리는 움직이지 않고, 사과가 존재하지 않으면 꼬리는 움직여야 ..

https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 수학 구현 브루트포스 알고리즘 정수론 중국인의 나머지 정리 ⊙ 문제 접근 과정 값이 같을 때까지 무지성으로 1 올려주면 된다. 범위가 넘으면 다시 1로 초기화만 시켜주자 ⊙ 문제 풀이 import sys input = sys.stdin.readline E, S, M = map(int, input().split()) x, y, z = 1, 1,..