백준 온라인저지 10816번 숫자 카드 2 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제풀이 알고리즘 분류에는 이분 탐색으로 되어있는 문제다. 그러나 Counter 함수, 딕셔너리 등 여러 가지 방식으로 풀이할 수도 있는 문제이다. 그냥 단순히 배열의 메소드인 count()를 사용하면 시간초과가 발생하니 알아두자. 나는 bisect를 이용해 문제를 풀었다. 일단 이분탐색을 하..

백준 온라인저지 18870번 좌표압축 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제풀이 시간 복잡도가 굉장히 중요한 문제이다. 근본적인 알고리즘은 쉬운 편이다. 중복되지 않은 배열을 정렬해 그 인덱스를 가져오면 된다. 만약 여기서 리스트에서 인덱스를 가져오는 index()메소드를 사용하면 시간복잡도가 O(N)이다. 그런데 문제에서 N의 범위는 무려 1 ≤ N ..

백준 온라인저지 7576번 토마토 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제풀이 1. 바이러스같이 퍼져가는 구조이므로 bfs를 사용해야한다. 2. 퍼져나가면서 1씩 증가시켜 기록하면 최대값을 통해 모두 익을 때까지의 최소 날짜를 알 수 있다. 3. dx, dy 배열을 이용해 사방에 있는 토마토들을 탐색하자. 4. 만약 bfs를 사용해서 탐색했는데도 0이 남아있다면 -1에 의해 가로막혀 있는..

백준 온라인저지 1654 랜선 자르기 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제풀이 이 문제는 이분탐색을 이용해야하는 문제이다. start는 1로 잡고, 랜선 중 최대길이를 end로 정한 다음 이분 탐색을 하면 다음과 같다. 첫 번째 mid는 402cm이다. 402cm로 자르면 랜선이 5개 밖에 나오지 않기 때문에 mid를 mid = (start + mid - 1) // 2 로..

백준 온라인저지 10989번 수 정렬하기 3 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제풀이 자세히 보면 메모리 제한이 8MB인 반면 시간제한은 널널하다. sort() 함수를 사용하면 메모리제한을 넘기기 때문에 계수정렬 을 사용해야한다. import sys cnt = [0] * 10000 n = int(sys.stdin.readline()) for i in range(n): cnt[int(sys.stdin.readline())..

프로그래머스 연습문제 문제풀러 바로가기👇👇👇👇👇👇 https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 문제풀이 124나라의 숫자는 기본적으로 3진수와 비슷하다. 3진법에서는 숫자를 0, 1, 2 순서로 표현한다면 124나라에서는 4, 1, 2 순서대로 숫자를 표기한다. 그런데 약간 다른 점이 있다. 1의 자리 숫자일 때, 3의 배수일 때는 일반 3진법 표기와 다르게 표기된다는 점이다. -3의 배수가 아닐 때 10진법 3진법 124나라 1 1 1 5 12 12 7 21 21 3진법과 124나라의 표기가 동일하다는 것을 확인할 수 있다. -3의 배수일 때 10진법 3진법 124나라 3 1..