본문 바로가기

Problem Solving/boj68

[BOJ] 8911. 거북이(Python) / Simulation www.acmicpc.net/problem/8911 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 www.acmicpc.net 실버2 문제라 그리 어렵지 않은 시뮬레이션 문제였다. 맵을 그릴 필요 없이 (0, 0) 위치에서 시작하여 문제에 주어진 조건 그대로 구현한다. L과 R의 경우는 방향만 바꿔준다. 이 때, 현재 방향을 각 경우별로 만들어놓은 방향 전환 리스트(dirL, dirR)를 참조하여 현 방향에 해당하는 인덱스로 바꾼다. F와 B의 경우는 현재 방향으로 한 칸 나아간다. 이 때, 이동한 위치를 min_r/c, max_r/c 최솟값과 .. 2021. 3. 9.
[BOJ] 1063. 킹(Python) / Simulation www.acmicpc.net/problem/1063 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 무난한 수준의 시뮬레이션 문제였다. King의 위치와 Stone의 위치를 입력받은 정보대로 움직이며 최종 위치를 출력한다. 이동 정보는 파이썬 Dictionary 자료구조를 활용해 이동할 곳을 Masking해주었다. Input 받을 때 좌표를 다루기 쉬운 숫자 형태로 변환하는 것과 이동 처리 후 Output할 때 다시 문자 형태로 변환하는 것이 꽤 까다로웠다. 이 때, 파이썬의 ord() 함수와, chr() 함수를 사용해.. 2021. 3. 9.
[BOJ] 9466. 텀 프로젝트(Python) / DFS www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 꽤 까다로웠던 DFS 문제였다. 각 학생이 함께 프로젝트 하고 싶은 사람들 지목하고 지목을 한 사람들끼리 사이클을 이루는지 여부를 파악하여 팀을 이루지 못한 학생들의 수를 계산해야 한다. DFS를 이용하여 1번 학생부터 n번 학생까지 방문표시하며 지목한 다음 학생의 번호를 차례대로 확인한다. 이 때, 사이클 리스트에 넣는데, 다음 숫자가 이 리스트에 있다면 사이클 이루는 경우이므로, 전체 학생의 수에서 사이클을 이루.. 2021. 3. 9.
[BOJ] 2023. 신기한 소수(Python) / DFS www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 원래 8자리로 10 ** 8 짜리 리스트로 에라토스테네스의 체를 사용해 미리 소수 0, 1 테이블을 만들어놓으려고 했는데, 메모리를 보니 4mb로 매우 작아서 백트래킹(Backtracking)으로 재귀로 들어오는 temp 값의 소수여부를 확인해 가지치기했다. 출력되는 소수값을 자세히 보면 맨 앞자리 수는 2, 3, 5, 7만 올 수 있고 2~N자리 수까지는 1, 3, 7, 9만 올 수 있어서 이를 반.. 2021. 3. 8.
[BOJ] 2661. 좋은 수열(Python) / Backtracking www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 깔끔한 Backtracking 문제였다. 1시간 22분 소요 Backtracking은 제약조건 만족문제에서 해를 찾는 방법이다. 개념 : 여러가지 경우의 수가 있는 문제에서 특정조건을 만족하는 찾는 데 있어, 조건을 탐색하다가 어느 순간 조건이 맞지 않는 것으로 판단되면 그 쪽의 경우의 수는 더이상 체크하지 않고 다른 경우의 수를 체크하는 것이다. 일종의 문제 푸는 전략으로, 알고리즘은 아니다. 고려할 수 있는 경우의 수를.. 2021. 3. 7.
[BOJ] 11053. 가장 긴 증가하는 부분 수열(Python) / DP www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net LIS(Longest Increasing Subsequence, 최장 증가 부분 수열 문제)는 가장 전형적인 Dynamic Programming 문제! 수열의 크기가 N일 때, 기본적인 DP 알고리즘으로 시간 복잡도 O(N^2)으로 해결할 수 있다. dp[i] = array[i]를 마지막 원소로 가지는 부분수열의 최대 길이 모든 0 2021. 3. 4.

티스토리툴바