본문 바로가기
반응형

IT 톺아보기/알고리즘38

백준 23288번 | 주사위 굴리기 2 - python https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 문제 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있는 칸의 좌표는 (N, M)이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 각 면에는 1보다 크.. 2022. 10. 7.
백준 16234번 | 인구 이동 - python 문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은.. 2022. 10. 7.
백준 1107번 | 리모컨 - python https://www.acmicpc.net/problem/1107 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 입력 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤.. 2022. 9. 15.
[백준 14503번 | 삼성 SW 역량 테스트 기출] 로봇 청소기 - python 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음과.. 2022. 9. 14.
2022년 4차 Softeer 정기 역량 진단 코딩테스트 후기 9월 7일 현대자동차 그룹이 운영하고 있는 softeer에서 4차 정기 역량 진단 콘테스트를 진행했다. 일명 HSAT이라고 하는 시험인데 많은 대기업이 SW 인재를 확보하기 위해 자체 플랫폼을 제작하여 거기서 시험을 치고 일정 수준의 시험을 통과하면 인증서를 수여해주는 방식이다. 그중에서 현대 NGV에서 운영하는 소프티어(이하 'Softeer')는 현대자동차 그룹에서 진행하는 것으로 개인적으로는 시험 수준이 높다고 생각된다. 시험 방식은 노트북 캠과 휴대폰 캠을 둘 다 켜서 시험을 보는 방식이라서 시험 치기 전 독립된 공간에서 칠 수 있는지 확인하는 것이 시험에 집중할 수 있을 것이다. 이번 시험도 2문제를 180분(3시간) 동안 진행하는 것이었는데 3개 정도의 테스트 케이스만 주어지고 나머지 히든 케이.. 2022. 9. 7.
[백준 15686번 | 삼성 SW 역량 테스트 기출] 치킨 배달 - python https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로.. 2022. 9. 1.
백준 1991번 트리 순회 - python 해당 문제는 이진 트리의 전위 순회, 중위 순회, 후위 순회를 이해하고 있는지에 대한 문제라고 생각한다. 재귀를 이용해서 문제를 풀어 나갔는데, edge의 node들을 defaultdict에 리스트 형태로 저장해서 탐색을 진행해 나갔다. 순회하는 방식은 동일하지만 언제 출력을 진행하는 가에 차이에 따라 전위, 중위, 후위가 결정 된다. 그래서 아래의 함수를 보면 동일한 방식을 채택하고 있지만, 출력문의 위치만 다른 것을 볼 수 있다. def pre_order(n): if n != '.': print(n, end='') pre_order(edge[n][0]) pre_order(edge[n][1]) def in_order(n): if n != '.': in_order(edge[n][0]) print(n, e.. 2022. 7. 26.
백준 2004번 조합 0개의 개수 - python 처음 해당 문제를 봤을 때 팩토리얼을 활용하여 문제를 풀어도 되지만 시간초과가 날 것 같다는 생각이 들었다. 그러나 정말 그런지 궁금하니 한번 돌려보자.. from math import factorial n, k = map(int, input().split()) number = factorial(n) // (factorial(k) * factorial(n - k)) i = 0 while True: if not number % (10 ** i): i += 1 else: print(i - 1) break 해당 코드로 실행하니 당연하게 시가 초과가 발생했다. 이를 해결하기 위해 다른 방법에 대해 고민을 해 본 결과, m과 n-m의 최소값 만큼 반복문을 실행하는 방식을 진행해 보았다. n, k = map(int.. 2022. 6. 20.
[python]백준 21610번 - 마법사 상어와 비바라기 (feat. 삼성 SW 역량 테스트 기출 문제) https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 해당 문제를 푸는데 있어서 문제 이해를 하는데 어려움이 좀 있었고 다 구현한 뒤에도 시간 초과를 해결하는데 애를 먹었다. 최대한 함수를 이용하여 보기 쉽게 코드를 작성해봤는데 도움이 될 지 모르겠습니다. 아래 코드 참고 # d, s가 정해졌을 때 범위 안에서 움직이도록 만드는 함수 def moves(val, direction, sep, n): val = val + direction * se.. 2021. 12. 2.
반응형