본문 바로가기

Dev

 (37)
[백준] 2580 - 스도쿠 www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 스도쿠 맵을 입력받아 말그대로 프로그램이 스도쿠 맵을 완성하도록 하는 문제이며 백트래킹 문제다. 백트래킹보다는 스도쿠 맵에서 숫자 후보군의 정합성을 판단하는 로직의 구현력이 더 중요한 문제같다. #include using namespace std; #include #include int map[9][9]; bool col[9][9]; bool row[9][9]; bool squ[9][9]; void solve(..
[백준] 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..
Authorization Code 방식으로 티스토리 API를 이용하자 - 근성판 [Log] - 티스토리 API가 재대로 동작하지 않았던 이유를 알아내다. 티스토리 API가 재대로 동작하지 않았던 이유를 알아내다. 9월 1일부터 주식 종목분석 자동 포스팅이 올라오지 않았다. [Log] - 티스토리 API에 다시 문제가 생겼다. 티스토리 API에 다시 문제가 생겼다. 9월 1일부터 개발했던 종목분석기의 기능인 티스토� nemowork.com 몇일 전까진 티스토리 API가 안되는 이유에 대해서 알아냈었고, 그렇다면 '이제 어떻게 해야하는가?'에 대한 고민을 하기 시작했다. 시간이 많다면 주식 정보를 간단하게나마 공유하고 내가 보길 원하는 정보를 더 보기 좋게 할수 있도록 작은 웹서비스나 앱이라도 만들어보겠지만 그럴시간이 없다. (난 둘째를 키워야 한다.) 티스토리 API 소스코드를 어떻게..
[백준] 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하여 배열에 저장하..

티스토리툴바