본문 바로가기

나는 오늘,

 (371)
[BOJ] 배열 돌리기1 풀이 16926 맞았습니다!! 2696 100 C++14 / 수정 2001 1) 배열의 가장 바깥쪽 -> 안쪽-> 안쪽으로 계속 반복되어야 하기 때문에 cnt를 (가로, 세로 중 작은수)/2 로 정한다. 2) 배열을 돌릴 횟수 (r) 과 한 번 돌릴 때 반복되어야 하는 횟수 (cnt)를 파라미터로 받는 함수 rotate 정의 3) rotate에서 tmp는 처음 만나는 값을 저장한다. 이 배열이 주어졌을 때 배열의 가장 바깥쪽에서 가장 먼저 만나는 값은 1 이므로 tmp는 1을 저장한다. 1이 저장 되어야 하는 방향은 위-> 아래이므로 가장 먼저 위-> 아래로 가는 방향으로 돌린다. - 위 아래 방향이 끝났을 때 tmp에는 13 이라는 값이 저장되어있다. 13이라는 방향이 다음에 가야할 방향은 -> 이므로..
[BOJ] 불 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다. 각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다..
[SWEA] 점심식사시간 [문제] https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [풀이] 1) 조합 + 시뮬레이션 2) 문제를 읽고 단번에 파악할 수 없는 점은 사람들이 항상 가장 가까운 계단으로 가는 것은 아니라는 것이다. (최소 시간이 되는 계단이 꼭 가까이에 있는 계단이 아니기 때문에) 3) 그래서 모든 경우의 수를 구해줘야 한다. 다행인 건, 계단이 2개뿐이라는 것이다. (visited로 해결 가능) - people 백터에 사람들의 위치를 넣어주고 - stair..
[BOJ] 아맞다우산 5 5 ##### #S..E #...# #..X# ##### 7 *물건을 찾으러 가는 순서에 따라서 최단 거리가 결정이 된다. *물건에 번호를 매겨서 비트마스킹으로 하려고 했으나, 매번 값이 달라짐 *시작점, 물건, 도착점을 모두 하나의 백터배열에 저장하여 모두의 최단거리를 dp에 저장한다. (dp는 다이나믹이라기보다는 그냥 저장배열로 생각한다.) *시작점, 도착점을 제외한 물건들을 순열로 순서를 만들어 탐색하면서 최단거리를 저장한다. (처음 시작은 시작지점, 마지막은 도착지점으로 해야한다) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 ..
[BOJ] Maaaaaaaaaze [문제] 문제 평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다. 대회의 규칙은 아래와 같다. 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸을, 검은 칸은 참가자가 들어갈 수 없는 칸을 의미한다. 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있다. 그러나 판을 뒤집을 수는..
[BOJ] 야구 [문제] ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. 타순은 이닝이 변경되어도 순서를 유지해야 한다. 예를 들어, 2이닝에 6번 타자가 마지막 타자였다면, 3이닝은 7번 타자부터 타석에 선다. 공격은 투수가 던진 공을 타석에 있는 타자가 치는 것이다. 공격 팀의 선수가 1루, 2루, 3루를 ..
[BOJ] 색종이 붙이기 [문제] 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다. 종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자. 입력 총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다. 출력 모든 1을 ..
좌표의 크기가 너무 크다면? 좌표 압축 알고리즘 [알고리즘 기본 개념] 위 문제로 예를 들어보자면 x, y의 좌표는 최대 0,0~2^31, 2^31이다. 2^31은 int의 바운더리 안에 가깝게 들어오는 값이다. (int는 최대 2^32 = 20억정도) 만약, (0,0) 과 (2^31, 2^31) 을 비교하라고 하면 n의 범위를 2^31 로 둘 수 있을까? 시간 초과 결과가 나올 것이다. 컴퓨터가 1초에 처리할 수 있는 연산은 1억 정도. 그래서 인덱스를 이용한 좌표 압축 알고리즘이 있다. data = [[0, 0], [1, 1], [0, 2], [2, 0], [0, 3], [3, 2], [1, 4], [4, 4], [100, 50], [150, 30]] 이렇게 비교가 필요한 좌표가 주어진다면 x의 좌표와 y좌표를 따로 구분한다. xpoint = [0..

티스토리툴바