본문 바로가기

전체 글91

백준(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.
백준(BOJ) 13460 구슬 탈출 2(Python) BFS 문제. 18170이랑 비슷하게 두 개의 요소를 고려하는 BFS 문제였다. 거기다가 좌표를 한 번에 여러 칸 이동해야 했기 때문에 고려할 부분이 많았다. 먼저 빨간 공을 움직이는데, 움직일 자리에 파란 공이 있을 때 파란 공도 움직일 수 있다면 둘 다 움직이고, 그렇지 않다면 break한다. 이때 파란 공이 움직여서 구멍에 도착했는지 확인하고, 구멍에 도착했다면 continue한다. 만약 빨간 공이 움직일 자리에 파란 공이 없다면 계속 움직인다. 빨간 공이 구멍에 도착했다면 flag를 수정하고, 파란 공을 마저 움직인다. 이때 파란 공이 구멍에 도착했다면 continue하고, 그렇지 않다면 횟수를 출력하고 break한다. 만약 빨간 공이 구멍에 도착하지 않은 상태라면 visited에 두 공의 좌표를.. 2022. 7. 20.
백준(BOJ) 2162 선분 그룹(Python) Union-Find에 선분 교차 판정을 곁들인 문제. 각 선분이 모두 교차하는지 확인하고, 교차한다면 Union-Find를 진행하면 되는 문제. 일반적인 선분 교차 판정과는 달리 두 선분이 하나로 겹쳐지는 경우나 한 점에서 접하는 경우도 포함해야 하기 때문에 이 부분을 고려해서 선분 교차 판정을 수정해줬다. 코드는 다음과 같다. # -*- 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()).. 2022. 7. 19.
백준(BOJ) 2143 두 배열의 합(Python) 누적 합 & 이분 탐색 문제. 두 배열의 모든 누적 합의 값을 각각 새로운 배열에 저장하고, A의 누적 합의 값에 대해 T-값을 B의 누적 합의 값이 저장된 리스트에서 이진 탐색을 통해 찾고, 개수를 센다. 파이썬의 bisect 라이브러리를 사용하면 쉽게 구할 수 있다. 코드는 다음과 같다. # -*- 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()) n=int(input()) A=lis.. 2022. 7. 19.

티스토리툴바