분류 전체보기

이중 우선순위 큐 성공다국어 한국어 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 시간 제한메모리 제한제출정답맞힌 사람정답 비율 6 초 256 MB 66501 14953 11023 21.853% 문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 ..

연속합 성공 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 (추가 시간 없음) 128 MB 142794 54278 38623 36.610% 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33..

요즘 프로젝트 하나 끝난 기념으로 UnrealEngine책을 사서 공부하고 있다. Unity에 익숙한 나머지 VSCode를 사용해 코딩하고싶지만 UE는 VSCode와 잘 맞지 않고 오히려 불편하다고 느껴 VS2017을 사용하여 코딩중이다. (UE4는 VS2017까지만 지원하는듯 하다... 아직 배움이 짧아서 더 지원하는지는 정확히 모른다.) 근데 자동완성이 진짜 한참 느렸다. 코드를 입력하면 항상 10초 뒤, 20초 뒤에 자동완성 추천이 뜨고 스크립트간 이동 하거나 에디터에 다녀오는 등 이러한 동작이 있을때마다 자동완성이 너무 느려서 속이 터졌다. 다음과 같은 방법을 사용하면 해결할 수 있다. VS를 켜고 도구 -> 옵션 -> 텍스트편집기 -> c/c++ -> 고급 -> 자동업데이트 사용안함을 True로..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net RGB거리 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.5 초 (추가 시간 없음) 128 MB 113629 63845 47407 55.288% 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 ..

개요 요즘 열심히 하는 게임이 생겼다. 하이 우동 호텔이라는 게임인데 이 게임에는 영화관이라는 컨텐츠가 있다. 방문하는 손님들의 요구사항에 따라 만족할만한 영화를 찾아서 상영시켜야한다. 지금은 상영중인데 위에 관람소원이라는 칸을 보면 손님들이 어떤 영화를 보고싶어 하는지 힌트를 준다. 처음 봤을땐 어느 장르의 영화를 상영해야하나 검색해보고 하나하나 고르는 작업을 했다. 하다가 보니까 이거 그냥 편하게 프로그램을 하나 짜서 하면 편하지 않을까 라는 생각을 하였고 바로 실행에 옮겼다. 다 만들고 안 사실이지만 계속 정확한 영화 요구를 들어주다가 보면 위의 주황색 글씨처럼 소원 맨 끝에 어떤 장르인지 뜨는 기능이 있었다... ㅠㅠ 콘텐츠 영화 관람 소원에 대한 정보는 다음 블로그에서 참고하였다. https:/..

2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 나무 자르기 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 192409 56640 35151 26.113% 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같..

0. 순차탐색 이때까지 했던 가장 많이 사용했던 탐색은 순차탐색이다. 별 어려운 알고리즘이 아니라 리스트의 요소 하나하나에 접근해 찾는 값이 맞는지 체크하는 알고리즘이다. #순차탐색 li = [1,3,2,5,4,6,7,9,8,0] #7을 찾으려면 for i in li: if i == 7: print("찾았다!") else: print("못찾았다!") 이처럼 간단하게 구현 할 수 있고, 장점은 정렬이 안되어 있어도 찾을 수 있다는 점이다. 이전글에서 배웠던 정렬 없이 사용할 수 있어서 좋다면 좋은 알고리즘이다. 하지만 리스트가 길면 길수록 시간이 더 더 걸린다는 단점이 있다. 이어서 이진탐색을 설명하겠다. 1. 이진탐색 이진탐색은 다음과 같다. 확실히 순차탐색보다 적은 수의 탐색을 하면 된다. 이진탐색을 ..

정렬 공부를 하면서 얻은 모든것을 정리한다. 정렬(sorting)이란, 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다. 정렬을 배워야만 다음 장의 이진탐색을 진행할 수 있기 때문에 정렬에 대한 정리를 하려고 한다. 0. 들어가기전에 정렬을 배우기 전에 알아둬야 할 코드는 스와프 코드가 있다. 다른언어(특히 c언어)는 구조적인 특성상 두 변수의 위치를 스왑하려면 별도의 함수가 필요하다. 하지만, 파이썬에서는 아주 간단하게 스왑을 할 수 있다. ///C언어에서 구현한 스왑 함수 include void Swap(int &a,int &b){ int temp = *a; *a = *b; *b = temp; } int main(){ x = 1; y = 2; Swap(1,2); printf("%d, %d",x..

문제 동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시외어있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 갯수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력조건 1. 첫째줄에 두 정수 N, M (4= m: continue if li[nx][ny] == 0: continue if li[nx][ny] == 1: li[nx][ny] = li[x][y] + 1 queue.a..

섬의 개수 성공다국어 한국어 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 68110 34562 24780 49.495% 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다..