본문 바로가기

BOJ

[백준 C++] 11053, 12015 가장 긴 증가하는 부분 수열 1, 2 가장 긴 증가하는 부분 수열 1 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 가장 긴 증가하는 부분 수열 2 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 자료 출처 1. [최장 증가 수열] LIS(Longest I..
[백준 C++] 9935번 문자열 폭발 문자열 폭발 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 www.acmicpc.net 자료 유형 : 스택인 줄 알았지만 문자열을 다루는 것이 핵심 문자열과 함께 나도 폭발했다. 수 차례 WA를 받고 주먹구구 식으로 코드를 고쳐나가는 내 모습이 비참했다. 문자열과 폭발 문자..
[백준 C++] 7785번 회사에 있는 사람 7785번 회사에 있는 사람 7785번: 회사에 있는 사람 문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성 www.acmicpc.net 문제 유형 : set 시간 복잡도 : nlogn 아래와 같이 n과 n만큼의 출퇴근 로그가 주어진다. 로그는 직원의 이름과 enter 혹은 leave로 주어지며, 현재..
[백준 C++] 나는야 포켓몬 마스터 이다솜 나는야 포켓몬 마스터 이다솜 문제 분류 : map(unordered_map) 전에 brute force로 풀려고 하다가 시간초과로 못 풀었던 문제다. map을 배우고 나니 풀 수 있을 것 같아서 시도해봤다. N개의 포켓몬 이름(string)을 입력받고, M개의 int 혹은 string을 입력받는다. int라면 int를 index로 삼아 포켓몬의 이름을 출력하고, string이라면 해당 포켓몬의 index를 출력하면 된다. 1. '이름 -> 인덱스'나 '인덱스 -> 이름' 중 하나만 해도 되는 것이라면 map 하나만 써서 손쉽게 해결할 수 있지만, 둘 다를 요구하기 때문에 string을 저장해놓는 별도의 array를 만들어야 한다는 점이 까다로웠다. 2. cin, cout보다 printf, scanf가 유..
[백준 C++] 6549번 히스토그램에서 가장 큰 직사각형(스택, 라인 스위핑) 히스토그램에서 가장 큰 직사각형 기록을 확인 해보니 정확하게 23일 전에 분할정복으로 해결하려고 했다가 시간초과 문제를 도저히 해결할 수 없어서 포기했던 문제다. 풀지 못했던 문제를 시간이 지남에 따라 풀 수 있게 되는 것도 알고리즘 공부의 쏠쏠한 재미인 듯 하다. 히스토그램에서 '가장 큰 직사각형'이 되기 위해서는 각 높이(height)를 가지고 만들 수 있는 가장 큰 직사각형 중 가장 큰 값이어야 한다. 각 막대는 자신보다 작거나 같은 최초의 막대를 왼쪽과 오른쪽에서 각각 하나씩 찾아야 한다. 왼쪽과 오른쪽 값을 찾는 것이 이 문제의 시간 복잡도를 결정짓는다. 나도 처음에 생각했던 Brute Force로 한다고 하자. 최악의 경우에 각 막대는 가장 왼쪽까지, 그리고 가장 오른쪽까지 탐색해야 결과를 얻..
[백준 C++] 1931, 4307번 회의실배정, 개미 - 그리디 알고리즘 회의실배정개미 이 링크에는 그리디 알고리즘(탐욕법)을 활용해 풀 수 있는 문제들이 몇가지 있다. '동전 0' 문제는 전에 풀어서 이번에는 풀지 않았고, 'ATM'과 '로프'는 상대적으로 난이도가 낮았으므로 따로 포스팅을 하지 않고, '회의실배정'과 '개미' 문제를 풀면서 그리디 알고리즘을 어떻게 적용시킬 것인지 고민해봤다. 그리디 알고리즘 그리디 알고리즘은 문제를 해결하기 위해 문제를 여러 개의 조각으로 나누고, 각 조각의 답을 바탕으로 답을 찾는다는 점에서 동적계획법과 비슷한 점이 있다. 하지만 동적계획법은 문제 해결을 위해 (거의) 모든 선택지를 고려해보고 그 중 답에 해당되는 것을 고르는 것인 반면, 그리디 알고리즘은 조각에 해당하는 작은 문제를 풀 때마다 최선의 방법만을 선택하기 때문에 최선이 아..
[Programmers C++] Winter Coding(재시도) 윈터 코딩 프로그래머스에서 주최하는 겨울 인턴 프로그램 코딩 테스트에 참가한 적이 있다. 알고리즘을 막 배우기 시작했던 단계였으며, C++은 아직 하지도 못했던 터라 Javascript로 참가했었다. 결과가 너무 처참해서 아직도 기억이 난다. 두 시간동안 세 문제를 풀어야 하는데, 두 번째와 세 번째 문제는 봐도 아무것도 모르겠어서 첫 번째 문제라도 풀어야겠다 싶어서 두 시간동안 그것만 풀었는데 그것마저 못 풀었다. 그 이후로 '이래서는 안되겠다' 싶어서 BOJ도 열심히 풀고, C++ 공부도 하고, 알고리즘과는 관련없지만 정보처리기사 준비를 위해 운영 체계 공부도 하며 겨울 방학을 알차게 보냈다. 방학이 끝나가는 지금 겨울 방학 동안 한 것의 성과를 확인하기 위해 겨울 인턴 프로그래밍 코딩 테스트 문제를..
[백준 C++] 7576, 7569번 토마토, 토마토 토마토토마토 두 문제 모두 BFS를 활용해서 풀 수 있기 때문에 이번 기회에 BFS를 연습했다. 비슷한 아이디어로 풀 수 있는 문제들이다. 두 문제 모두 상자에 있는 모든 토마토가 익는데 며칠 걸리는지 알아내는 문제다. 첫 번째 토마토 문제의 경우에는 상자가 하나 밖에 없으므로 상자의 가로, 세로 사이즈만 알면 풀 수 있지만, 두 번째 토마토 문제는 상자가 여러 개 있을 수 있기 때문에 가로, 세로 뿐만 아니라 높이도 알아야 한다. 그래서 조금 더 복잡하고 실수하기 쉽다. 두 문제의 공통적인 접근법은 다음과 같다. 1. 가로(M), 세로(N), 높이(H)는 int 타입으로 할당해 입력받는다. 하지만 칸 안에 토마토가 익었는지(1), 익지 않았는지(0), 아예 토마토가 없는지(-1)에 대한 정보는 int에..

티스토리툴바