본문 바로가기

알고리즘

 (305)
[백준] 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 >=..
[백준] 2174번 : 로봇 시뮬레이션 2174번: 로봇 시뮬레이션 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 🤔 문제분석 간단한 구현문제로, 주어진 명령의 조건에따라서 수행하면된다. 특이한점은 y좌표의 그래프가 거꾸로 되어있기때문에 y좌표가 거꾸로 되어있는것만 잘 맞추어준다면 쉽게 문제를 해결 할 수 있다. 또한 방향을 결정할때에 4바퀴를 돌면 원점임으로 4를 나눈 나머지의 로테이션을 하게되면 시간복잡도를 줄일 수 있다. 💻 코드 import sys input = sys.stdin.readline A, B = map(..
[백준] 2933번 : 미네랄 2933번: 미네랄 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 🤔 문제분석 미네랄이 떨어지는것을 구현하는게 이 문제의 핵심 입니다. 미네랄이 떨어지는 후보를 만들고, 그 후보가 땅에 떨어질때까지의 최소 거리를 구한뒤 그 최소거리로 미네랄 클러스터들을 이동시킨다. 최소거리를 구하는 방법은 너비우선탐색으로 구하였는데, 모든 후보들을 큐에 넣고 땅에 닫거나 다른 클러스터에 접촉되는경우 너비우선탐색을 종료하고 최소거리를 구한다. 해당 최소거리로 떨어지는 후보들을 움직이면 된다. 💻 코드 import sys from colle..
[백준] 1113번 : 수영장 만들기 1113번: 수영장 만들기 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 🤔 문제분석 높이를 1~9 까지 순회하면서 해당 높이에서 수영장을 만들 수 있는 후보를 찾고, 그 후보중에서 만들 수 있는 가장 작은 높이의 수영장으로 만든다. 가장 작은 높이의 수영장이기때문에 다음 높이의 리터레이션에서 물이 다시 채워진다. 바깥쪽에 있는 숫자들은 땅으로 흡수되기 때문에 미리 방문처리를 해준뒤, 그룹을 찾아 나아간다. 그룹을 찾는 과정은 너비우선 탐색으로 해결하였고 해당 그룹에서 가장 작은 높이..

티스토리툴바