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/42747# 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 프로그래머스 문제는 종종 문제 자체가 이해가 잘 되지 않는 경우가 많다. 아직 레벨2 따리지만... 논문의 인용 수 h를 norm(기준이라는 뜻)이라는 변수로 지정하고 0으로 초기화 한뒤 1씩 올려가는 while 반복을 통해 norm 이상으로 인용된 논문 수를 구하는 방식으로 구했다. 문제의 포인트는 h번 이상 인용된 논문의 개..

https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 일단 문제 해석이 어색하게 될 수 있어서 좋은 문제는 아니라는 생각이 든다. 질문을 검색하면 다른 사람들도 문제 이해에 많은 혼란을 겪은 듯 하다. 문제에서 주식 가격이 바로 다음 순간에 바뀌더라도, 1초간 가격이 변동되지 않았다는 것으로 간주해야 한다는 점이 포인트이다. 즉, 다음 원소가 더 작은지 여부를 판단하기보단 ..

https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 레벨2 문제라고 쉽게 생각했다가 몇일동안이나 고민했다. 프린트 순서를 만지는 방법은 금세 떠올랐지만 코드로 구현하는 능력이 부족했다. 근처 난이도의 문제를 더 풀며 구현능력을 키워야 한다ㅠㅠ 두가지 방법을 풀 수 있었는데, 먼저 두 방법 모두 큐를 사용하기 위해 collection의 deque를 import 했다. 첫번 째 방법은 아래 코드블럭에서 주석처리한 방법이..

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과 ..