자두의 데브로그

https://www.acmicpc.net/problem/1158 [문제 이해]원을 이루어서 사람들이 서있으면 한 명씩 제거해가는 문제였는데 여기서 제일 큰 문제는 "deque에서 어떻게 순회하도록 만드는가" 였다.N과 K가 주어졌을 때, N명의 사람 중 K번째 사람이 계속 제거되는 문제라 문제 자체를 이해하는데에 있어서는 큰 어려움은 없었던 것 같다. [문제 풀이]생각한 방법은 1부터 N까지 모두 덱에 저장하고 N에서 K번째 수를 계속 빼는 방식이었는데 "순회"를 계속 생각하다보니까 다른 방법이 생각났다 !!! 일단 deque는 K부터 저장하도록 해서 N까지 저장하고 앞 쪽에 남은 수는 (ex. K = 3이면 1, 2) N 뒤에 저장하도록 수정하였다. 가장 앞의 원소부터 제거하면서 K-1개 만큼만 po..

https://www.acmicpc.net/problem/10828 [문제 이해]문제의 제목처럼 스택을 구현하는 문제였다. 실버 4라고는 하지만 스택만 안다면 충분히 풀 수 있는 문제라 금방 풀었던 것 같다! [문제 풀이]파이썬에서도 스택이나 큐를 사용하는 문제를 풀 때 deque를 사용했던 것처럼 자바에서도 deque를 사용하여 이 문제를 해결하였다.deque는 linked list로 가져와서 사용했고, deque 라이브러리 내에 있는 add(), getLast(), removeLast() 등을 활용했다. 스택이니까 top이나 pop의 경우, 가장 마지막에 삽입된 원소를 찾기 위해 Last에서 꺼낼 수 있도록 해주었다. isEmpty()의 경우, boolean 값을 반환하기 때문에 if문에다가 바로 넣..

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개의 랜선을 만드려고 할 때 랜선 하나의 길이가 최대가 되는 수를 구하는 문제이다. [문제 풀이]큰 범위를 탐색 범위로 가질 때 이진 탐색을 활용하면 되는데 이 문제도 탐색 범위가 넓어 이진 탐색을 구현하여 적용하면 되겠다고 생각했다. 강의를 들으면서 풀었던 떡볶이 떡 만드는 문제와 동일한 방식으로 풀이를 하면 ..

문제를 풀다가 리스트에서 한 번에 모든 원소에서 같은 값을 뺄 수 있는 방법이 있는지 찾아보다가 발견하여 기록해둔다. [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...

매번 습관적으로 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..

* 해당 포스팅은 아래 알고리즘 강의를 듣고 정리한 내용입니다. https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5 이진 탐색 알고리즘 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 → 가장 기본적인 형태의 데이터 탐색 알고리즘 ex. 선택 정렬에서 매 단계마다 가장 작은 데이터를 찾는 과정 ⇒ 리스트에서 특정 데이터가 존재하는지 검색할 때 별다른 말이 없으면 기본적으로 순차 탐색을 이용하는 것 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시간 복잡도: O(logN) 이진 탐색은 시작점, 끝점, 중..

* 해당 포스팅은 아래 알고리즘 강의를 듣고 정리한 내용입니다. https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4 정렬 알고리즘 정렬: 데이터를 특정 기준에 따라 순서대로 나열하는 것 → 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨 ex. 데이터의 개수가 적을 때, 데이터의 개수가 많지만 데이터의 범위가 특정하게 한정되어있을 때, 이미 데이터가 정렬되어있을 때 컴퓨터에게 정확히 어떠한 방식으로 정렬을 수행할 것인지 코드를 사용해서 나타내어야 함 선택 정렬 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 → 매번 현재 범위에..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을www.acmicpc.net[문제 이해]나이와 이름이 주어졌을 때 나이순으로 정렬하고, 만약 나이가 동일하다면 입력 받은 순서대로 회원을 정렬하는 문제였다. [문제 풀이]문제의 난이도는 높지 않아서 해결 방법은 쉽게 찾긴 했지만 헷갈리는 부분이 몇 개 있었다.1. 입력을 어떻게 받아야 하지?2. 정렬 기준을 어떻게 하지?3. 출력은 어떻게 하지?사실 문제를 풀면서 당연히 고민해보게 될 부분인데 이번에는 특히나 문제가 쉬운 만큼 고민이..

https://www.acmicpc.net/problem/18870 Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 " data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/18870" data-og-url="https://www.acmicpc.net/problem/18870" data-og-image="https://scrap.kakaocdn.net/dn/btjHbV/hyVDEsnKE8/CukpDZnIkubYTSCFFBrH9K/img.png?width=2834&height=1480&face=0_0_2834_1480"> 18870번: 좌표 압축수직선 위에 N개의 좌표 ..