본문 바로가기

Algorithm

 (175)
[BOJ] 11660. 구간 합 구하기5 Python, Java https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 1. 해결방법 진짜 DP 너무 어렵다,,,, 이 문제를 보면 어떻게 하면 정상적인 출력이 나오게끔 코드를 구현하는 것은 정말 쉬울 것이다. 하지만 !!! 그렇게 그 쉬운, 각 배열을 탐색해서 더하는 방법이라면 시간복잡도에 걸려서 시간초과라는 안타까운 결과를 보게된다. 문제 설명을 위한 예시를 보자, 숫자들로 채워진 N x N의 표가 있고, 두 개의 좌표 ..
[SWEA] D4. Ladder1 Python, Java https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 해결방법 위 그림을 보면 위에서 아래로 연결되는 사다리 길을 찾는 문제이다. 여기서 포인트는 아래로 가다가 좌 또는 우로 갈 수 있는 경로가 생긴다면 반드시 반드시 좌 또는 우로 가야한다. 좌 또는 우가 같은 위치에서 생길 순 없다. 문제대로 위에서 아래로 사다리 길을 찾는 탐색을 시작한다면 많은 경우의 수가 생길 것이다. 이를 해결하고자, 정해진 출구 2인 아래 위치에서 위로 이동하면 한 번..
[BOJ] 16987. 계란으로 계란치기 Python https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 1. 해결방법 문제를 이해하면 백트레킹이라는 것을 알 수 있지만, 이해도 어렵고 문장도 길어서 어떤 알고리즘인지 찾아내기가 꽤 어려웠다. 문제 이해하는데만 20~30분 정도는 걸린 것 같다. 이 문제에 대한 접근은 왼쪽부터 계란을 집어서 다른 계란을 때리는 것이다. 이 때, 내구도와 무게에 따라 들고있는 계란이 깨지는지 다른 계란이 깨지는지의 경우를 고려해야한다. 조건을 생각해 보면..
[BOJ] 4358. 생태학 Python https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 1. 해결방법 파이썬 딕셔너리를 활용해서 해결하는 방법이 가장 적절하다. 1. while문으로 나무의 종을 입력받고, 그것을 딕셔너리에 저장한다. 2. 저장할 때, 입력받은 나무가 이미 딕셔너리에 있다면? => 해당 나무의 value를 + 1 한다. 3. 시간복잡도를 고려해서 while 문 안에 나무를 입력받으면서 idx 총 개수를 카운팅한다. 4. 알파벳 순으로 정렬. 5. 정렬한 딕..
[BOJ] 2075. N번째 큰 수 Python https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 1. 해결방법 음... 솔직히 heapq 알고리즘에 대해서 완벽히 이해와 시간복잡도 또는 메모리에 대해서 잘 알고 있지 않는 이상 과연 heapq 를 떠올릴 수 있을까?? 이 문제는 뇌빼기 코딩으로 2차원 배열을 저장하고 2중 for문을 한번 더 돌아서 리스트에 저장한 다음, 정렬해서 찾으려고 한다면 시간복잡도는 어떻게든 되겠지만 메모리라는 벽에 부딪혀 버린다. 가장 중요한 포인트는 heapq 라이브러리..
[BOJ] 11279. 최대 힙 Python, Java https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 해결방법 heapq 우선순위 큐 문제이다. python 의 우선순위 큐가 있는지는 공부 역량이 부족해서 잘 모르지만, heapq로도 가능하다. 1. heap이라는 리스트를 빈 값으로 생성. 2. 입력받은 정수 x가 0이 아닌 정수라면, heap에 삽입. 3. 삽입할 때, 문제의 목적이 최대 값을 뽑아야 하므로 -x를 삽입한다. 4. x가 0일 때, heap이 빈 상태라..
[BOJ] 1620. 나는야 포켓몬 마스터 이다솜 Python, Java https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 1. 해결방법 이 문제에서 포인트는 시간복잡도이다. 리스트에 대한 시간복잡도와 파이썬의 딕셔너리의 시간복잡도를 이해하는지에 대한 의도가 드러나있다. 리스트의 경우, 자주 쓰이는 append와 pop과 같은 경우에는 O(1)의 시간복잡도를 가지지만, list.index()와 리스트 탐색의 경우에는 O(N)의 시간복잡도를 가진다. 해당 문제는 isdigit() 메서드까지 ..
[BOJ] 2206. 벽 부수고 이동하기 Python https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. 해결방법 일단 체감상 어떻게 해결해야할지 감은 오지만 조건을 맞추는데 어려워서 굉장히 많은 시간을 함께 보낸 문제이다. 하지만 좋은 문제인 것 같다. 전형적인 BFS 문제이며 , 벽을 딱 한번 부술 수 있는 특징이 있는 문제이다. 방문 체크를 2차원으로 해버리면, 이미 벽을 부순 노드가 빈 공간을 방문하다가 이동할 수 없는 상황일 때, 다녀면 위치가 다 방문 체크가 ..

티스토리툴바