초이의 끄적끄적

프로그래머스

# 두 정수 사이의 합 

def solution(a, b):
    answer = 0
    for i in range(min(a,b),max(a,b)+1):
        answer += i
    return answer

+ (GOOD) 다른 사람 풀이 -> sum을 생각 안했다ㅋㅋㅋ

def solution(a, b):
    return sum(range(min(a,b),max(a,b)+1))

# 체육복 

- 처음 내 코드

def solution(n, lost, reserve):
    for i in reserve:
        if i in lost:
            lost.remove(i)
        elif i-1 in lost:
            lost.remove(i-1)
        elif i+1 in lost:
            lost.remove(i+1)
    return n - len(lost)

• 테스트 케이스 5,7 통과 못함
• why? 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
• ex) 5 [2,3,4] [1,2,3] 4 -> 2번은 2번 체육복을 써야됨 -> 중복되는건 미리 빼놓고 시작해야됨.

- 수정 후 코드

• Point. 집합 set과 차집합 사용

def solution(n, lost, reserve):
    set_reserve = set(reserve) - set(lost)
    set_lost = set(lost) - set(reserve)
    for i in set_reserve:
        if i-1 in set_lost:
            set_lost.remove(i-1)
        elif i+1 in set_lost:
            set_lost.remove(i+1)
    return n - len(set_lost)

프로그래머스

# 가운데 글자 가져오기

