본문 바로가기

개발/algorithm

[백준 23288번] 주사위 굴리기2 - python 문제 링크 https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 풀이 백준 14499번 주사위 굴리기 를 풀었으면 그다지 어렵지 않게 풀 수 있는 문제이다. 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고.. 더보기
[백준 21611번] 마법사 상어와 블리자드 - python 문제 링크 https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 풀이 우선 나의 풀이는 pypy3 으로만 통과한다... 아래에서 python3으로 통과한 사람의 코드와 비교해 볼 예정이다. 구현 문제이고, 흐름은 다음과 같다. 우선, 2차원 배열로 된 graph을 new_graph에 1차원 배열로 바꿔주었다. 그리고 idx 라는 딕셔너리에 graph 인덱스(key) 별 new_graph의 인덱스(value)를 대입시켜주어 두 배열을.. 더보기
[백준 21609번] 상어 중학교 - python 문제 링크 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 풀이 나름 간단해보이는데, 난이도가 높다면 함정이 있다는 것 .. 여기서 주의해야할 점은 일반 블록 색은 모두 같아야하며, 무지개 블록은 상관없다는 것이다. 따라서 가장 큰 블록을 bfs를 사용해서 구할 때, visited 배열에 방문표시를 하게 되는데, 계산이 끝나면 무지개 블록은 다시 방문 표시를 해제해 주어야 한다... 사용한 주요 알고리즘은 다음과 같다. 1. 시계 방향 90.. 더보기
[백준 14499번] 주사위 굴리기 - python 문제 링크 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 회전 시 규칙을 찾아 풀어주면 된다. dice에 위치별 숫자를 저장한다. dice[0]은 주사위의 위 dice[1]은 뒤 dice[2]은 오른쪽 dice[3]는 왼쪽 dice[4]는 앞 dice[5]은 바닥 이라고 설정한다. 각 값을 a,b,c,d,e,f라고 한다면, 주사위를 오른쪽으로 돌렸을 때 위치는 a, b, .. 더보기
[백준 20058번] 마법사 상어와 파이어스톰 - python 문제 링크 https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 풀이 디버깅 정말 ... 힘들었다. 첫번째는 90도 회전시키는 것이 올바르게 구현되지 않아 힘들었다. 인덱스 별 변하는 위치에 따라 규칙을 찾아서 구현해줄 수도 있지만, 시험 때는 시간이 부족할 수도 있으니 외워두는 것도 좋을 듯하다. def rotate(x, y, l): # 회전한 배열 임시 저장 new =[ [0] * l for _ in range(l)] for .. 더보기
[백준 20057번] 마법사 상어와 토네이도 - python 문제 링크 https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 풀이 문제 이해가 잘 안돼서 애먹은 .. 1. 중앙에서부터 시작하는 토네이도 이동 규칙은 다음과 같다. 왼쪽 1번 -> 아래 1번 -> 오른쪽 2번 -> 위 2번 > 왼쪽 3번 -> 아래 3번 ... 따라서 홀수번째 일 때 왼쪽, 아래 이동 시 모래 양을 계산해주었고 짝수번째 일 때 오른쪽, 위 이동 시 모래 양을 계산해주었다. 2. 방향에 따른 모래 비.. 더보기
[백준 21610번] 마법사 상어와 바비라기 - python 문제 링크 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 풀이 난이도가 그렇게 높지 않은 구현 문제이다. 조건에 맞게 구현만 하면 되는 문제인데 디버깅에 적지 않은 시간이 걸렸다. 문제 조건이 모든 구름이 이동이 끝난 후에 다음 단계로 넘어가야 하는데, 하나의 구름이 이동할 때마다 대각선을 탐색하여 물을 올려줬기 때문이었다. 정말 사소한 실행 위치 차이가 .. ㅠㅠ 앞으로 이런 점에 유의해야겠다. # https://www.acmicpc.. 더보기
[백준 21608번] 상어 초등학교 - Python 문제 링크 https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 완전 탐색 문제 1. 학생을 자리에 배치할 때마다 graph를 완전 탐색하여 자리 별 인접한 칸의 좋아하는 학생 수와 빈칸 수를 구해서 heap에 삽입 2. heap에 (- 좋아하는 학생 수, - 빈칸 수, 행 번호, 열 번호) 를 삽입시켜줘서 조건에 맞는 자리 pop 3. graph에 학생 번호 표시하고, sheet 에 학생 자리 위치를 기록 4. sheet을 통해 만.. 더보기

티스토리툴바