본문 바로가기

Algorithm

 (9)
[백준 2309] 일곱 난쟁이 (c++) https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 이 문제는 아홉 난쟁이들 중 7명을 뽑아(조합)하여 키의 합이 100인 경우를 찾는 문제입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include #include using namespace..
[Programmers] 파괴되지 않은 건물 (Python 풀이) - 2022 KAKAO BLIND RECRUITMENT https://programmers.co.kr/learn/courses/30/lessons/92344 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr 이 문제는 쉬워보이지만 효율성 테스트를 통과하기 어려운 문제입니다. 효율성 테스트 실패 코드 문제를 처음 읽고 생각나는대로 알고리즘을 푼다면 보통 다음과 같이 코드를 작성했을 것입니다. 1 2 3 4 5 6 ..
[Programmers] 양과 늑대 (Python 풀이) - 2022 KAKAO BLIND RECRUITMENT https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr 풀이 이 문제는 이진 트리에서 조건에 따라 순회 가능한 모든 경우의 수를 탐색하면서 최대 양의 개수를 구하면 정답이 됩니다. 순회는 순서에 따라 영향을 받습니다. 따라서 같은 번호를 순회하더라도 여러 경우의 수가 ..
[Programmers] 신고 결과 받기 (Python 풀이) - 2022 KAKAO BLIND RECRUITMENT https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 from collections import defaultdict def solution(id_list, report, k): answer = [] report_to_from = defaultdict(set) # key(id)를 신고한 목록 report_from..
[알고스팟] 시계 맞추기(C++) 문제 설명 더보기 https://www.algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 www.algospot.com 예제 입력 2 12 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12 12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6 예제 출력 2 9 풀이 더보기 우선 스위치에 링크된 시계들을 다음과 같이 정의합니다. vector linkedClocks = { ..
[프로그래머스] 문자열 압축(Python 풀이) - 2020 KAKAO BLIND RECRUITMENT https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 더보기 문제 설명 데이터 처리 전문가가 되고 싶은 **"어피치"**는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습..
[백준 21608번] 상어 초등학교 (Python) 문제 더보기 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N^2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다. 비어있는 칸 중에서 좋아하는 학생..
[Algorithm] 보글(Boggle) 게임 문제 (C++) 다음 도서를 참고하여 작성하였습니다. http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9788966260546 알고리즘 문제 해결 전략 세트 - 교보문고 이 책은 프로그래밍 대회 문제를 풀면서 각종 알고리즘 설계 기법과 자료 구조에 대해 배우고, 나아가 문제 해결 능력까지 키울 수 있도록 구성되어 있다. 각 장에는 독자가 스스로 프로그램을 www.kyobobook.co.kr 문제 보글 게임은 다음과 같이 5 x 5 크기의 알파벳 격자를 가지고 하는 게임입니다. 목적은 상하좌우/대각선으로 인접한 칸들의 글자를 이어서 단어를 찾아내는 것입니다. 예를들어 위의 그림에서 (b), (c), (d)는 각각 PRETTY..
[Algorithm] n개의 원소중 m개를 고르는 모든 경우 찾기(C++) 0번부터 차례대로 번호 매겨진 n개의 원소 중 4개를 고르는 모든 경우를 출력하는 코드를 생각해봅시다. 만약 n = 6인경우 출력은 다음과 같습니다. (0, 1, 2, 3) (0, 1, 2, 4) (0, 1, 2, 5) ... 중략 ... (2, 3, 4, 5) 위 출력은 다음과 같은 4중 for문으로 간단하게(?) 해결할 수 있습니다. for(int i = 0; i < n; ++i) for(int j = i+1; j < n; ++j) for(int k = j+1; k < n; ++k) for(int l = k+1; l < n; ++l) cout

티스토리툴바