본문 바로가기

BOJ79

백준(BOJ) 12892 생일 선물(Python) 두 포인터 문제. 선물의 가격을 기준으로 입력값을 오름차순 정렬한 리스트를 생성하고, s, e 두 포인터를 이용해 문제를 해결했다. (e가 가리키는 선물의 가격) - (s가 가리키는 선물의 가격)이 d 미만인 경우 k에 e가 가리키는 선물의 만족도를 더한다. 그러다가 d 이상인 경우 ans를 max(k,ans)로 갱신하고, (e가 가리키는 선물의 가격) - (s가 가리키는 선물의 가격)이 d 미만이 될 때까지 s를 옮기며 k를 수정한다. e가 n인 경우 이를 종료한다. 마지막에는 ans를 한 번 더 갱신해주는데, 이는 목록 중 가장 비싼 선물과 싼 선물의 값 차이가 d 미만인 경우 ans가 위 과정에서 갱신되지 않기 때문이다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import .. 2022. 7. 23.
백준(BOJ) 2580 스도쿠(Python) 백트래킹 문제. 빈 칸의 좌표를 먼저 모두 담은 리스트를 만들고, 그 리스트의 원소의 개수만큼 백트래킹을 하며 문제를 해결했다. 어떤 수를 빈 칸에 넣을 때 행과 열, 3X3 칸에 같은 수가 존재하는 지를 확인하고 존재하지 않는다면 다음 칸으로 넘어가는 방식으로 해결했다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations import bisect #input=sys.stdin.readline #sys.setrecursionlimit(100000000) L=[list(map(int,input().split())) .. 2022. 7. 23.
백준(BOJ) 9663 N-Queen(Python) 백트래킹 문제. 각 행마다 퀸을 하나씩 배치하는데, 이때 이전 행에 배치한 퀸의 열 번호를 토대로 현재 위치에 퀸을 배치할 수 있는 지를 판단한다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations import bisect #input=sys.stdin.readline #sys.setrecursionlimit(100000000) n=int(input()) L=[0]*n ans=0 def func2(k): for i in range(k): if L[k]==L[i] or abs(L[k]-L[i])==k-i: retu.. 2022. 7. 22.
백준(BOJ) 1946 신입 사원(Python) 그리디 문제. 먼저 서류 성적을 기준으로 입력값을 오름차순 정렬한다. 신입 사원이 선발되기 위해서는 자신보다 서류 성적이 높은 사원 중 한 명 이상 면접 성적이 더 높아야 하므로, 리스트의 처음부터 면접 성적의 최솟값을 갱신하며 현재 면접자의 면접 성적과 비교하면 된다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy from itertools import combinations import bisect input=sys.stdin.readline #sys.setrecursionlimit(100000000) t=int(input()) for i in range(t): n=.. 2022. 7. 21.
백준(BOJ) 9322 철벽 보안 알고리즘(Python) 딕셔너리를 이용한 해싱으로 푼 문제. 1공개키와 2공개키를 입력받고, 1공개키의 i번 인덱스의 값이 2공개키의 j번 인덱스에 위치한다고 할 때, D[i]=j로 해싱한 뒤 암호문을 입력받아 인덱스 0부터 n-1까지 해싱된 값에 따라 L3[D[i]]를 공백으로 구분해 출력한다. 코드는 다음과 같다. t=int(input()) for i in range(t): n=int(input()) L1=input().split() L2=input().split() D={i:0 for i in range(n)} for j in range(n): for k in range(n): if L1[j]==L2[k]: D[j]=k L3=input().split() for j in range(n): print(L3[D[j]],end=.. 2022. 7. 20.
2주차 정리 & 플래티넘 달성 및 향후 계획 7월 20일 새벽에 플래티넘을 달성했다. 플래티넘 달성에 필요한 AC Rating은 1600으로, 1600에 딱 맞춰서 달성했다. 어찌보면 이게 내가 플래티넘을 목표로 PS를 했다는 반증이기도 할 거다. 지난 한 주 동안은 20문제 조금 안 되게 문제를 풀었다. 그리디 문제에 잡혀서 하루를 날려먹은 적도 여럿 있었고, 그 덕에 PS에 대한 의욕이 떨어지기도 해서 1주차보다 10문제 이상 못 풀었던 것 같다. 플래티넘에 대한 이야기를 조금 더 하자면, 사실 플래티넘을 찍었다고 해서 내가 PS를 잘하는 편이라고 생각하진 않는다. 학회에서 워낙 잘하는 사람을 많이 보기도 했거니와, 아직 내 스스로에게 그렇게 만족스러운 실력이 아니기 때문이다. 적어도 플래티넘이면 골드 문제는 어떻게 풀 수 있어야 할 텐데, 문.. 2022. 7. 20.

티스토리툴바