본문 바로가기

알고리즘/백준

 (263)
[백준] 1253번 : 좋다 1253번: 좋다 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 🤔 문제분석 N이 2000보다 작거나 같기때문에 시간복잡도는 O(n^2)으로 생각 할 수 있고 정렬 + 투포인터로 문제를 해결 할 수 있다. 입력받은 배열을 정렬한뒤 배열을 오름차순으로 순회하면서 해당수가 좋은 수인지 아닌지 판단한다. 좋은 수 인지 아닌지 판단하는 방법을 투포인터를 활용하여 해결한다. left = 0, right = len(arr)- 1로 둔다. arr[left]와 arr[right]를 더하여 현재 값과 비교를하고, 만약 값이 더 크다면 right값을 감..
[백준] 2109번 : 순회강연 2109번: 순회강연 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 🤔 문제분석 두가지의 방식으로 문제를 풀어보았습니다. 처음에 제가 풀은 방식은 유니온-파인드를 응용하여 문제를 해결하였고, 정답 판정을 받은뒤에 다른사람은 어떻게 풀었을까 풀이를 참조해보니, 우선순위큐를 활용하여 문제를 해결하신분이 있어서 풀이를 참조하였습니다. 유니온-파인드 유니온-파인으로 문제를 해결할때에는 정렬을 p의 내림차순을 정렬한뒤에 순회합니다. 파인드 : 문제에서 이야기한 d일안에 강연을 만족..
[백준] 1377번 : 버블소트 1377번: 버블 소트 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 🤔 문제분석 버블 소트가 어떻게 동작되는지 잘 파악하고 있다면 그것을 응용하여 문제를 해결 할 수 있습니다. 문제에서 요구 하는 답은 정렬된 원소와 정렬되지 않는 원소를 비교하여 정렬된 값이 정렬이전의 값 대비 왼쪽으로 가장 많이 이동한 원소로 문제를 해결 할 수 있다. 현재 코드에서 가장 큰 값을 오른쪽으로 이동시키면서 정렬을 하고있기때문에, 왼쪽으로 이동한 횟수중에서 가장 큰 값이 정답이 될 수있다. 💻 코드 i..
[백준] 17140번 : 이차원 배열과 연산 17140번: 이차원 배열과 연산 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 🤔 문제분석 배열의 구조를 잘 파악하고 있다면 쉽게 문제를 해결 할 수 있습니다. 임시의 딕셔너리를 만들어 가중치를 담아내고 딕셔너리를 순회하여 다시 배열을 만든다음, 해당 배열을 정렬한뒤 새로운 행렬을 만들어 내었습니다. R연산은 기본적으로 배열을 순회하는 방식이 똑같기때문에 최대길이를 구한뒤, 그 최대 길이만큼 도달하지 못한 행은 0을 뒤에 최대길이 만큼 추가해주었습니다. C연산은 순회하는 방식이 날라서 최대길이의..
[백준] 21609번 : 상어 초등학교 21608번: 상어 초등학교 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 🤔 문제분석 문제만 잘 이해하고 접근했다면 쉽게 풀 수 있는 문제이다. 조건에 따라서 첫번째 연산까지만 할지 두번째 연산까지만 할지 세번째 연산까지만 할지 분기시킨다. 필자는 첫번째 연산, 두번째 연산이 배열의 길이가 1 초과인경우 연산을 추가로 할것인지 분기를 시켰다. 그리고 각 조건에 맞는 결과를 얻기위해 딕셔너리를 사용하였고 딕셔너리를 배열로 전환한뒤 주어진 조건에 따라서 정렬해서 문제를 해결하였습니다. 💻 코드 imp..
[백준] 10800번 : 킬러볼 10800번: 컬러볼 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 🤔 문제분석 정렬 + 누적합 유형의 문제로 먼저 첫번째로 크기의순서, 두번째로 색상의 순서 정렬합니다. 정렬한 데이터를 순회하여 데이터를 누적하며 현재의 리터레이션에서 누적된 값을 활용하여 정답을 바로 도출 해낼 수 있습니다. 주어진 n은 200,000 이기때문에 n의 제곱으로 문제를 접근하고자 한다면 시간복잡도 판정을 받을 것입니다. 해당 문제를 풀기위해서는 적어도 nlogn 의 시간복잡도로 문제를 해결해야합니다..
[백준] 4574번 : 스노미노쿠 4574번: 스도미노쿠 4574번: 스도미노쿠 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 www.acmicpc.net 🤔 문제분석 완전탐색과 구현 유형의 문제로, 모든 타일의 경우(방문하지 않은)를 가로방향, 세로방향을 놓아보면서 문제를 해결 하였습니다. 💻 코드 import sys input = sys.stdin.readline def get_pos(LU): y, x = ord(LU[0]) - ord('A'), int(LU[1])-1 return y, x def is_range(y, x): return 8 >= y >=0 and 8 >=..
[백준] 2933번 : 미네랄 2933번: 미네랄 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 🤔 문제분석 미네랄이 떨어지는것을 구현하는게 이 문제의 핵심 입니다. 미네랄이 떨어지는 후보를 만들고, 그 후보가 땅에 떨어질때까지의 최소 거리를 구한뒤 그 최소거리로 미네랄 클러스터들을 이동시킨다. 최소거리를 구하는 방법은 너비우선탐색으로 구하였는데, 모든 후보들을 큐에 넣고 땅에 닫거나 다른 클러스터에 접촉되는경우 너비우선탐색을 종료하고 최소거리를 구한다. 해당 최소거리로 떨어지는 후보들을 움직이면 된다. 💻 코드 import sys from colle..

티스토리툴바