본문 바로가기

전체 글272

[프로그래머스] 양궁 대회 (Lv 2) https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 보기보다는 매우 간단한 문제이다. 0점을 제외하고 한 발 더 쏘거나, 아예 안 쏘거나 그리디한 케이스만 따지면 된다.남는 화살은 모두 0발로 간다. 어차피 0 안보내도 아예 질거라면 무조건 지고, 최적의 케이스는 저기 안에서만 나온다.저 케이스를 1점~10점 모두 순차적으로 따져줘야 하므로 DFS가 가장 자연스럽다.아, 점수 차가 동일할 케이스가 여러 개 나올 수도 있다. 이때 예외처리를 위해 정렬 잊지 말자. 이거 빼먹어서 두 번 실패함.wi.. 2024. 11. 15.
[BOJ] 테트리미노 (14500, G4) https://www.acmicpc.net/problem/14500우선, 어느 모양이 최대값이 될지 모른다. bfs는 이런 류에서 직전의 위치로 돌아가 올바르게 탐사할 수 없다. 아니, 이전의 길을 올바르게 기억할 수가 없기 때문에 bfs는 불가. 기본적으로는 dfs를 해야 한다.문제는, dfs는 깊이 탐색이기 때문에 그것이 불가능한 모양이 존재한다. 그것은 바로. T 모양의 테트리미노.이것의 경우는 별도로 예외 처리를 해 줘야 한다.dfs로 이전에 갔던 곳은 가지 않고, 딱 4칸 파게 진행을 해야한다. 어느 시작칸에서 최대가 날지 모르니까 모든 칸을 다 브루트 포스로 시도해 봐야 하고 그렇게 코드를 짜면 다음과 같다.import sysinput = sys.stdin.readlinetetra_map = .. 2024. 11. 12.
BOJ 약 11일차의 기록 코딩 분야에 다시 흥미를 가질 겸, 코딩 테스트도 좀 있었어서 다시 감 좀 회복할 겸 BOJ를 본격적으로 시작했습니다.사실 예에에에에에전 계정이 있긴 할건데 유의미하게 푼 것도 아니고, 어차피 기억도 안나고 해서 새 계정을 파서 시작한지 어느덧 11일차 입니다.약 2주 가까이 되가는 지금, 현재 티어는 골드 3, 벌써 많은 문제를 풀고 있습니다. 다익스트라도 복습하고 기존에 약했던 문제들도 풀면서 코딩 체력을 회복해 나가는 느낌입니다. 재미도 붙고 있고요. (짜증도 나지만... 내 잘못이긴 할건데 왜 틀린건데 왜 시간초)티어 자체 보다는, 내실을 이것저것 많이 신경 쓰고 있습니다. 사실 티어 자체는 꽁승 정수론 공식 몇개 가져오면 금방 올릴건데, 그게 중요한건 아니니까요. 유명한 문제들은 배우는 느낌으로.. 2024. 11. 12.
[BOJ] 이중 우선순위 큐 (7662, G4) https://www.acmicpc.net/problem/7662    이게 무슨 골4야... 골1~2줘도 될거 같은데힙 하나에서 최댓값과, 최솟값을 모두 뺄 수 있을까?기본적으로 파이썬의 힙에서는 최솟값만 빼게 되어있다. 최댓값을 빼는 힙은 모든 원소를 -1배해서 넣고 pop한 원소를 다시 돌려줘야 한다. 문제는 이걸 하고 싶다고, 최솟값을 만든 힙에다가 원소를 -1배 하면, 힙의 구조가 다 깨진다! 힙에서는 힙 명령어인 push, pop, 루트 확인만 고려해야 한다. (애초에 사실 자료구조 이론상, 삽입/삭제도 맘대로 하는게 아니었다. 별도의 절차와 알고리즘 순서가 있었다.)따라서 이 경우에는 두 개의 힙을 만들어야 한다. 최대힙과, 최소힙.문제는 최대힙에서 뺄 때, 최소힙은 그 원소를 어떻게 빼야하.. 2024. 11. 12.
[BOJ] 2166 - 다각형의 면적 https://www.acmicpc.net/problem/2166 * 신발끈 공식으로도 풀 수 있고, 사실 오목다각형이어도 성립한다고 하나, 오목다각형에서는 안 되는 줄 알고 다른 풀이를 썼다.적분에서 아이디어를 얻어 사용한 풀이입니다. 다각형의 좌표가 순서대로 돌아갑니다. 만일, x좌표의 값이 증가하면 넓이가 증가하게 잡았고, x좌표가 줄어드는 방향에서는 넓이를 뺍니다.  즉,  x축에서 진행하는 변이 이루는 사다리꼴의 넓이의 증감을 고려합니다.  이를 위해서 , 평행이동까지 진행합니다.N = int(input())area = 0point_list = []y_list = []for i in range(0, N): cur_x, cur_y = map(int, input().split()) poi.. 2024. 11. 2.
[프로그래머스] 유전 법칙 (PCCP 모의고사 1-3) https://school.programmers.co.kr/learn/courses/15008/lessons/121685# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 4진법에서 아이디어를 얻어야 하는 문제이다.다만, 나머지 0을 처리하기가 어렵기 때문에 잘 생각해야 한다.하위 세대를 선택하는 것은 4로 나눈 나머지, 윗 세대롤 보는 것은 4로 나눈 몫이다.다만, 몇 번째인지를 계산하는 것이므로, 4로 나눈 몫을 올리는 것이중요하다 (ceil 사용)맨 윗 세대까지 올라가야 하는데, 그 도중에 몫이 0으로 떨어지는 경우가 존재할 것이다. 그 경우는 맨 왼쪽으로 붙을거기에, 왼쪽으로 보낸다.RR : 1,.. 2024. 11. 1.

티스토리툴바