Devlog_by_0giru

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 드디어 풀었다. 풀고나니 허무할 정도였다. 아마 이 문제 제일 오랫동안 못푼사람일듯 아마 필자처럼 이 문제를 오래 풀 사람은 없겠지만...혹시 몰라 자세히 적어보려한다 ㅠㅠ 이 문제는 사실 N * N의 배열을 만들어서 풀어도 된다. 그게 틀린 풀이가 아니지만 최적의 실행시간을 가지기 위해서는 반드시 1차원 배열(필자는 파이썬을 이용했기 때문에 리스트)을 사용해야 하는 모양이다. 2차원 배열을 이용해 실제 체스판 ..

https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 따로 어려웠던 내용이 없는 간단한 문제였다. 노란색은 항상 중앙에 모여있으므로 n개가 주어질 때 약수 쌍을 구분하는 것이 포인트다. ex) 노란색이 24개 일 때, 가로 세로가 1줄-24줄 or, 2줄-12줄 or 3줄-8줄 ... 등등 해당하는 약수 쌍이 나왔을 때, 큰 값 - 작은 값 순으로 정렬해서 리턴해주었다. def getBrown(col, row)..

programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr DFS/BFS 분류로 되어있지만 문제를 풀 때에는 어떻게 풀어야 할지 참 난감했던 문제다. 각 숫자 앞에 -, + 두 가지의 연산자가 올 수 있어 시간복잡도는 최악의 경우 O(2^n)이 나오는데, 입력의 수가 최대 20개였기 때문에 그냥 완전탐색으로 시도해 해결했다. from itertools import combinati..

programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 순열을 활용해볼 수 있었던 문제였다. 처음에는 문제를 잘못 이해해서 중복순열을 사용했다가, 문제를 다시 읽어보니 사용한 카드를 다시 사용할 수 없어 순열을 이용해 해결할 수 있었다. 소수를 판별하는 로직을 기억해두는 것이 좋을 것 같다. from itertools import permutations def Prime(toTest): if toTest == 0 o..

www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 어떻게 풀지 어떻게 풀지 이게 왜 실버문젤까 하면서 꽤 오래 고민했던 문제다. BFS문제는 격자 혹은 좌표형태의 문제만 풀어봐서 그런지 어떻게 BFS로 푼다는 말인가 오랫동안 이해가 안갔었지만 큐를 이용해 갈 좌표들을 하나 씩 점검해주는 방식으로 푸니 이게 결국 BFS였다. 문제의 TC로 나온 예를 이용해 설명해보면, 처음에는 위와 같은 형태의 계층 구조가 있고 빈 큐를 이용한다. 우리는 3과 ..

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2차원 다이나믹 프로그래밍을 활용하는 대표적인 문제다. 원래는 '안녕_1535' 문제를 풀기 위해 먼저 풀어본 문제인데, 백트래킹을 이용한 재귀함수 호출로 풀려고 시도해봤지만 시간 초과로 통과하지 못했다. pypy3로도 안되더라. 처음 내가 시도했던 방법을 그림으로 그렸다. 물건이 A B C D 네 가지가 있다고 가정한 후 각 물건을 넣느냐, 마..

www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N( result: result = cur_joy return # 현재 사람을 선택할 경우 Recursion(idx+1, cur_joy+joys[idx], cur_life-costs[idx]) # 현재 사람을 선택하지 않을 경우 Recursion(idx+1, cur_joy, cur_life) Recursion(0, 0, life) print(result) 2차원 다이나믹 프로그래밍을 이용한 풀이 (체력을 깎아가는 방식이 아닌 0에서 채우는 방식으로 풀었다.) """ 2차원 DP를 이용한 풀이 """ n = int(input()) costs = [0] joys = [0] cost = list(map(int, inpu..

가장 긴 증가하는 부분 수열1 에 이은 시리즈 문제다. 처음에는 11053번처럼 dp로 접근하려고 했지만 입력 데이터의 수가 너무 많아 dp로 해결할 수 없는 문제임을 깨달았다. dp를 이용하려면 전체 리스트(배열)에서 i번째와 i-1번째까지의 데이터를 중복해서 탐색해 O(N^2)의 시간 복잡도를 가지게 된다. 11053번의 경우 입력 데이터의 개수가 1000개 까지라 시간 초과에 걸리지 않지만 12015번의 경우 입력 데이터가 훨씬 많아 O(N^2)의 시간복잡도를 가진 알고리즘을 사용할 경우 시간 초과가 발생한다. 따라서 O(NlogN)의 시간 복잡도로 해결해야 하고 이를 위해 i-1번째까지의 데이터를 이진탐색을 통해 시간을 단축해줘야 했다. 사실 위 부분까지는 이해가 되는 부분이나, 아래 부터 나오게..