시나위

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알고리즘 스터디의 첫 문제이다. 이 문제의 알고리즘은 Dynamic Programming 이다. 이웃하는 집의 색이 같지 않게 하면서 모든 집을 칠해야하고, 이 때의 최소 비용을 구해야한다. 제일 처음 생각했던 건 Greedy 방식이다. 매순간 마다 최소 비용을 선택하되 이웃하는 집의 색이 같지 않게 칠하면 된다. 3 1 100 100 100 100 100 1 100 100 위와 같은 입력에서 입력이 1번 집은 최소 비용이 1인 빨강을 선택..

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/submissions/ Lowest Common Ancestor of a Binary Search Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이진 탐색 트리에서 가장 가까운 공통 조상을 찾는 문제이다. 알고리즘 순서는 다음과 같다. 1. 주어진 root를 시작으로 BFS를 진행한다. 1-1. 이 때 unorde..

https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 투 포인터 문제이고 어렵진 않았다. 다만, try except를 사용해서 에러를 캐치해야하는게 별로 좋지 않은 문제인듯 하다. import sys; input = sys.stdin.readline def main(): while(1): try: # 0 input x = int(input()) * 10**7 n = int(input()) nums = [int(input())..

https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 꽤 오래 걸린 문제이다. 우선 어떻게 풀어야할지 감이 안왔다. 처음 문제를 봤을때 순열을 구하는 공식을 사용해서 만들어야하나 고민했다. 하지만 level 2에서 그런 문제가 나올리가 없다고 생각해서 다른 방법을 생각했다. 물론 공식을 사용해서 풀수만 있으면 훨씬 빠르게 끝낼수 있었겠지만 범위가 있어서 공식은 아니라고 판단헀다. 오랫동안 고민했는데 도저히 떠오..

https://www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 구현문제이므로 설명은 패스 import sys; input = sys.stdin.readline d = [(1, -1), (1, 0), (1, 1), (0, -1), (0, 0), (0, 1), (-1, -1), (-1, 0), (-1, 1), ] def calculate_direction(arduino, js): r1, s1 = js r2, s2 = arduino if r1 < r2: dr =..

https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 구현문제이다. # import sys; input = sys.stdin.readline def check_line(string, player): ret = False if player == string[0] == string[1] == string[2]\ or player == string[3] == string[4] == string[5]\ or player == string[6] == str..

https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 회문 체크하는게 굉장히 오래걸렸다. 처음 시도는 슬라이싱으로 했으나 시간초과가 되어 인덱스로 접근하는 방식으로 했다. # import sys; input = sys.stdin.readline def check_palindrome(string, start=None, end=None): if start is None: start = 0 if end is None: end = len(string) - 1 cnt = 0 pre_idx..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 구현문제여서 알고리즘 설명은 스킵. #include #include using namespace std; typedef struct Seat { int num; // student number int adj[4]; // u l r d int adj_student; // number of adjacent student } SEAT; SEAT arr[20][20]; int like[401]..

https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 브루트포스 문제이고 시뮬레이션 방식으로 풀었다. 알고리즘은 다음과 같다. 1. 입력 vector에 array를 추가하는 방식으로 이닝별 선수들의 행동을 저장했다. 2. 브루트포스 2-1. 1~9까지 순열 구하기(permutation) 2-2. 구한 순열로 시뮬레이션해서 점수 구하기 2-3. 최대 점수 갱신 1부터 9까지 숫자를 가지고 있는 배열(players_order)을 선언하고 algorithm 헤..

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 시뮬레이션 문제이다. 알고리즘 순서는 다음과 같다. 1. 입력 1-1. board: 격자 정보, fireballs: 파이어볼 정보 1-2. 0