본문 바로가기
728x90
반응형

백준 알고리즘55

[정렬 알고리즘][파이썬][백준 10989] 정렬 알고리즘 기초 문제 팁 정렬 알고리즘 기초 문제들을 풀면서 어느정도 문제를 푸는 방식에 대한 감을 잡았다. 정렬 문제 풀이의 일관성을 위해서 내가 문제 푸는 방식을 정리해보려한다. 먼저 파이썬에서는 기본적으로 정렬을 하는 함수를 제공한다. 바로 sort와 sorted 이다. sort와 sorted li= [1, 3, 6, 2, 3, 4] 이러한 리스트가 있다고 하자. li를 원본 리스트라고 하고 이 원본 리스트 자체를 정렬하고 싶다면 li.sort()를 사용한다. 정렬 후 print(li)로 원본 리스트를 출력해보면 출력 [1, 2, 3, 3, 4, 6] 제대로 출력되는 모습을 볼 수 있다. sorted의 경우 원본 리스트를 정렬하는 것이 아닌 정렬된 새로운 리스트를 반환하는 함수이다. li2 = sorted(li) 와 같이 .. 2023. 2. 7.
[백준 10799][파이썬] 쇠막대기 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net https://growth-coder.tistory.com/82 이전에 풀었던 괄호 문제와 유사한 스택을 활용한 문제이다. 이 문제는 레이저를 만났을 때의 쇠막대기의 개수가 중요하다. 그냥 쇠막대기의 개수가 아니라 레이저를 만났을 때 관통중인 쇠막대기의 개수이다. 다시 말해 아직 ')' 를 만나지 못한 '(' 문자의 개수가 중요하다. 그렇다면 아직 ')' 를 만나지 못한 '(' 문자의 개수를 어떻게 구할 수.. 2023. 2. 5.
[백준 9012][파이썬] 괄호 문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 괄호 모양이 올바른 괄호 모양인지 판단하는 문제이다. 올바른 괄호 모양의 정의를 다음과 같이 내렸다. 1. '(' 모양의 개수를 left, ')' 모양의 개수를 right로 정한다. 2. 문자열의 앞에서부터 left와 right를 증가시키는 과정에서 left는 항상 right 보다는 같거나 커야한다. 3. 한 문자열을 전부 조사하고 나면 left와 right의 개수는.. 2023. 2. 3.
[백준 18870][파이썬] 좌표 압축 (파이썬 dictionary) https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 처음 생각한 알고리즘은 다음과 같다. 1. 리스트를 새로운 집합으로 만들어서 중복을 제거한다. 2. 집합을 리스트로 바꾸어서 정렬 후 다시 리스트로 생성한다. 3. 새로운 리스트 요소들의 인덱스가 곧 자신보다 작은 요소들의 개수가 된다. 오름차순으로 정렬을 하게 되면 자연스럽게 인덱스가 자신보다 같거나 작은 요소의 개수가 된다. 자신보다 작은 요소.. 2023. 1. 31.
728x90
반응형