본문 바로가기

About/Algorithm

 (45)
[백준 20055] 컨베이어 벨트 위의 로봇(Python 풀이) https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 해당 문제는 골드5 레벨의 구현 문제입니다. 풀이 0. 전역 변수 및 입력 1 2 3 4 5 6 7 8 from copy import deepcopy N, K = map(int, input().split()) robots = [] belts = list(map(int, input().split())) # 컨베이어 벨트 - 1차원 리스트로 표현(2*N개) belts.insert..
[백준 21609] 상어중학교 (C++ 풀이) https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 이 문제는 골드2 레벨의 구현 문제입니다. 문제 풀이에 주의할 사항은 다음과 같습니다. 1. 크기가 가장 큰 블록을 찾을 때 bfs 알고리즘을 이용하는데, 이 때 무지개 블록은 중복으로 사용해야 합니다. 2. 중력이 작용하는 경우 검정 블록(-1)을 만나면 거기서 블록이 멈춰야합니다 풀이 알고리즘 풀이 순서는 다음과 같습니다. 1. 가장 큰 블록 그룹 탐색 - find_largest_block..
[백준 21611번] 마법사 상어와 블리자드(Python 풀이) https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 이 문제는 골드1 난이도의 '구현' 문제입니다. 풀이 복잡한 과정을 좀 더 쉽게 풀이하기 위하여 2차원 격자를 1차원으로 변환하여 풀이하였으며, 절차가 많고 복잡하므로 단계를 함수단위로 나누어 풀이하였습니다. 풀이 순서는 다음과 같습니다. 1. 격자 초기화(2차원 -> 1차원) 2. 방향과 거리를 기준으로 구슬 파괴 3. 파괴된 구슬 정리 4. 연속하는 구슬 파괴 및 정리 5. ..
[백준 21610] 마법사 상어와 비바라기(Python 풀이) https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 이 문제는 골드 5 난이도의 구현 문제입니다. 문제에서 제시한 방향대로 코드를 구현한다면 쉽게 풀릴 내용이지만 다음 내용만 조심하면 될 것 같습니다. 이어진 격자 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에..
[백준 23288] 주사위 굴리기 2 (Python 풀이) https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 이 문제는 '주사위 방향에 따른 이동'을 풀어내는 것과 BFS 알고리즘을 활용하면 풀 수 있습니다. 풀이 주사위 이동 주사위 이동에 대한 함수는 따로 알고리즘으로 풀어내기 보다는 케이스가 4개뿐이기 때문에 규칙을 찾아 하드코딩으로 구현하였습니다. 주사위의 이동은 좌우로 움직이는 경우와 상하로 움직이는 경우로 나눌 수 있습니다. 그림으로 표현하면 다음과 같습니다. 따라서 주사위와 ..
[백준 23290] 마법사 상어와 복제(Python 풀이) https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 이 문제는 구현 문제로 문제에서 요구한 순서에 맞게 구현하는 것이 중요합니다. 주의할 점은 다음과 같습니다. 배열의 index가 0이 아닌 1번 부터 시작하도록 되어 있습니다. 물고기의 방향 정보 또한 1~8번 까지의 정보를 가지기 때문에 헷갈리지 않도록 조심해야합니다. 물고기의 냄새가 있는 곳은 '이동'을 못하는 것입니다. 따라서 물고기가 잡아 먹혀서 물고기 냄..
[Programmers] 표 편집(Python 풀이) - 2021 카카오 채용연계형 인턴십 코딩 테스트 문제 https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 풀이 이 문제는 효율성 테스트까지 통과해야합니다. 따라서 각 행들의 관계를 '링크드리스트(Linked List)' 자료형으로 정의하여 풀어야합니다. 일반 배열 자료형에 비해 링크드리스트의 경우 삭제/삽입의 시간복잡도가 O(1)인 점을 이용하여야 합니다. 링크드리스트에 대한 개념이 없는 분은 다음 링크를 참조하세요..
[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..

티스토리툴바