끵뀐꿩긘의 여러가지

문제링크 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 전구의 상태를 바꾸면 양옆 전구가 바뀌기 때문에 두번째 전구부터 시작해서 이전 전구의 상태가 희망하는..

문제 링크 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 문제 설명/ 풀이 - 그래프에서 사이클 찾기 사이클을 검출..

문제 링크 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 1062 가르침, 2668 숫자고르기에 먼저 도전했지만, 비트마스킹과 유향가중그래프라는 벽에 막혀 문제를 풀지 못하였다 담주에는 꼭 둘 중 하나를 풀어서 포스팅하겠다 문제 설명/ 풀이 이차원 배열로 그림의 모양을 받고, 처음부터 돌면서 1인 지점을 발견하면 n으로 바꿔주며 bfs를 수행한다 bfs를 모두 수행하면 그림의 숫자를 n+1로 바꿔주고 이차원 배열을 모두 탐색한다. 모두 탐색한 후 ..

문제 링크 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 문제 설명 / 풀이 생각해야 하는 부분 1. 이 괄호들이 올바른 괄호열인가? ex. (()[[]]) => 올바른 괄호열, ][[](]) => 올바르지 않은 괄호열 이 부분은 일반적으로 stack으로 풀 수 있다 2. 괄호열 규칙에 대한 계산 방법 () == 2, [] == 3, ([]) = 2*3, ([]()) = 2*(3+2) 같은 깊이의 괄호끼리는 덧셈으로 연산하고, 다른 깊이의 ..

문제 링크 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제 설명/ 풀이 정답률도 55퍼이고 그냥 보기엔 쉬워보였는데, 코드를 짜다보니 반례가 많이 생겨서 생각보다 시간이 엄청 오래 걸렸다 고려해야할 조건 1. 물은 양쪽에 기둥이 있을 때 채워진다 위의 그림과 같은 경우 물이 채워지지 않는다 2. 양 기둥의 높이가 다를경우 낮은 기둥의 높이에 맞춰 물이 채워진다 가설-1: 양 기둥은 감소배열의 최대값과 증가배열의 최대값이다..

문제 링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 설명/ 풀이 전형적인 재귀로 푸는게 편한 dfs문제 재귀를 통해 연산을 끝까지 해주고 결과값을 최대와 최소값을 비교하면 된다. 코드 import sys # 재귀 함수를 사용하여 dfs 구현 def recursive(N, l, op, total): # N 남은 연산 횟수, ㅣ: 숫자배열, op: 남은 연산자, total: 계산 ..

문제 출처 이것이 취업을 위한 코딩 테스트다 - p.388 화성탐사 문제설명/풀이 - 문제 당신은 화성 탐사 기계를 개발하는 프로그래머다. 그런데 화성은 에너지 공급원을 찾기가 힘들다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 한다. 화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재한다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N - 1][N - 1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하라. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다. a. 입력 조건 첫째 줄에 ..

문제링크 https://www.acmicpc.net/problem/15501 15501번: 부당한 퍼즐 현욱은 퍼즐 게임을 굉장히 좋아한다. 어느 날 현욱은 친구로부터 간단한 플래시 퍼즐 게임을 하나 추천 받았는데, 이 퍼즐 게임은 다음과 같은 규칙을 갖고 있다. 플레이어는 1 ~ n 까지 숫자가 www.acmicpc.net 문제 설명/ 풀이 수열을 조작할 수 있는 방법은 1. 뒤집기와 2. 밀기 밖에 없으므로, reverse()메소드로 뒤집기를 해결하고, 리스트를 원순열로 만들어서 밀기를 해결하기로 생각했다. - 수열을 원순열로 만들기 rotate 메서드가 있지만, rotate()는 항상 수열의 끝 길이나 첫 길이에서 index 값을 조정해주어야해서 indexing 하기 힘들다. 그래서 나는 메모리를 ..