이것저것 공부 기록하기

문제링크 https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 문제설명 문제풀이 def promising(i, col): # 대각선 방향 겹치는지 체크 k = 1 flag = True while k < i and flag: if col[i] == col[k] or (abs(col[i]-col[k]) == i-k): flag = False k += 1 return flag def nqueen(i,n,c..

문제링크 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제풀이 주어진 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제이므로 투포인터로 풀이가 가능한 문제이다. 수열의 길이 N과 타겟으로 봐야할 S의 범위는 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000) 이므로 시간초과에 유의해야한다. 처음에는 아무 생각 없이 주어진 수열 arr의 길이를..

문제링크 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제풀이 에라토스테네스의 체 기반으로 풀었다. m, n이 1부터 입력될 수 있기 때문에 sieve의 0, 1을 False로 초기값을 설정해야 한다. m, n = map(int, input().split()) x = int(n**0.5) sieve = [False,False] + [True] * (n-1) for i in range(2, x+1): if sieve[i] == True: for j in range(2*i, ..

문제링크 https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 문제풀이 n, k = map(int, input().split()) sieve = [True] * (n+1) m = int(n**0.5) chk = [] for i in range(2,m+1): if sieve[i] == True: chk.append(i) for j in range(2*i, n+1, i): sieve[j] = False if j not in chk: chk.append(j) chk += [i for i in range(m+1,n+1) if sieve[i] =..

문제링크 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제는 일정 범위 내의 연속된 소수의 합을 찾아야하므로 에라토스테네스의 체로 소수의 리스트를 구하고, 구한 소수 리스트에서 투포인터로 그 합을 구하는 것이 포인트이다. 이 부분을 인지해서 풀이했지만, 처음에는 시간초과가 났고 투포인터 부분에서 시간복잡도 문제가 있다고 생각했다. val = sum(tmp[left:right])에서 (O(right-left) 만큼의 공간을 만드는 시간) + (sum 함수 시간복잡도)가 소요된다. (이 부분은 감으로 고치고 풀이 통과 후에 이왜맞과 맞왜틀을 동시에 시전하며 질문해..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net n = int(input()) tmp = [] for i in range(n): tmp.append(input().split()) tmp = [[int(x[0]),x[1]] for x in tmp] tmp.sort(key=lambda x:x[0]) for i in range(n): print(*tmp[i]) 정렬문제인데 나는 그냥 sort 써서 했다보니 채점시간이 4000ms이 걸렸다. 이후에 좀 더 ..

오늘부터 나도 1일1문제 시작. 오늘의 문제 : https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net # sys.stdin.readline() 을 사용해야 시간초과 안 나고 통과됨 (같은 풀이일 때 input() 으로 받면 시간초과남) import sys from collections import deque n = int(sys.stdin.readline()) q = deque() for i in range(n): tmp =..

둘 다 완전탐색 시 시간초과가 날 때 유용하게 사용될 수 있다. 투포인터 문제 풀다가 차이가 궁금해서 정리해봤다. 투포인터 vs 이분탐색 투포인터 : left, right 두 개의 포인터를 한 칸씩 이동하면서 알맞은 값을 찾음 이분탐색 : mid를 활용해 매 연산마다 탐색하는 범위를 절반으로 좁혀나감 투포인터(Two Pointer) 이분탐색(이진탐색, Binary Search) 시간복잡도 O(N) O(log N) 가정 특별히 없으나, 일반적으로 배열이 정렬되어있을 때 좀 더 유용 데이터가 정렬되어있어야 함 방식 양 끝단에서 한 칸씩 이동하면서 알맞은 값을 찾음 mid를 활용해서 매 연산마다 탐색하는 범위를 절반으로 좁혀나감 참고 파이썬 알고리즘 인터뷰 https://skesswswkk.tistory.co..