def solution(s):
    answer = ''
    if len(s)%2 == 1:
        answer = s[len(s)//2]
    else:
        answer = s[len(s)//2-1 : len(s)//2+1 ]
    return answer

# 같은 숫자는 싫어

def solution(arr):
    answer = [arr[0]]
    for i in range(1,len(arr)):
        if answer[-1] != arr[i]:
            answer.append(arr[i])
    return answer

# 수박수박수박수박수박수?

def solution(n):
    answer = ''
    for i in range(1,n+1):
        if i%2 != 0:
            answer+="수"
        else:
            answer+="박"
    return answer

+ (GOOD) 다른 사람 풀이 

def solution(n):
    return "수박"*(n//2) + "수"*(n%2)

# 문자열 내 마음대로 정렬하기

• Point. 문자열 정렬
• 처음 접근 방법 -> sorted(strings, key=lambda x:x[n]) -> n번째 숫자가 같은 경우 사전순 정렬 안됨
  • 사전순 정렬을 해주고 n번째 기준으로 정렬해주면됨

def solution(strings, n):
    return sorted(sorted(strings), key=lambda x:x[n])

+ (GOOD) 다른 사람 풀이  미.쳤.다.

• n번째 수를 글자의 앞에 붙인다음, 정렬함

def solution(strings, n):
    answer = []
    for i in range(len(strings)):
        strings[i] = strings[i][n] + strings[i]
    strings.sort()
    for j in range(len(strings)):
        answer.append(strings[j][1:])
    return answer

프로그래머스 - 완전 탐색

# 모의고사 (Level 1)

def solution(answers):
    answer = []
    math_1 = [1, 2, 3, 4, 5]
    math_2 = [2, 1, 2, 3, 2, 4, 2, 5]
    math_3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    count = [0,0,0]
    for i in range(len(answers)):
        if answers[i] == math_1[i%5]:
            count[0] +=1
        if answers[i] == math_2[i%8]:
            count[1] +=1
        if answers[i] == math_3[i%10]:
            count[2] +=1

    for i in range(3):
        if count[i] == max(count):
            answer.append(i+1)
    return answer

# 소수 찾기 (Level 2)

• itertools를 이용해 순열 구하기 permutations (참고)
  • 중복되는 수 set으로 줄여 속도 높이기
• 소수 판정 -> 시간복잡도를 위하여 1) 제곱근 2) 에라토스테네스 체 이용하기

from itertools import permutations
import math

def check(n): # 소수 판별
    k = math.sqrt(n) # 제곱근 사용
    if n < 2: 
        return False

    for i in range(2, int(k)+1):
        if n % i == 0:
            return False
    return True

def solution(numbers):
    answer = []
    for k in range(1, len(numbers)+1):
        perlist = set(list(map(''.join, permutations(list(numbers), k)))) # k개 순열 구하기
        for i in list(perlist):
            if check(int(i)):
                answer.append(int(i))

    answer = len(set(answer))

    return answer

# 카펫 (Level 2)

def solution(brown, yellow):
    xy = brown + yellow
    plus_xy = (xy - yellow + 4)//2
    
    for i in range(1,xy//2+1):
        if i + xy/i == plus_xy:
            return sorted([i,xy//i], reverse = True)

프로그래머스 - 정렬

# K번째수 (Level 1)

def solution(array, commands):
    answer = []
    for i,j,k in commands:
        answer.append(list(sorted(array[i-1:j]))[k-1])
    return answer

# 가장 큰 수 (Level 2)

• 문자열로 정렬해서 합친다
• numbers의 원소는 1,000이하 ->세자리까지 확인한다 ->  x*3
• Point. 문자열 비교연산 -> 사전과 같은 방식
  • ex) 첫번째 인덱스인 666[0]인 6과 101010[0]인 1과 222[0]인 2를 ascii숫자로 바꿔서 비교합니다. 물론 같으면, 다음 인덱스도 비교합니다. 비교한 결과 [6, 2, 10]의 순으로 정렬됩니다.

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

# H-Index (Level 2)

• Point. enumerate를 사용해서 반복문의 index번호 가져오기
• H-지수 구하는 방법(참고)

def solution(citations):
    answer = 0
    for i, p in enumerate(sorted(citations,reverse=True)):
        if i+1 <= p:
            answer+=1
    return answer

# 11066 파일 합치기 (골드3)

• 고난이도 문제 핵심 DP식 구하기

def process():
    N, A = int(input()), [0]+list(map(int, input().split()))
    # S[i]는 1번부터 i번까지의 누적합
    S = [0 for _ in range(N+1)]
    for i in range(1, N+1):
        S[i] = S[i-1] + A[i]

    # DP[i][j] : i에서 j까지 합하는데 필요한 최소 비용
    # DP[i][k] + DP[k+1][j] + sum(A[i]~A[j])
    DP = [[0 for i in range(N+1)] for _ in range(N+1)]
    for i in range(2, N+1): # 부분파일의 길이
        for j in range(1, N+2-i): # 시작점
            DP[j][j+i-1] = min([DP[j][j+k] + DP[j+k+1][j+i-1]
                                for k in range(i-1)]) + (S[j+i-1] - S[j-1])
    print(DP[1][N])


for _ in range(int(input())):
    process()

#12849 본대 산책 (실버1)

• 한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.
• D 가 주어진다 (1 ≤ D ≤ 100,000) 
• 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력 한다.
• 참고

# 0 분에 어떤 지점에 도착할 수 있는 상태
# 0 : 정보과학과 1 : 전산관 2 : 미래관 3 : 신양관
# 4 : 한경직기념관 5 : 진리관 6 : 학생회관 7 : 형남공학관
DP = [1,0,0,0,0,0,0,0]

def nxt(state):
    tmp = [0 for _ in range(8)]
    tmp[0] = state[1] + state[2]
    tmp[1] = state[0] + state[2] + state[3]
    tmp[2] = state[0] + state[1] + state[3] + state[4]
    tmp[3] = state[1] + state[2] + state[4] + state[5]
    tmp[4] = state[2] + state[3] + state[5] + state[7]
    tmp[5] = state[3] + state[4] + state[6]
    tmp[6] = state[5] + state[7]
    tmp[7] = state[4] + state[6]
    return tmp

for i in range(int(input())):
    DP = nxt(DP)

print(DP[0]%1000000007)

프로그래머스 네트워크 (문제)

• Point. 덩어리 구하기 -> BFS 사용

def solution(n, computers):
    answer = 0 # 네트워크의 개수 저장
    q = [] # 탐색을 위한 큐
    visited = [0]*n # 방문한 노드 체크

    while 0 in visited: #모든값이 방문표시가 될때까지 반복
        x = visited.index(0)
        q.append(x) # 첫 노드 인덱스 추가
        visited[x] = 1 # 첫 노드 방문 표시
        
        while q: 
            node = q.pop(0) # 큐 앞에서부터 노드 꺼내기
            visited[node] = 1
            for i in range(n): #인접 노드 방문
                if visited[i] == 0 and computers[node][i] == 1:
                    # 인접노드이고 방문한적 없는 경우
                    q.append(i) # 큐에 추가
                    visited[i] = 1 #방문했음을 표시
        answer += 1 # 한 네트워크 탐색을 마치면 개수 증가
    return answer

프로그래머스 - 두 개 뽑아서 더하기 (level 1)

def solution(numbers):
    answer = []
    for i in range(len(numbers)):
        for j in range(i+1,len(numbers)):
            answer.append(numbers[i]+numbers[j])
    sort_ans = sorted(answer)
    return sorted(list(set(answer)))

# 1915 가장 큰 정사각형 (골드5)

• n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.
• Point. DP로 풀기... .. 노이해... 다시 풀어보기

N, M = map(int, input().split())
A = [[0 for _ in range(M+1)] for i in range(N+1)]
# DP[i][j] = i,j까지 왔을 때, 가장 큰 정사각형의 한 변의 길이
DP = [[0 for _ in range(M+1)] for i in range(N+1)]

for i in range(N):
    for idx, j in enumerate(list(map(int, list(input())))):
        A[i+1][idx+1] = j
mx =0
for i in range(1, N+1):
    for j in range(1, M+1):
        if A[i][j]:
            DP[i][j] = min(DP[i-1][j], DP[i-1][j-1], DP[i][j-1])+1

print(max([max(i) for i in DP]) ** 2)

단계별풀기 - 정렬

# 2108 통계학 (실버4)

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

• input()으로 하면 시간초과 남 import sys sys.stdin.readline() 사용
• 데이터 개수 세기 collections 모듈의 Counter 클래스 사용 ( 참고 )

from collections import Counter
import sys
N = int(sys.stdin.readline())
N_list = [int(sys.stdin.readline()) for _ in range(N)]
N_sort = sorted(N_list)

print(round(sum(N_list)/N)) # 반올림함수 round
print(N_sort[int(N/2)])
N_count = Counter(N_sort).most_common(2) #데이터 개수가 많은 순으로 정렬된 배열 리턴
if N > 1: # 데이터가 하나일 경우에는 out of range 뜨니까
    if N_count[0][1] == N_count[1][1]:
        print(N_count[1][0])
    else:
        print(N_count[0][0])
else:
    print(N_list[0])
print(N_sort[-1]-N_sort[0])

# 1427 소트인사이드 (실버5)

• 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

n = input()
n_list = []
for i in n:
    n_list.append(i)

n_sort = sorted(n_list, reverse=True)
for i in n_sort:
    print(i,end="")

Q. 외부단편화와 내부 단편화란?

• 외부단편화란 총 메모리 공간은 충분하지만 실제로 할당할 수 없는 경우(메모리 배치에 따라 발생하는 문제)
• 내부단편화란 메모리 할당 시 프로세스가 필요한 양보다 더 큰 메모리가 할당되어 메모리 공간이 낭비는 되는 현상

+ 메모리 단편화란

• RAM에서 메모리 공간이 작은 조각으로 나뉘어져 사용가능한 메모리가 충분히 존재하지만 할당(사용)이 불가능한 상태를 보고 메모리 단편화가 발생했다고 한다.

Q. 페이징과 세그먼테이션의 차이점은?

• 페이징은 고정 크기를 가지고, 세그먼테이션은 가변 크기를 가집니다.
• 페이징은 내부 단편화가 발생할 수 있고, 세그먼테이션은 외부 단편화가 발생할 수 있습니다.

+ 페이징(Paging)이란 (참고)

• 페이지 단위의 논리-물리 주소 관리 기법
• 논리(가상)메모리는 페이지(Page)라 불리는 고정 크기의 블록으로 나누어지고, 물리 메모리는 프레임(Frame)라 불리는 페이지와 같은 크기의 블록들로 나누어진다.
• 가상메모리 사용, 외부 단편화를 해결, 내부 단편화 존재 (페이지가 클수록 내부 단편화도 커진다.)

+ 세그먼테이션(Segmentation)이란

• 사용자/프로그래머 관점의 메모리 관리 기법
• 같은 크기의 페이지를 갖는 페이징 기법과 달리 서로 다른 크기의 논리적 단위인 세그먼트(Segment)로 분할 한다.
• 가상메모리 사용, 내부 단편화는 해결, 외부 단편화는 존재

Q. 페이징과 세그먼테이션을 쓰는 이유

• 다중 프로그래밍 시스템에서 여러 프로세스를 수용하기 위해 주기억장치를 동적분할하는 메모리 관리 작업이 필요하기 때문입니다.