본문 바로가기

Algorithm

 (640)
삼성SW 1859. 백만 장자 프로젝트 문제 출처 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc result 값이 억단위를 초과할 수 있으므로 long으로 생성하는 것과 앞으로 배열을 만들 때는 항상 동적 할당 사용하기. -> 런타임 오류 방지 배열 생성은 컴파일 타임에 이뤄지고 cin으로 받아오는것은 런타임에 이뤄지므로 배열이 런타임보다 전에 만들어 지게 되는데 값이 없는 변수를 참조하게 되므로 오류가 발생. 근데 지원하긴 해서 어찌저찌 돌아가는데 오류날 가능성 多 알고리즘은 간단하다 어차피 전날의 시세는 다음날에 영향을 못미치므로 마지막 날의 시세를 기준으로 첫날까지 가면서 자신보다 전날 시세가 높다면 전날은 자신으로 ..
백준 2841번 외계인의 기타연주 문제 상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다. 보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다. 멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다. 예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손..
백준 12764번 싸지방에 간 준하 (GG) 문제 현재 대한민국 해군에 소속되어있는 준하는 문제를 풀기 위해 매일같이 사이버 지식 정보방 통칭 싸지방에 다닌다. 그러나 최근 문제가 생겼다. 싸지방에 사람이 몰려 컴퓨터 수가 모자라게 된 것이다. 이런 사태를 도저히 용납할 수 없었던 준하는 곧 전역하는 선임을 설득해 민원을 넣도록 하는 데 성공했다. 마침내 부대에서는 민원을 받아들이기로 하였고, 컴퓨터를 증설하기로 했다. 또한, 컴퓨터 간의 사용률에 따라 다른 성능의 컴퓨터를 설치하고자 한다. 하지만 예산이 부족해 사람 수 만큼 컴퓨터를 살 수가 없었다. 고심에 고심을 거듭한 준하는 모든 사람이 항상 정해진 시간에 싸지방을 이용한다는 사실을 발견했다. 컴퓨터가 있는 자리에는 1번부터 순서대로 번호가 매겨져 있다. 모든 사람은 싸지방에 들어왔을 때 비..
백준 7569번 토마토 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한..
백준 1697번 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 간단한 DFS 문제라고 생각하고 풀었는데 생각보다 답이 잘 안나왔고,..
백준 2816번 디지털 티비 문제 2012년 12월 31일 새벽 4시부터 지상파 아날로그 TV방송이 종료되었다. TV를 자주보는 할머니를 위해서, 상근이네 집도 디지털 수신기를 구입했다. 원래 상근이네 집에는 KBS1과 KBS2만 나왔다. 할머니는 두 방송만 시청한다. 이제 디지털 수신기와 함께 엄청난 양의 채널을 볼 수 있게 되었다. 하지만, 할머니는 오직 KBS1과 KBS2만 보려고 한다. 따라서, 상근이는 채널 리스트를 조절해 KBS1을 첫 번째로, KBS2를 두 번째로 만들려고 한다. 티비를 켜면 디지털 수신기는 시청 가능한 채널 리스트를 보여준다. 모든 채널의 이름은 서로 다르고, 항상 KBS1과 KBS2를 포함하고 있다. 상근이는 이 리모콘을 이용해서 리스트의 순서를 바꾸는 법을 알아냈다. 리스트의 왼편에는 작은 화살표가..
2112. [모의 SW 역량테스트] 보호 필름 출처 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu 역대급 레전드 문제.... 구현도 구현인데 그보다 시간줄이기가 가장 힘들었다. DFS에서 가장 핵심은 재귀하면서 재귀로 또 나아가지 않아도 될 조건들을 찾아서 해당 조건에서 진행을 무시하도록 하는 것인데 ,,, 여러 아이디어가 있다. 검사 함수를 하드코딩으로 하는 것, 그리고 필요없는 count에 대한 무시, 검사시에 끝까지 진행하기 전에 탈출 하기. 등등 그리고 DFS에서 나는 카운트를 인자로 넘겨서 그 카운트부터 인덱스가 진행되게 했는데 같은 카운트에 대해 다른 인덱스가 존재 할 수 있고 이를 통해 더 빨리 결과값을 찾아 낼 수 ..
2382. [모의 SW 역량테스트] 미생물 격리 출처 https://swexpertacademy.com/main/solvingProblem/solvingProblem.do 무작정 BFS 하면 군집이 합쳐 졌을 때 언제가 마지막이 되는지 모르므로 queue에 push를 못함. 따라서 vector를 이용한 DFS를 구현해야 하는데 또 여기서 중요한 점은 하나의 군집씩 끝까지 이동, 끝까지 이동 , 끝까지 이동 이렇게 간다면 같은 순간에 이를테면 첫번째 개체가 갔다가 돌아오는 경우와 두번째 개체가 떠나려고 하는 경우 첫번째 개체를 끝까지 진행하고 두번째로 나아간다면 두번째 개체가 아직 자리에 남아있는 것으로 보일 수 있기 때문에 병렬적으로 처리해 줘야함. #include #include using namespace std; int N, M ,K; int t..

티스토리툴바