728x90 BOJ 썸네일형 리스트형 [백준알고리즘] 6549번: 히스토그램에서 가장 큰 직사각형-C++ 6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net) 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 보니까 2년 전에 풀다가 말았던 문제인 것 같다. 파이썬으로 풀려고 시도했던 흔적이 남아있다. 플레티넘 5라고 해서 너무 쉬운 방법은 안 풀릴 거 같았다. 조금 생각해서 스택을 이용해 푸는 방법을 생각했고, 약간 지저분해 보여 조금 아이디어를 가다듬고 문제를 풀었다. 사실 바로 풀릴지 모르고 했는데 돼서 놀랬다. 해당 문제에 대한 게시판.. 더보기 [백준알고리즘] 11444번: 피보나치 수 6 -C++ [백준알고리즘] 11444번: 피보나치 수 6 -C++ 11444번: 피보나치 수 6 (acmicpc.net) 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 골드 난이도면서 정답 비율이 높길래 되게 쉬운 문제인 줄 알았다. 근데 난생처음 보는 풀이를 보고 따라 풀었다. 이 문제를 푸는 방법은 2가지가 있다고 한다. 행렬 곱을 이용한 방법과 방정식을 이용한 방법이다. 아래는 방정식으로 문제를 풀었다. 문제를 푸는 방식은 백준 블로그의 글을 참고했다. 피보나치 수를 구하는 여러가지 방법 (acmicpc.net) 피보나치 수를 구하는 여러가지 방법 피보나치 수는 다음과 같이 정의되는 수열입니.. 더보기 [백준알고리즘] 1802번: 종이 접기 -C++ [백준알고리즘] 1802번: 종이 접기 -C++ 1802번: 종이 접기 (acmicpc.net) 1802번: 종이 접기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1 www.acmicpc.net 문제만 읽었을 때는 되게 어려운 문제라고 생각했다. 문제를 푸는 방법을 찾았을 때도 시간 초과가 괜찮을지 걱정했었는데 여유로운 시간이었다. 정답 비율만 보고 살짝 어려운 문제인가 싶었는데 실버 문제는 실버 문제였다. 분할 정복으로 분류되어 있는데, 분할 정복인가.. 싶긴 하다. 문제 풀이 문제의 내용은 사실 대부분이 불필요한데 괜히 길다. 아무튼 원룡이가 막 접었.. 더보기 [백준알고리즘] 2470번: 두 용액 -C++ [백준알고리즘] 2470번: 두 용액 -C++ 2470번: 두 용액 (acmicpc.net) 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 골드 5의 문제다. 정답 비율도 낮아서 생각보다 어렵나 하고 풀었는데 생각보다 훨씬 쉽게 풀리긴 했다. 예전에 비슷한 느낌의 문제를 푼 적이 있던 것 같은데, 그 덕분인지는 모르겠다. 전부터 골드 5의 문제들이 적당히 난이도 있고 풀기에 좋았던 것으로 기억한다. 그래서 진짜 어려운 문제는 아니었을 수도 있다. 문제 풀이 문제에서는 여러 .. 더보기 [백준알고리즘] 10867번: 중복 빼고 정렬하기 -C++ [백준알고리즘] 10867번: 중복 빼고 정렬하기 -C++ 10867번: 중복 빼고 정렬하기 (acmicpc.net) 10867번: 중복 빼고 정렬하기 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. www.acmicpc.net 사실 이번 문제는 굉장히 쉬운 문제다. 정렬 알고리즘이라고 해서 풀려고 했는데, 너무 민망할 정도의 문제다. 그래서 글을 따로 작성하지 않으려다가 그냥 기록용으로 남긴다. 문제 풀이 문제에서 요구하는 조건 중에 주목할 것은 오름차순 정렬과 중복을 제거하는 것이다. 가장 먼저 생각이 든 것은 C++의 set를 이용하는 방식이다. set는 JAVA의 HashSet과 유사한 개념이다.. 더보기 [백준알고리즘] 2589번: 보물섬 -C++ [백준알고리즘] 2589번: 보물섬 -C++ 2589번: 보물섬 (acmicpc.net) 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 문제를 봤을 때 브루트 포스인가? 단순히 최단거리는 못 구하는데? 일단 해보자! 했다. 예전에는 너무 최단거리 문제만 풀다가 브루트 포스 문제 여부를 감을 잡지 못했었는데, 지금 오히려 눈이 넓어졌나보다. 골드라고 해서 살짝 쫄았는데 정답 비율은 생각보다 높았다. 어쩐지 어렵진 않더라.. 문제 풀이 문제는 브루트 포스 방식을 사용하면 된다. 그리고 그래프 탐색을 사용하면 된다... 더보기 [백준알고리즘] 18111번: 마인크래프트 -C++ [백준알고리즘] 18111번: 마인크래프트 -C++ 18111번: 마인크래프트 (acmicpc.net) 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 실버 문제 치고는 정답률이 낮다. 문제를 풀면서 그럴만하다고 느낀 게 실수하기 쉬운 부분이 있다. 다만 어려워서 그런 것은 아니기 때문에 반례도 생각하면서 풀어보면 좋을 문제다. 나는 생각한 반례도 다 돌아는 갔는데.. 통과를 못해서 반례 모음이 올라온 것을 보고 잘못된 부분을 찾을 수 있었다. 그리고 최대한 함수를 작게 나눠서 작성하고 있는데, 확실히 오류 .. 더보기 [백준알고리즘] 5639번: 이진 검색 트리 -C++ [백준알고리즘] 5639번: 이진 검색 트리 -C++ 5639번: 이진 검색 트리 (acmicpc.net) 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 생각보다 애를 먹었다. 처음에 list 자료형을 이용해 splice 함수로 이리저리 preorder를 postorder로 바꾸려고 시도해봤다. 동작은 하는 것 같으나, 시간 초과/메모리 초과가 발생해 고민을 많이 했다. 그러다가 배열을 쓰는게 훨씬 빠르다는 것을 보고, 배열과 인덱스를 이용해 처리하도록 변경했다. 문제 풀이 트리 탐색 방법은 전.. 더보기 이전 1 2 3 4 5 ··· 32 다음