IT Crowd

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

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

www.acmicpc.net/problem/2527 2527번: 직사각형 4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직 www.acmicpc.net www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1829&sca=9010&stx=%EC%A7%81%EC%82%AC%EA%B0%81%ED%98%95 JUNGOL www.jungol.co.kr 문제 풀이 이 문제는 가능한 경우의 수를 줄여나가면서 원하는 답을 찾아나가는 방법으로 보다 쉽게 해결할 수 있음 입력에서 사각형1(x1,y1,p1,q1)을 기준으로 하고 사각형2(x..

재귀 함수 자기 자신을 호출하는 함수 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법 python에서의 기본 재귀 구조는 아래와 같다. 실행결과는 어떻게 될까? 자기자신을 계속 호출하므로, 무한반복에 빠지며 지정된 재귀 깊이를 초과하여 에러가 발생한다. 그렇다면, 무한 루프에 빠지지 않게 하려면 어떻게 해야하는가? 당연하지만 그냥 나 자신을 계속 호출한다면 무한반복이 일어날 것이다. 이 무한한 반복을 우리가 원하는 만큼만 반복하고 중단시키는 것이 우리의 목표다. 우리가 기본적으로 아는 반복문에서와 마찬가지로 반복을 중단시킬 무언가가 필요하다. 즉, 반복을 중단시킬 조건과 그 조건을 체크하기 위한 값을 저장할 변수. 과정을 정리하면 아래와 같다. 매개변수를 하나 받음..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제풀이 공기와 2변 이상 접촉한 치즈가 사라지는데 치즈가 모두 녹는데 걸리는 시간 구하는 문제 탐색 (bfs) 문제 공기 접촉면이 2인 구역을 찾아야함 : find 함수로 구현 찾은 치즈를 녹이고 녹인 치즈 갯수 알아냄 : melt 함수로 구현 find함수와 melt 함수를 반복해서 실행하고 녹인 치즈가 0개이면 종료하고 그 때 시간을 알아냄 find 함수 0,0 좌표에서 부터 bfs ..

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

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 삼성SW 역량테스트 기출문제 문제풀이 시뮬레이션 + 완전 탐색(dfs) 물고기이동 번호가 작은 물고기부터 이동 (1~) 이동가능한 칸 빈칸 다른 물고기가 있는 칸 이동할 수 없는 칸 상어가 있는 칸 공간의 경계를 넘는 칸 (맵을 넘어선 칸) 이동할 수 없으면 45도 반시계 회전하고 이동(8방향 모두 확인) 회전을 해도 이동할 칸이 없으면 이동하지 않음 이동시 다른 물고기가 있으면..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제풀이 입력으로 받은 인접 정보를 이용해서 인접행렬을 구성함 1~N까지의 도시번호를 이용해서 부분집합(power set) 을 구하고 선택된 집합을 A, 아닌 집합을 B로 묶음 도시집합 A,B의 길이가 0이 아니고 집합들이 모두 연결되어 있다면(bfs탐색으로 알아냄) 각 집합의 인구 총합을 구하고, 그의 차를 계산하여 그 중 최소 값을 찾음 각 집합 도시 연결 확인하기 각 도시 집합에 대해서 bfs 탐색을 수행하여 연..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 문제풀이 BFS 탐색 문제 날짜에 따라서 잠긴부분과 아닌 부분을 0과 1로 나타냄 그 다음, 1 인 부분(잠기지 않은 부분) 을 bfs 탐색으로 찾아내어 카운팅함 각 날짜별로 계산해서 그 중 최대 영역 개수를 찾아냄 코드 (python) dir=[[-1,0],[0,1],[1,0],[0,-1]] def bfs(start): que = [] que.append(start) map_b[start[0]][s..

문제풀이 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..