본문 바로가기

백준 알고리즘(BOJ)90

백준 알고리즘 18870(좌표 압축) - python, c++ 백준 알고리즘 18870(좌표 압축) - python, c++ > https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 주어진 입력에 대한 좌표를 압축하여 각 index에 맞는 rank를 mapping 해주는 문제. 문제는 간단하지만 구현은 은근히 까다롭다. (O(N^2)으로 구현했다가 시간 초과 당함) [문제 해결 - python] python은 short-coding을 목적으로 진행 1. 입력 _.. 2022. 7. 26.
백준 알고리즘 13305(주유소) - python, c++ 백준 알고리즘 13305(주유소) - python, c++ > https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 도시에서 주유하는 리터당 가격(price)과 거리(distance)를 이용하여 최소 거리를 구하는 문제. price는 도시의 수인 N 개의 배열, distance는 도시 간의 거리이기 때문에 N-1 개의 배열을 갖는다. 그리디 알고리즘으로 접근하여 해결하는 방법. [문제 풀이] 1. 그리디의 기준은 price이고, 더 작.. 2022. 7. 21.
백준 알고리즘 1181(단어 정렬) - python, c++ 백준 알고리즘 1181(단어 정렬) - python, c++ > https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 길이가 짧은 것부터, 길이가 같으면 사전 순으로 정렬하는 문제 python만 하다보니 c++을 너무 까먹어서 다시 같이 해야겠다.... [문제 해결 - python] 1. set를 통해 중복을 제거한다. 2. 사전 순으로 먼저 sort 3. lambda를 이용하여 길이가 짧은 순으로 재정렬 후 출력 python 쏘-이지! .. 2022. 7. 16.
백준 알고리즘 11650(좌표 정렬하기) - python 백준 알고리즘 11650(좌표 정렬하기) - python > https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net x, y의 좌표를 각각 기준으로 오름차순 정렬하는 문제 [문제 풀이] 1. 'x좌표가 같으면 y좌표가 증가하는 순서로 정렬'의 조건 - y좌표 기준으로 먼저 정렬 후 x좌표 기준으로 정렬하라! 2. python의 sort 함수에서 lambda를 이용하여 간단히 정렬 - lambda x.. 2022. 7. 14.
백준 알고리즘 1541 (잃어버린 괄호) - python 백준 알고리즘 1541 (잃어버린 괄호) - python > https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net '+'와 '-', 그리고 숫자로만 이루어져 있는 수식을 최소값으로 만드는 문제 [문제 풀이] 1. '-'가 나온 후로는 다시 '-'가 나오기 전까지 괄호를 치는 것이 최소값이 된다. - 먼저 '-'를 기준으로 split - 첫 idx는 무조건 양수일 수 밖에 없음 (값+) - 그 이후의 idx는 각 요소들을 더하여 빼줌 (값-) 2.. 2022. 7. 8.
백준 알고리즘 14889 (스타트와 링크) - python 백준 알고리즘 14889 (스타트와 링크) - python > https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 두 팀으로 나눠서 합산의 차이가 가장 적도록 만드는 문제. 백트래킹과 시간 효율이 중요한 문제이다. (처음엔 시간초과로 멘붕이었다가 다시 해결) [문제 풀이] 1. 절반(N//2명으로 구성)을 선택하여 조합을 생성 : DFS 탈출 조건 - 나머지 N//2명은 자동으로 결정됨 2. 예외 처리 - _min이 0일 경우에는 더 진행할 필요가 없음 3. 구해진 조.. 2022. 7. 4.
백준 알고리즘 1992 (쿼드트리) - python 백준 알고리즘 1992 (쿼드트리) - python > https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 분할 정복 문제인데, 주의할 점이 몇 가지 있다. 1. 4분할에 대한 4분면의 해당 순서 2. 시작 '(' 의 괄호를 넣는 위치 - 한 사분면 전체가 같지 않다는 것을 파악하면 대입 - 만약 입력 전체가 1이면 '(1)'이 아니라 그냥 '1'이다. 3. 끝 ')'의 괄호를 넣는 위치 - 한 사분면이 끝날 때 대입 [예시 입력] 8.. 2022. 6. 30.
백준 알고리즘 11399 (ATM) - python 백준 알고리즘 11399(ATM) - python > https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 전형적인 그리디 알고리즘, 누적 문제 [문제 풀이] 1. 뒤로 갈수록 누적이 되기 때문에 작은 순서대로 정렬 2. i번째의 수는 누적될 때 (N-i)번 누적되는 알고리즘 3. 누적 후 출력 import sys N = int(sys.stdin.readline()) people = list(map(int, sys.stdin.readline().split())) people.so.. 2022. 6. 30.
백준 알고리즘 1436 (영화감독 숌) - python (재풀이) 백준 알고리즘 1436 (영화감독 숌) - python > https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 666이 들어간 수열을 순서대로 찾는 문제. str으로 접근하니 간단했다. [문제 풀이] 1. 666에서 시작하여 str 기준으로 먼저 '6'을 발견하면 2. 그 idx부터 3개가 '666'인지는 체크 3. 맞으면 N을 -1하고 체크는 중단 4. 숫자를 올리면서 계속 반복 5. N == 0이 되면 출력 import sys N = int(.. 2022. 6. 29.
728x90

티스토리툴바