본문 바로가기

About/Algorithm

 (45)
[Programmers] 수식 최대화(Python 풀이) - 2020 카카오 인턴십 코딩테스트 문제 https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 풀이 수식의 분리(숫자와 연산자 배열) 먼저 수식을 숫자와 연산자로 분리합니다. get_numbers_and_exps() 함수는 수식을 받아 숫자 배열과 연산자 배열을 반환합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def get_numbers_and_exps(expression): # 수식을 숫자와 연산자 배열로 분리 exps = []..
[백준 8972] 미친 아두이노(Python 풀이) https://www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 풀이 문제 조건만 잘 확인해서 구현하면 쉽게 풀리는 문제였습니다. 입력 1 2 3 R, C = map(int, input().split(' ')) board = [list(map(str, input())) for _ in range(R)] moves = list(map(int, input())) cs 연속된 문자열 형태로 입력되기 때문에 위와 같이 map을 이용하여 list 형태로 입력받습니다...
[백준 20058] 마법사 상어와 파이어스톰(Python 풀이) https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 풀이 이번 문제는 배열의 회전, BFS를 이용하여 풀 수 있습니다. 풀이는 다음과 같습니다. 우선 다음과 같이 입력을 받습니다. N, Q = map(int, input().split(' ')) # N, Q len_board = 2 ** N # 얼음을 저장할 보드의 길이 board = [list(map(int, input().split(' '))) for _ in range(le..
[백준 16985] Maaaaaaaaaze(Python 풀이) 풀이 이 문제는 브루트포스, 순열, BFS를 이용하여 풀어야한다.(이외에도 배열 회전 알고리즘 등 복잡한 문제이다.) import sys from collections import deque from itertools import permutations board = [[list(map(int, input().split(' '))) for _ in range(5)] for _ in range(5)] b = [[[0] * 5 for _ in range(5)] for _ in range(5)] result = sys.maxsize dh = (0, 0, 0, 0, 1, -1) dy = (0, 0, 1, -1, 0, 0) dx = (1, -1, 0, 0, 0, 0) 다음과 같이 입력을 받고, result, dh..
[백준 1202] 보석 도둑(C++ 풀이) https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 이 문제는 우선순위 큐를 이용하면 간단하게 풀 수 있다. 우선 보석의 정보와 가방의 정보를 담을 배열 그리고 우선순위 큐를 다음과 같이 정의한다. pair v_jewerly[MAX]; int v_bag[MAX]; priority_queue pq; 원래는 vector 자료형을 사용했었는데, 배열 최대크기(MAX = 300001)가 너..
[백준 4256] 트리 (C++ 풀이) https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 풀이 preorder와 inorder의 결과를 이용하여 범위 내에서 중심이 되는 지점(좌우로 나뉘는 기점)을 찾고, 이를 기준으로 left/right로 범위를 나누어서(분할정복) 재귀함수를 호출하며 postorder의 결과를 출력합니다. void post_order(int start, int end, int pos){ for (int i = start; i < end; ++i) { if..
[백준 23291번] 어항 정리(C++ 풀이) https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 더보기 우선 NxN 형태의 2차원 벡터를 이용하여 어항의 배치를 표현하였으며, 어항이 존재하지 않는 좌표는 -1로 표현하였다. 그리고 문제에서는 어항이 위로 쌓이게 되지만 편의상 배열의 아래로 쌓이도록 표현하였다. 따라서 위 그림을 배열로 표현하면 다음과 같다. 코드 상에서는 board라는 변수를 사용한다. 1 2 3 4 5 6 7 8 -1 -1 3 14 9 3 11 8 -1 -1 3 5 -..
[백준 2638번] 치즈 (C++ 풀이) 2638번: 치즈 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 더보기 더보기 치즈의 "외부 공기"와 "내부 공기"를 BFS로 판단한 후 각 치즈의 상하좌우의 값을 확인하여 녹일 치즈를 정한다. 다음은 findAirStatusBFS()는 BFS를 이용하여 외부 공기를 판단하는 함수 // BFS를 이용하여 외부공기 판단 void findAirStatusBFS() { queue q; used = vector(N, vector(M, false)); q.push(make_pair(0, 0)); /..
[알고스팟] 시계 맞추기(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 = { ..
[백준 16234번] 인구이동(C++) 풀이 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 더보기 복잡한 2차원 영역을 1차원으로 변환한 후 bfs 알고리즘을 이용하여 문제 해결하였습니다. 위 사진 처럼 각 국경선이 열린 경우 점선으로 표시가 되는데 이를 나타내기 위해서 2차원 영역을 1차원으로 변환하는 게 좋다.(구현이 가능하지만 복잡해지기 때문에) 각 2차원 좌표에 차례대로 번호를 붙여 1차원 좌표로 변환한다. 2차원 좌표를 1차원 좌표로 변환하는 코드는 다음과 ..

티스토리툴바