본문 바로가기

전체 글714

[백준 1015] 수열 정렬 [Python] 풀이 입력받은 배열 A를 오름차순으로 정렬(sorted_A)했을 때, 원본 배열의 요소가 정렬된 배열에서 몇 번째에 위치하는지 구하는 문제다. N은 최대 50으로 모든 요소에 대해 배열을 전부 선형탐색해도 O(N^3) 제한시간 내 통과할 수 있다. 동일한 원소에 대해서도 순서는 별도로 부여되므로, 이미 찾은 요소는 범위를 벗어난 수(-1)로 채워넣어 탐색이 되지 않도록 해주자. 소스코드 소스코드 보기 출처 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 2023. 10. 3.
[백준 15678] 연세워터파크 [C++] 풀이 정수 K가 적혀있는 N개의 징검다리에 대해 징검다리를 건너며 얻을 수 있는 최대값을 구하는 문제다. 문제에서 주어진 조건 중 아래와 같은 조건이 있다. N개의 모든 징검다리에 순서대로 1 ~ N의 번호를 붙인다. U번 징검다리에서 V번 징검다리로 점프하기 위해서는, U와 V의 차이가 미리 정해진 값 D 이하여야 한다. 어떤 징검다리도 두 번 이상(한 번을 넘게) 밟을 수는 없다. 때문에, 징검다리의 양 끝이 아닌 중간에서 시작하더라도 왼쪽 또는 오른쪽 방향으로만 진행할 수 있다. 서로 다른 방향이더라도 결국 반대 방향의 부분집합에 속하는 영역이기 때문에 징검다리를 한 방향으로 진행한다고 가정하고 dp로 풀이할 수 있다. 진행 방향은 1번부터 N번이며 D씩 이동한다면 모든 징검다리가 탐색 대상이다. .. 2023. 9. 30.
[백준 28490] Area [Python] 풀이 N개의 가로와 세로의 길이를 입력받아 가장 큰 넓이를 출력해주는 문제다. 소스코드 소스코드 보기 출처 28490번: Area Stuart has $n$ rectangular frames, which are numbered from $1$ to $n$. Frame $i$ is a rectangle with height $h[i]$ and width $w[i]$. The size of a frame is the area that it covers. Stuart wants you to help him find the area covered by the largest size fram www.acmicpc.net 2023. 9. 10.
[구름톤 챌린지] 17일차 - 통신망 분석 풀이 N개의 정점에 대해 컴포넌트의 밀도가 높은, 하나로 연결된 정점을 간선으로 나눈 수치가 최대인 컴퓨터들의 목록을 출력해주면 되는 문제다. 연결만 되어있다면 동일한 컴포넌트로 볼 수 있으니 양방향그래프로 초기설정을 해주자. 이제 모든 정점에 대해 하나의 컴포넌트에 속하는 컴퓨터들의 목록을 저장해 반환해주는 bfs를 실행하자. 방문하지 않은 정점들에 대해 연결된 모든 정점을 set인 path에 추가해주는 방법으로 중복을 제거했다. 하나의 컴포넌트에 속한 컴퓨터를 모두 찾았다면, 해당 컴퓨터와 연결된 컴퓨터가 컴포넌트에 존재하는 만큼 간선의 개수를 계산하자. 반환받은 컴포넌트 내 컴퓨터 목록과 밀도를 이용해 문제에서 주어진 조건대로 알맞는 컴포넌트로 갱신 후 탐색이 모두 종료되었을 때 조건에 부합하는 컴.. 2023. 9. 10.
[백준 26495] Big Number [Python] 풀이 입력받은 양의 정수를 큰 수로 출력해주면 되는 문제다. 2, 5, 6 을 큰 수로 출력할 때 "2 "와 같은 형식이 아니라 "2"로 출력해주어야 한다. dict에 각 양수에 맞는 큰 수를 문자열 리스트 형태로 저장해두고 출력해주는 방식으로 풀이했다. 소스코드 소스코드 보기 출처 26495번: Big Number One of the professors at PLU has had a lot of trouble reading student programs. He just cannot read that small print. Your job is to write a program that will read a positive integer and rewrite the number in large block.. 2023. 9. 7.
[구름톤 챌린지] 16일차 - 연합 [Python] 풀이 N개의 섬에 대해 양방향으로 연결된 그룹의 개수를 구하는 문제다. 입력시에는 단방향으로만 입력받아야 한다. 1 ~ N 번 노드에 대해 방문하지 않은 노드에대해 bfs를 해주면 된다. 정점 u부터 시작해 연결 가능한 모든 정점을 확인하며, 양방향인 경우에만 방문표시와 함께 다음 탐색대상으로 포함시키면된다. 더 이상 탐색할 수 있는 정점이 없다면 bfs를 종료하며 1을 반환해 그룹의 개수를 증가시키면 된다. 출처 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 2023. 9. 6.

티스토리툴바