본문 바로가기

알고리즘

[Lv2]괄호 변환(python) 1. 문제 2. 구현 과정 - 정말.... 이 문제만 보면 그렇게 졸음이 와서(?) 문제 이해하는데 오래 걸렸다.. 문제 이해하는 데 대부분의 시간을 소요한 것 같다. - 구현 방법은 이미 문제에서 다 정의해줬고, 특별한 알고리즘을 사용하는게 아니라 재귀 함수를 만드는 거라 특정 알고리즘에 대해 고민할 필요는 없었다. 문제를 제대로 이해하는 게 핵심인 것 같다. - 구현의 흐름은 문제에서 정의했지만 중요한 건 "왜?" 저렇게 구현해야 하는지 인데, 큰 흐름은 다음과 같다. 1) 문자열을 균형잡힌 문자열( U ) 와 나머지 문자열 ( V ) 로 나눔 2) U가 올바른 문자열이 아니라면, 'U'의 시작 문자는 ')', 마지막 문자는 '('일 것이다! 균형 잡힌 문자열이면서 올바른 문자열이 아니다 = '('와.. 더보기
[이것이코딩테스트] 게임 개발(python) 1. 문제 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭 터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨 어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으.. 더보기
[Lv2] 행렬 테두리 회전하기(python) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 2. 접근 방법 - 파이썬으로 푸는 방법이 생각이 안나서 다른 풀이를 보고 참고했음.... 얼른 파이썬 익숙해지자 흑흑 - 난 전체 배열을 복사하려 했는데, 한 개의 값만 저장해놓고 값을 뒤에서( 현재 값 기준 반시계 방향의 값)을 땡겨서 가져온 후 맨 마지막에 저장했던 값을 넣는 방식으로 푸는 방식도 있었다. 다음부턴 다른 풀이 참.. 더보기
[1654] 랜선 자르기(python) 1. 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 2. 접근 방법 * 문제 이해 - 길이가 다른 k개의 랜선을 잘라서, N개 이상의 같은 길이 랜선들로 만들 때 (자르고 남는 대상은 버림) 만들 수 있는 최대 길이 * 접근 순서 1) 최대 길이 찾기(최적의 길이 찾기) : 최적 해를 구하는 것이므로 탐색(?)의 느낌이 남... 탐색에서 가장 대표적인 예시는 이분 탐색! 2) 탐색 시작 방향 구하기 : 가장 .. 더보기
[1874]스택수열(C++) 1. 문제 www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 2. 접근 방법 1) 스택에는 값을 "오름차순"으로 넣을 수 있다 => 내가 이번에 찾을 순열 값과 스택의 top을 비교해보면 스택에 내가 찾은 값이 있는지 알 수 있다. 한번이라도 넣었는지를 알 수 있다. - s.top() < v[idx] : 아직 스택에 v[idx]가 들어온 적이 없거나 혹은 전에 한번 넣었는데 po.. 더보기
[9012]괄호 1. 문제 www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 2. 접근 방법 1)스택을 이용해서 '('이면 스택에 넣고 ')'이면 스택에서 뺀다. 만약 '('이 나와서 빼려했는데 이미 스택이 비어있거나, 모든 괄호를 다 봤는데 아직 스택이 비어있지 않으면(닫히지 않은 괄호들이 있음) 올바르지 않은 문자열이다. 3. 실수했던 부분 & 처음 알았던 부분 1)stack에서 pop할때만 생각하지 말고, for문을 나왔을 때 스택에 값이 .. 더보기
[2805]나무자르기(C++) 1. 문제 www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 www.acmicpc.net 2. 접근 방법 1) 톱의 높이로 가능한 범위는 '~ 나무의 가장 높은 높이' 이다. 2) 톱의 높이를 정했을 때, 높이를 구하기 위해서는 log(N)만큼이 필요하다.(모든 나무들들을 다 베어서 합을 구해야 하므로), 따라서 모든 나무들의 높이에 맞게 나무를 잘라본다면 log(N^2)만큼 걸리므로 시간초과가 걸린다. 3) 이처럼 나무의 개수도 많고, 값도 크면 .. 더보기
[11048] 이동하기(C++/DP) 1. 문제 www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 2. 접근 방법 1) 이동방향이 (r+1, c), (r, c+1), (r+1, c+1) 이므로 사이클은 생기지 않는다. (1,1)->(N,M)까지 갈 수 있는 경우의 수를 구하려고 했다. 2) candy[i][j]가 (i,j)번째 도착했을 때 얻을 수 있는 최대 사탕 개수라고 할 때, candy[i][j]는 미로의 (i,j)번째 방에 놓인 사탕의 수 + (i,j)에 오기 직전까지 가장 .. 더보기

티스토리툴바