본문 바로가기

Dev/Algorithm

 (20)
[백준] 1806 - 부분합 www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투포인터 문제다. 특별히 주의해야할 사항은 없고 left, right 두 인덱스를 이동시키면서 부분의 합을 S이상을 넘기면서, 가장 짧은 길이를 갱신해나가면 된다. 시간 복잡도는 O(N) #include #include using namespace std; unsigned int arr[100001]; int main() { int n, m; scanf("%d%d", &n, &m); for (in..
[백준] 1759 - 암호만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 일전에 풀었던 N-Queen 문제와 비슷한 백트래킹을 이용한 문제이다. (N-Queen 문제가 순수 백트래킹 알고리즘만을 이용하는 것이므로 백트래킹에 대해서 좀더 높은 이해를 원한다면 이전글을 참고할 것.) [Dev/Algorithm] - [백준] 9663 - N-Queen [백준] 9663 - N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen ..
[백준] 9663 - N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제의 이름 'N-Queen'은 사실 컴퓨터공학 전공으로 알고리즘 수업을 들었다면 수업시간에 접해봤을 문제중 하나다. 이 문제를 풀기위해선 백트레킹을 이용한 탐색 방법을 적용해야 하는데, 검색어 'N-Queen'으로 구글링만 해도 내가 첨부해놓은 하단의 답안보다, 더 가독성이 좋은 소스코드가 한무더기로 나온다. 위키백과에 있는 해설도 꽤 좋은 편이다. (gif로 해답을 얻어과는 과정도 보여준다.) 다만 백트래킹을..
[백준] 1920 - 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 최대 10만개의 숫자목록을 받은 후, 다음에 입력받는 최대 10만개의 숫자들이 이전의 숫자 목록에 존재하는지의 여부를 확인하는 문제다. 10만개 정도의 input이 주어졌을 때, 시간복잡도가 N^2이 되어도 1000억번의 연산이 필요하다. N log N으로 시간복잡도를 끊어야 하는데, 이 문제의 경우는 검색 대상인 숫자 목록을 정렬을 시켜놓고 이분탐색을..
[백준] 1039 - 교환 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 처음엔 문제를 읽고 '연산을 K번 할 수 없다' 라는 의미가 뭔지를 이해하지 못해 한참 생각을 했다. 주어진 정수의 각 자리수를 바꿀때 자리수가 짧으면 K번을 교환할 수 없는 경우가 생긴다. 이에 대한 처리를 해줘야 하는데 K번의 최대값이 10이므로 BFS를 통한 완전 탐색이 가능할 것 같았다. 구현시 유의할 점은 다음과 같다. K번을 바꾼 뒤의 정수가 최대값이어야 하며, 바꾼 과정에서의 최대값은 의미가 없다. BFS로 Queue에서 Push시에 바꾼 정수의 앞자리가..
[백준] 1103 - 게임 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 문제에서 제시하는 map의 사이즈가 최대 50x50이라 시간초과가 날 일은 없을 것이라 생각하고, DFS(깊이우선 탐색)을 통한 완전 탐색을 하면 될 줄 알았다. 그런데 문제를 다시 읽어보니 말을 움직이는데 있어 중간에 사이클이 생길 수 있네? 사이클에 대해서는 같은 map 사이즈로 visited 배열을 선언해서 이전에 방문한 적이 있으면 -1을 출력 후 리턴을 하게 해주었는데, 같은 위치를 가더..
[백준] 1713 - 후보 추천하기 https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 � www.acmicpc.net 이문제 또한 특별한 알고리즘보단 구현력을 요구하는 문제다. 3회 시도만에 성공했는데 이게 정보올림피아드 초등부 1번이라니 -_-;;; 구현시 주의해야할 부분은 이정도다. - 정렬함수 qsort나 sort를 쓸때 정렬 규칙을 커스텀해야 한다. - 간단하게는 배열이나, STL을 사용한다면 벡터를 이용해 인덱싱을 통한 자료 접근에 대한 구현해야 한다. 코드가 심각하게 지저분하다;;; STL을 사..
[백준] 1062 - 가르침 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 처음엔 좀 쉽게 생각했다. ASCII 코드에 대한 이해도와 입력되는 문자열에서 나타나는 알파벳의 발생 횟수를 기억해놓고 이를 내림차순으로 정렬하면 배우는 글자 수에 따라 읽을 수 있는 단어 갯수를 알아낼 줄 알았다. 그런데 해보니까 아니네... 이번 문제에서 필요한 지식은 이정도가 될것 같다. ASCII 코드에 대한 이해를 통해 알파벳 별 출현 여부를 bit masking하여 배열에 저장하..
[백준] 3055 - 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치�� www.acmicpc.net 자료구조인 Queue와 BFS(너비우선 탐색)에 대한 이해가 필요한 문제다. 물이 차오르는 것과, 고슴도치가 이동하는 것 두가지에 모두 BFS를 적용할 수 있지만 나는 별생각 없이 고슴도치의 이동에 대해서만 BFS를 적용하였고, 물이 차오르는 것은 무식하게 for문을 돌렸다. 그럼에도 pass는 나온다. 처음엔 완전탐색으로 DFS(깊이 우선 탐색)을 해보았으나 시간초과가 나온다. 이미 갔던 곳에 대해 필터..
[백준] 3425 - 고스택 https://www.acmicpc.net/problem/3425 3425번: 고스택 문제 고창영은 스택을 조금 변형해서 고스택을 만들었다. 고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다. 편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고 � www.acmicpc.net 내가 다니는 회사는 알고리즘 역량을 시험으로 본다. 시험 결과를 통해 역량이 등급으로 나뉘어지는데 pro를 취득하라는 회사의 푸시가 상당하다. 그래서 매해 회사에는 여름쯤하여 스터디 그룹이 생겨났다가.. 참여율이 저조하고, 몇달 안있어 사라지는 상황이 반복되고 있다. 올해도 스터디 그룹이 생겼다. 올해는 스터디 그룹원들에게 알려줘야 하는 입장이 되는 바람에... 좀 열심히 해야하는 이유가 생겼다. 이..

티스토리툴바