전체 글
-
[Python] 백준 2580 스도쿠알고리즘/문제풀이 2021. 12. 12. 12:47
1. 문제 링크 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 2. 문제 요약 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 3. 아이디어 정리 백트래킹으로 진행 0으로 된 부분 모두 수를 채운 경우 그만 0으로 된 좌표에 어떤 값이 가능한지 모두 백트래킹 진행 4. 문제 풀이 4-1. 내 풀이 import sys..
-
[Python] 백준 15656 N과 M (7)알고리즘/문제풀이 2021. 12. 12. 12:43
1. 문제 링크 https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 2. 문제 요약 N개의 자연수 중 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 3. 아이디어 정리 증가하는 순서 출력이므로 정렬을 진행한다. 백트래킹으로 M개를 선택할 때 출력하게 한다. ⇒ 종료 조건 같은 수 여러 개 가능하기 때문에 for 문에 조건을 없이 넣는다. 4. 문제 풀이 4-1. 내 풀이 import sys def dfs(list_): if len(l..
-
Queue 두 개를 이용하여 Stack을 구현 & Stack 두 개를 이용하여 Queue를 구현CS(Computer Science)/Data Structure 2021. 12. 9. 17:30
1. Queue 두 개를 이용하여 Stack을 구현해 보세요 💡 큐 한 개는 메인 큐, 다른 큐는 임시 큐 용도로 둔다. 메인 큐에 값을 넣는다.(put) ex) 1→ 2→ 3 → 4 메인 큐에 1개의 원소가 남을 때까지 get 한 값을 임시 큐에 put 한다. 마지막 남은 원소는 result 변수에 저장한다. 임시 큐에 있는 원소들을 메인 큐로 모두 이동시킨다. (get → put) result 값을 리턴한다. 1-1. 순서 설명 메인큐에 값을 넣는다.(put) ex) 1→ 2→ 3 → 4 메인 큐에 1개의 원소가 남을 때까지 get 한 값을 임시 큐에 put 한다. 마지막 남은 원소는 result 변수에 저장한다. 임시 큐에 있는 원소들을 메인 큐로 모두 이동시킨다. (get → put) result..
-
[Python] programmers 뉴스 클러스터링알고리즘/문제풀이 2021. 12. 4. 23:36
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 2. 문제 요약 두 문자열의 자카드 유사도를 출력 자카드 유사도: 교집합 크기 / 합집합 크기 3. 아이디어 정리 문자열 2개씩 끊기 교집합, 합집합 구하기 다중집합 구하기 교집합: 두 교집합에서 갯수 최소값 합집합: 두 교집합에서 갯수 최대값 4. 문제 풀이 4-1. 내 풀이 import math def get_set(s)..
-
[Python] programmers 입국심사알고리즘/문제풀이 2021. 12. 4. 23:34
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 2. 문제 요약 모든 사람이 심사를 받는데 걸리는 시간 최솟값 구하기 3. 아이디어 정리 이분 탐색을 통해 걸리는 예측 시간을 구한다. 해당 예측 시간으로 몇 명이 허용되는지 확인 허용 가능한 인원으로 left, right 값을 조절 4. 문제 풀이 4-1. 내 풀이 def solution(n, times): answer = 0 left = 0 r..
-
[Python] 백준 15683 감시알고리즘/삼성 역량 문제 2021. 12. 4. 23:29
1. 문제 링크 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 2. 문제 요약 사각지대의 최소 크기를 출력 3. 아이디어 정리 각 cctv 모든 경우의 수 구하기 ⇒ 각 경우 별 감시 가능한 좌표를 모두 구한다. 백트래킹으로 모든 경우의 조합을 탐색한다. 최댓값인 경우 갱신한다. 4. 문제 풀이 4-1. 내풀이 def watch(x, y, dir): """ 해당 방향으로 보기 :return: """ set_ = set() for d..
-
[Python] programmers 교점에 별 만들기알고리즘/문제풀이 2021. 11. 27. 22:27
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/87377 코딩테스트 연습 - 교점에 별 만들기 [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, - programmers.co.kr 2. 문제 요약 Ax + By + C = 0으로 표현할 수 있는 ..
-
[Python] 백준 21921 블로그알고리즘/문제풀이 2021. 11. 27. 21:28
1. 문제 링크 https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 2. 문제 요약 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는가 3. 아이디어 정리 누적합을 먼저 구한다. 슬라이딩 윈도우로 특정 기간 동안 최대 값인 경우 방문자 수와 기간을 갱신한다. 4. 문제 풀이 4-1. 내 풀이 n, x = map(int, input().split()) # 블로그 일수, x일 동안 가장 많이 들어온 방문자 arr = list(map(..