본문 바로가기
반응형

BOJ47

[Python] 백준 15645: 내려가기 2 sovled.ac 기준 Silver 1 개인적으로 알고리즘 문제 중 가장 수학적 사고력을 동반한 창의성을 요구하는 분야가 DP라고 생각한다. 저장할 공간의 효율과 동시에 방식을 스스로 정하여 수학 공식 처럼 점화식을 만들어 내야 하기 때문에, 수학 공부를 해야하나 고민하게 하는 분야 중 하나다. 문제N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다.. 2024. 6. 30.
[Python] 백준 1347: 미로 만들기 solved.ac 기준 Silver 2구현 문제의 매력은 문제 속에서 모든 해답을 찾을 수 있기 때문에, 한 없이 꼬아서 낼 수 있다는 점이다. 아니면 요구사항을 대폭 늘려서 코드 생산 효율을 줄여버릴 수도 있다. 이를 격파해내기 위해 설계하는 과정을 보기 위해 어려운 구현 문제는 꼭 필요한 것 같다. 해당 문제는 노트에 움직이면서 미로를 그리는 형식이기 떄문에 출력이 매우 유동적이라는 점이다. 이 부분에서 유추해내 문제를 풀었다.문제홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍준이는 미로에서 모든 행과 열의 이동할 수 있는 칸을 걸어다녔다. 그러면서 자신의.. 2024. 6. 29.
[Python] 백준 1326: 폴짝폴짝 solved.ac 기준 Silver2 난이도에 비해 유난히 낮은 정답률을 보여 풀게 된 문제이다. 하지만 문제를 해석해보면 BFS 활용 시 크게 어려운 문제는 아닌 듯 보이지만, 아마도 문제의 모호한 면이 문제의 정답률을 낮춘게 아닐까 하는 생각이다.문제개구리가 일렬로 놓여 있는 징검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오.입력첫째.. 2024. 6. 28.
[Python] 백준 21608: 상어 초등학교 solved.ac 기준 Gold5 구현 문제의 핵심은 지문을 잘 이해해서 풀이 속도를 높이는 것이다. 그래서 국어 비문학 문제와 같기도 하다. 사실 특별한 기술을 요하는 것이 없고, 어떻게든 풀 수 있게 나오기 때문에, 글에 나와있는 규칙을 이해하고, 코드로 옮기는 과정을 빠르게 해야한다. 그래서 이 문제처럼 긴 지문이 나오면 덜커덕 겁이 나기도 하지만, 세심하게 읽으면서 구조를 짠다. 한 3~4분은 키보드 안잡고 문제를 보며 구조를 생각하는 습관을 들이자. 문제 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의.. 2024. 4. 13.
[Python] 백준 20055: 컨베이어 벨트 위의 로봇 solved.ac 기준 Gold5 구현 문제의 장점은 문제만 읽어내면 어떻게든 풀 수 있다는 것이고, 단점은 문제만 읽어서 모든 것을 이해해내야한다는 것이다. 문제를 풀다가 자기확신에 빠져들지 않고 최대한 문제 지문에 코드를 일대일 대응 시키게끔 해야 풀기가 수월해지는데, 나는 중간에 자기확신을 가졌기 때문에 로직은 완벽히 짜고서 자그마한 수정만 하면 되는걸 많이 헤맨 문제였다. 문제 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부터 2N까지의 번호가 매겨져 있다. 벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고.. 2024. 4. 13.
[Python] 백준 1342: 행운의 문자열 백트래킹은 예전에도 나를 많이 괴롭힌 문제다. 모든 케이스를 다 보는 것이라서, 시간초과, 메모리초과가 항상 뒤따라다니는 알고리즘이기 때문이다. 그렇기에 적절하게 제약조건을 걸어줘서 시간복잡도와 메모리 관리를 모두 잡아내야한다. 문제 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다. 입력 첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다. 출력 첫째 줄에.. 2024. 4. 9.
반응형

티스토리툴바