관찰과 질문, 그리고 데이터

https://www.acmicpc.net/problem/1728117281번: ⚾⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 www.acmicpc.net 삼성A형 기출문제였고, 효율성을 고려하면 백준 환경에서 python 3으로는 사실상 풀 수 없는 문제. 1번 타자는 정해져 있고, 나머지 8명의..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다. www.acmicpc.net Python의 deque.rotate를 쓰면 쉽게 해결할 수 있는 문제. deque.rotate(iter) : iter 횟수만큼 deque의 맨 뒷 값을 맨 앞으로 이동시킨다. deque.rotate(-iter) : iter 횟수만큼 deque의 맨 앞 값을 맨 뒤로 이동시킨다. 해당 숫자가 있는 index를 구해..

https://www.acmicpc.net/problem/15997 15997번: 승부 예측 첫 번째 줄에 조별리그를 진행할 국가명 네 개가 공백으로 구분되어 주어진다. 주어지는 모든 국가명은 알파벳 대문자로만 구성된 길이가 1 이상 10 이하인 문자열이다. 두 번째 줄부터 일곱 번째 줄까지는 A B W D L 순으로 주어지는데, 전문가들의 예측에 따르면 A와 B가 경기를 진행했을 때 A가 승리할 확률은 W, 비길 확률은 D, 질 확률은 L이라는 의미이다. A, B는 각각 첫 번째 줄에 있는 국가명 중 하나이고, A와 B가 같은 경우는 주어지지 www.acmicpc.net 각 승부의 경우의 수마다 발생할 수 있는 모든 가능성을 확인하는 완전탐색 문제. 나는 이 문제에서 '확률'을 어떻게 사용해야 할지 감..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 www.acmicpc.net Union-find 문제.

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 백준에 삼성A형 기출문제로 분류되어 있다. 검색이 통제된 시험장 가서는 절대 못 풀 것 같은 문제. bfs로 라벨링하고 최소 거리 구하는 것까지는 혼자서 처리할 수 있었는데, union find 코드는 예전에 내가 쓴 코드 다시 보고 만들어야 했다. 문제를 풀기 위해 생각해야 할 개념은 크게 세 가지다. 1. 각 섬을 구분해 준다. (섬별로 Labeling 해 준다고 보면 된..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 기타 조건이 추가된 BFS문제. bfs로 좌표를 탐색하면서 '각 좌표별 상하좌우 값이 0인 경우의 개수'를 dictionary에 저장하고, ..

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과 www.acmicpc.net 2019년 어느 기업 코딩테스트에선가 이 문제를 봤었던 걸로 기억한다. stack을 사용하되, 이전 state를 저장하는 prev 변..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다. www.acmicpc.net 17298 '오큰수'와 푸는 방법이 똑같은 문제. 오큰수의 for문을 오름차순이 아니라 내림차순으로 돌면 된다. [Python] 백준 17298. 오큰수 스택을 사용해 풀 수 있는 문제. _ = input() # len(arr) 값과 똑같아서 패스 arr = list(map(int, input().split())) stack = [] # 값이 없으면 ..

https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 시뮬레이션 문제. c연산을 수행할 때 row와 column을 바꾸는 transpose 연산을 해줘야 하는데, python에서는 map과 zip함수를 써서 쉽게 변형할 수 있다.

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 www.acmicpc.net DFS 문제. 문제 자체는 쉽게 이해할 수 있었지만, 코드로 어떻게 구현할지가 머리 아팠던 문제. C++이나 자바로 풀었던 다른 코드에는 ..