Algorithm/BOJ (95) 썸네일형 리스트형 [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차원으로 해버리면, 이미 벽을 부순 노드가 빈 공간을 방문하다가 이동할 수 없는 상황일 때, 다녀면 위치가 다 방문 체크가 .. [BOJ] 2146. 다리만들기 Python https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 해결방법 BFS 문제이다.. 쉬울줄 알았는데 어려웠다. 2개의 큐를 사용해야 하고, 시간 복잡도를 고려해야 한다. 시간나면 다시 한번 풀어봐야겠다. 1. 각 섬을 구분짓기 위해 bfs1을 돌아서 각 섬들이 고유의 번호를 갖기 위해 값을 하나씩 증가시켜 maps을 저장했다. 2. 2중 for문으로 특정 섬부터 시작해서 두 번째 bfs2를 돈다. 3. 유효성 검사를 하고 자신의 섬이 아닌 다른 섬을 .. [BOJ] 13549. 숨바꼭질 3 Python https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 해결방법 DFS인줄 알았으나, 재귀에러에 두들겨 맞고 BFS로 풀었다. 왜 bfs인지는 문제를 풀면서 느낌;; 1. 현재 인덱스 위치랑 time을 q에 append 한다. 2. x * 2, x - 1, x + 1의 경우에는 가중치가 0 그리고 1로 다르므로 bfs를 이용하여 3가지 모두 탐색을 한다. 3. 유효성 검사와 방문체크도 하고, 새로운 인덱스 위치와.. [BOJ] 6593. 상범 빌딩 Python https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 1. 해결방법 상 하 좌 우 위 아래 6 방향으로 탐색해야하므로 당연히 BFS 문제이며, q를 이용해서 z, y, x 인덱스 뿐만 아니라 time 이라는 변수까지 추가해서 q에 담아내는 노하우가 있으면 좋을지도..? 문제 글을 잘 읽자.. 입력 관련 글을 안봐서 입력에 시간 다 보냈다;;; 1. L, R, C가 0을 입력받을 때, 종료되야 하므로 while문을 이용해서 무한 반복을 하고, 2차원 배열을.. 이전 1 2 3 4 5 ··· 12 다음 목록 더보기