본문 바로가기

Problem Solving/boj

 (68)
[BOJ] 1316. 그룹 단어 체커(Python) 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. 사용 알고리즘 : 문자열 + 구현 코드 설..
[BOJ] 13335. 트럭(Python) / Simulation 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 문제 설명다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라. # 21분 소요 사용 알고리즘 : 문제에서 주어진 그대로 구현하는 Simulation 문제 전체적인 흐름은 아래 코드에 주석으로 달아놓았고, solve() 함수에서 중요! 표시한 부분을 보면, trucks에서 맨 앞의 트럭이 다리로 이동할 수 있는 ..
[BOJ] 3980. 선발 명단(Python) / DFS, Backtracking 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 11개의 포지션에 11명의 선수를 채웠을 때, 능력치의 합의 최댓값을 구하는 문제. # 42분 소요. (한 번에 통과, PyPy3 제출 기준 시간 1위 달성했다!) 사용 알고리즘 : Backtracking, DFS 순열 구하기 무난하게 순열 구하는 dfs 재귀로 접근해 가지치기하여 가짓 수를 쳐냈다. 원래 dfs 순열로는 11개 자리에 11명을 각각 다른 자리에 배치하는 경우의 수가 39,916,800개가 나오는데, Backtracking으로 가지치기하면 경우의 수가 1824개로 확연히 준다. perm 함..
[BOJ] 1941. 소문난 칠공주(Python) / DFS, Backtracking 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 전형적인 Backtracking 문제이다. 내가 매우 취약한 알고리즘.. 이번 주는 백트래킹/DFS 문제를 파보자 사용 알고리즘 : Backtracking / DFS 재귀로 조합 구현 조합으로 접근해야한다는 것을 생각도 하지 못했다. 가짓 수가 너무 많을 것이라 생각했는데, 백트래킹으로 Y를 4번 이상 만났다면 return하여 가지치기로 어느정도 거를 수 있다. dfs 함수로 25개 칸에서 7개 칸을 선택하는 조합을 구현한다. 이 때, 7개 숫자를 리스트로 담는데,..
[BOJ] 11725. 트리의 부모 찾기(Python) / BFS, DFS 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하는 문제. # 26분 소요 사용 알고리즘 : Stack을 이용한 루트 노드 구하기 Stack을 이용한 기본적인 코드로 아래 주석으로 설명을 대신한다. Stack을 사용해 푼 파이썬 코드는 다음과 같다. (아래 코드에서 stack만 queue로 바꿔 head부터 pop하면 BFS로 푼 코드가 된다.) from sys import stdin input = stdin.readline def solve(): parentNo..
[BOJ] 1938. 통나무 옮기기(Python) / BFS 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4
[BOJ] 1525. 퍼즐(Python) / BFS 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 신박한 느낌의 BFS 문제였다. 처음 문제 봤을 때 감조차 잡히지 않았다. 이게 어떻게 BFS 인지 이해가 되지 않아, 코드 말고 아이디어 만이라도 얻어야겠다 싶어 구글링 해보니.. 3*3 맵에 있는 숫자들을 문자열로 변환해서 0이 있는 곳 기준으로 숫자 바꿀 수 있는 위치로 바꿔주고 BFS로 뻗어나가며 타겟 문자열을 찾는 방식으로 접근해야 한다는 것을 깨달았다. 이 아이디어를 바탕으로 코드를 짜봤다. # 아이디어 참고까지 30분, 문제 pass까지 1시간 30분/ 총 2시간 소요 사용 알고리즘 : BFS 최단 시간 알고리즘 3*3 맵의 ..
[BOJ] 14425. 문자열 집합(Python) / Trie 자료구조 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 매주 알고리즘 코딩 & 컴공 전공 스터디를 진행하는데, BFS, DFS, 백트래킹, Brute Force, Greedy 등은 자주 푸니까 매주 한 개씩 새로운 알고리즘을 공부해보자 하여 지난 주 이분탐색에 이어 이번 주는 트라이 자료구조에 대해 한번 공부해보기로 했다. ..

티스토리툴바