IT Crowd

이 문제는 N(2 ≤ N ≤ 1,000,000)이라는 것을 생각하고 풀어야 하는 문제이다. 문제를 해결하려고 가장 첫번째로 생각나는 방법은 아마도 현시점에서 매수를 하고 현재 시점에서 부터 끝까지 탐색해서 그중 최고값을 찾아 이익을 얻는 것일 것이다. 하지만 이방법으로 문제를 풀려고 한다면, 2중 for문이 필요하고 N^2의 시간복잡도를 가지게 된다. 주어진 테스트 케이스를 해결하더라도 N이 커질 경우 시간초과가 발생할 수 있다. 이때, 뒤에서 부터 순회하는 방법을 사용하면 위의 문제를 해결할 수 있다. 뒤에서 부터 순회를 하면서 현시점 (현위치)에서 부터 끝까지 중 최고치를 알아낼 수 있고, 현시점의 매매가 보다 최고 값이 높으면 매수하고 최고치에 팔면 이득을 얻어 낼 수 있다. 설명한 내용을 간단히 ..

문제풀이 2차원 배열의 특정 위치에서 부터 인접 좌표들로 이동을 하면서 최소비용을 구하는 문제 가중치가 없다면 단순 bfs로 해결할 수 있음. 문제에서는 현재좌표의 높이와 새로운 좌표의 높이 차이가 있다면 ( 새로운 좌표가 높다면) 그 높이 만큼을 가중치로 계산함 시작점 (0,0)에서 BFS 탐색을 하면서 각 인접 좌표 (상하좌우)에 대해 간선완화를 진행 한 좌표의 상하좌우에 있는 새로운 좌표 계산 각 좌표가 범위내인지 확인 새로운 좌표의 높이가 현재의 높이보다 높다면 그 차이를 가중치로 계산 높이 차이가 없거나 새좌표가 더 낮으면 가중치는 1 (기본 비용) 새로운 좌표의 현재까지의 최소비용(시작점에서 부터의 최소비용)가 현 좌표를 찍고 가는 것 보다 높으면 새로운 비용으로 갱신 새좌표의 최소비용 > 현..

www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m^2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1≤K≤20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나� www.acmicpc.net 입력 변의 방향이 동,서(1,2)일 경우 가로변, 변의 방향이 남,북(3,4)일 경우 세로변임을 알 수 있음. 6각형이고 입력이 순서대로 들어오므로 변의 방향과 길이를 저장하기 위한 2차원 배열을 생성하여 저장함. 문제 풀이 ㄱ자 모양이라는 것에서 아이디어를 얻음 그림과 같이 큰 사각형에서 작은 사각형을 빼면 ㄱ자 도형의 면적을 구할 수 있음 큰 사각형의 면적 주어진 변의 길이중 가장 긴 가로 변, 세로변의 길..

알고리즘 강의를 하다보면 생각보다 많은 학생들이 입력에서 막혀서 시간을 허비하는 것을 봤다. 이번 기회에 정리해 놓으면 한 분이라도 도움이 될것 같아서 정리해보도록 하겠다!! ^-^ 코딩테스트에서는 대게 input파일이 주어진다. 문제를 풀때 입력을 줘야하는데 가장 간단한 방법은 input 텍스트를 복사해서 프로그램을 실행하고 콘솔창에 붙여넣기 해주는 것이다. 하지만 이 방법은 디버깅시에 귀찮기도 하고, 가끔 발생하는 pycharm 콘솔창 오류를 만나면 난감하다. 이 때, input 파일을 텍스트 파일로 저장하고 바로 읽어서 실행할 수 있도록 설정하면 편하다. 파일로 입력받기 sys 모듈 임포트 표준 입력을 파일/읽기로 설정 import sys #표준입력을 파일로 설정 sys.stdin = open("i..

https://swexpertacademy.com/ SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 자세한 문제의 내용은 위 사이트의 수록된 문제로 5521. 상원이의 생일파티 를 검색하여 문제를 확인하면 된다. 문제풀이 상원이가 생일파티에 자신과 친한 친구와 친한친구의 친한친구에게 초대장을 주는 상황 그래프로 표현할 수 있음 나눠 줘야하는 초대장의 수를 구하는 문제이고 1번이 상원이임. 그래프를 탐색하여 해결할 수 있고, 탐색 시작이 1번임을 알 수 있음. 친한친구의 친한친구까지 탐색 너비우선탐색 (BFS)을 이용하여 해결할 수 있고, 탐색의 너비를 2로 제한함. que에 담긴 요소의 갯수를 저장하고 이를 이..

문제풀이 dfs를 이용하여 최적화를 하는 문제이다. 가장 높은 봉우리에서 부터 탐색을 시작함. 봉우리의 사방을 탐색 다음 길이 낮으면 그대로 탐색 진행(dfs호출) 다음 길의 높이가 같거나 높고 공사를 아직 안했으면 공사를 진행함 공사는 최대 깊이 K만큼 할 수 있음 (1~K) 모든 경우( 모든 공사깊이 ) 를 탐색 공사 후에 다음 길의 높이가 낮아졌다면 dfs를 호출해서 탐색 계속 (dfs호출) 등산로길이의 최대값을 계속 업데이트해서 최대값을 결과로 얻음 소스코드(python) dr = [-1,0,1,0] dc = [0,1,0,-1] def dfs(r,c,path,isConst): global ans if ans < path: #최장 등산로 갱신하기 ans = path #사방 탐색 : 등산로 탐색 fo..