전체 글40 [파이썬] 백준 1654번 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [문제 이해] 이미 가지고 있는 랜선 K개를 가지고 잘라서 N개의 랜선을 만드려고 할 때 랜선 하나의 길이가 최대가 되는 수를 구하는 문제이다. [문제 풀이] 큰 범위를 탐색 범위로 가질 때 이진 탐색을 활용하면 되는데 이 문제도 탐색 범위가 넓어 이진 탐색을 구현하여 적용하면 되겠다고 생각했다. 강의를 들으면서 풀었던 떡볶이 떡 만드는 문제와 동일한 방식으로 풀이를.. 2024. 3. 23. [코테 스터디] 리스트의 모든 원소에서 같은 값 빼기 문제를 풀다가 리스트에서 한 번에 모든 원소에서 같은 값을 뺄 수 있는 방법이 있는지 찾아보다가 발견하여 기록해둔다. [1] map 이용 가장 익숙한 map과 lambda를 이용하는 방법이다. 원래 저장하고 있던 리스트의 각 원소에서 어떤 값을 어떻게 처리할 것인지 lambda의 조건에 작성하면 된다. array2 = list(map(lambda x: x-n, array1)) [2] List Comprehension 이용 array2 = [i-1 for i in array1] + numpy 이용: numpy 설치 후 numpy 내의 subtract 함수를 사용한다. 사용 방법은 아래와 같다. array2 = numpy.subtract(array1, 1) 참고 https://jlim0316.tistory... 2024. 3. 23. [코테 스터디] sys.stdin.readline()으로 입력 받기 매번 습관적으로 input() 대신 sys.stdin.readline()으로 입력을 받아왔는데 스터디를 하면서 input() 대신 sys.stdin.readline()을 사용하는 이유에 대한 질문이 들어와 정확히 내 머리에도 넣기 위해서 찾아보고 기록해두도록 하겠다. 하나의 입력을 받는 상황에서는 input()으로 입력을 받아도 괜찮지만 반복문으로 여러 줄을 입력 받아야 하는 상황이라면 sys.stdin.readline()으로 입력 받아야 시간 초과가 발생하지 않는다고 한다. 사용 방법은 아래와 같다. import sys n = sys.stdin.readline() 정수로 입력을 받아 사용하기 위해서는 위의 입력 받는 식에 int()함수를 사용한다. import sys n = int(sys.stdin.r.. 2024. 3. 23. [코테 스터디] Week4 이진 탐색 개념 정리 * 해당 포스팅은 아래 알고리즘 강의를 듣고 정리한 내용입니다. https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5 이진 탐색 알고리즘 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 → 가장 기본적인 형태의 데이터 탐색 알고리즘 ex. 선택 정렬에서 매 단계마다 가장 작은 데이터를 찾는 과정 ⇒ 리스트에서 특정 데이터가 존재하는지 검색할 때 별다른 말이 없으면 기본적으로 순차 탐색을 이용하는 것 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시간 복잡도: O(logN) 이진 탐색은 시작점, 끝점, 중.. 2024. 3. 23. [코테 스터디] Week3 정렬 개념 정리 * 해당 포스팅은 아래 알고리즘 강의를 듣고 정리한 내용입니다. https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4 정렬 알고리즘 정렬: 데이터를 특정 기준에 따라 순서대로 나열하는 것 → 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨 ex. 데이터의 개수가 적을 때, 데이터의 개수가 많지만 데이터의 범위가 특정하게 한정되어있을 때, 이미 데이터가 정렬되어있을 때 컴퓨터에게 정확히 어떠한 방식으로 정렬을 수행할 것인지 코드를 사용해서 나타내어야 함 선택 정렬 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 → 매번 현재 범위에.. 2024. 3. 23. [파이썬] 백준 10814번 나이순 정렬 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net [문제 이해] 나이와 이름이 주어졌을 때 나이순으로 정렬하고, 만약 나이가 동일하다면 입력 받은 순서대로 회원을 정렬하는 문제였다. [문제 풀이] 문제의 난이도는 높지 않아서 해결 방법은 쉽게 찾긴 했지만 헷갈리는 부분이 몇 개 있었다. 1. 입력을 어떻게 받아야 하지? 2. 정렬 기준을 어떻게 하지? 3. 출력은 어떻게 하지? 사실 문제를 풀면서 당연히 고민해보게 될 부분인데 이번에는 특히나 문제가 .. 2024. 3. 23. [파이썬] 백준 11870번 좌표 압축 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net [문제 이해] 받은 좌표 리스트를 오름차순으로 배열했을 때, 해당하는 리스트의 인덱스를 순서대로 출력하는 문제이다. 좌표 압축이라고 해서 문제 자체를 이해하기 힘들었는데 입력을 보고 위처럼 이해하고 푸니까 더 풀기 쉬웠던 것 같다. [문제 풀이] 1. 입력 받은 리스트를 오름차순으로 정렬하고 리스트의 원소에 해당하는 값을 오름차순 인덱스에 해당하.. 2024. 3. 20. [파이썬] 백준 1181번 단어 정렬 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net [문제 이해] 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래의 조건에 따라 정렬하는 프로그램을 작성하는 문제이다. 1. 길이가 짧은 것부터 2. 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거한다. [문제 풀이] 단어 리스트를 받았을 때, 조건대로 짧은 순으로 먼저 정렬하고, 만약 길이가 같으면 사전 순으로 정렬하는 문제라 어렵지 않게 풀 수 있었다. 그 전에 .. 2024. 3. 20. [파이썬] 백준 11047번 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net [문제 이해] 입력 받은 동전 종류 중 일부를 적절히 사용해서 입력 받은 결과 값을 만들기 위해 필요한 최소 동전 개수를 구하는 문제이다. [문제 풀이] 내림차순 정렬을 통해 가지고 있는 동전 중 가장 높은 수부터 만들어야 하는 값과 비교한다. 가지고 있는 동전이 크다면 더 작은 동전과 비교해가며 동전의 개수를 센다. 이때 동전의 개.. 2024. 3. 14. 이전 1 2 3 4 5 다음
