차가운오미자님의 유리병

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 이해 배열을 얼마나 자유자재로 다루는지를 보는 문제인 것 같다. 그리고 문제에 나와있지 않은 예외 사항을 잘 캐치하는지를 보는 것 같다. 사실 아이디어는 단순하다. 배열을 가로/세로로 한 줄 탐색하면서 만약에 높이가 달라지면 낮은 쪽에 연속으로 경사로 길이 X 만큼의 공간이 있는지를 확인하면 된다. 나는 check()라는 함수를 만들어서 위의 조건을 확인했다. 그러기 위해서 세로와 가로 줄을 ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 이해 거의 그냥 시뮬레이션 문제인데, 내가 문제를 또 잘못봐서 한참을 헤맸다. 최종 점수를 판단하는 건 모든 cmd를 수행하고 난 후이다! 난 cmd를 한 번 실행할 때마다 점수가 나는 건줄 알았다... cmd를 하나씩 수행할 때, - 좌우에 다른 극인 자석이 있으면 걔네를 돌린다. - visited 배열을 하나 두어서 이미 한번 돌렸던 애가 다시 돌아가지 않게 한다. 예를 들어 2번 자석이 ..

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2156&sca=9030 JUNGOL www.jungol.co.kr 문제 이해 제리의 체력이 치즈를 먹을 때마다 1씩 증가하고, 치즈는 1에서 N까지 하나씩만 있으므로, 1에서 N까지의 치즈를 순서대로 하나하나씩 찾아가는 경로를 찾으면 된다. 최단 시간(경로) 를 찾으라고 했으니 BFS를 사용하는 문제일 것이다. 좀 더 자세히 보자면 시작위치에서 1까지 가는 최단 경로를 BFS를 이용해서 찾고, 2에서 3까지의 최단 경로를 BFS를 이용해서 찾고 이런 식이다. 각 BFS를 호출할 때마다 큐와 visited 배열을 초기화 하는 것을 잊지 말자!! 추가적으로 주의해야할 점은, map을 문자열로 받기 때문에 정수..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 이해 사람은 최대 10명이므로, 사람을 기준으로 DFS를 구현해도 충분히 할 수 있다. 문은 2개뿐이므로 사람 별로 문을 선택하면 2^10의 경우가 나온다. 모든 경우를 살펴봐도 시간 limit안에 들어올 수 있다. 그러므로 사람을 기준으로 DFS를 하면 된다. 모든 사람이 둘 중 하나의 문을 선택한 후에, 그 정보를 기반으로 시간이 얼마나 걸렸는지를 계산한다. 그리고 각 시간마다 최대값과 비..

https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 문제 이해 주어지는 입력 중에, 각 요소가 어느 위치의 길이인지를 파악하는 것이 관건이다. 주어질 수 있는 경우는 ㄱ,┏, ┗, ┛ 네 개이다. ㄱ 모양의 경우에 한 번 씩 나오는 방향의 길이가 큰 사각형이 너비(North), 높이(West)이고, 두 번씩 나오는 방향(South, East)의 길이들 중에, 껴있는 것이 작은 사각혐의 너비, 높이이다. 다시 말해서 East방향의 길이들 중에서도 ..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 이해 모든 경우를 탐색해서, 연결되어 있는 것들의 수를 세서 저장하면 된다. (map[i][j] == 0일때 BFS 혹은 DFS를 돌리기) 모든 경우를 탐색하기 때문에 DFS를 이용해도 되고, BFS를 이용해도 된다. 문제를 잘 읽어야하는게, 집의 개수를 저장한 배열을 정렬해서 출력해야 한다. (안했다가 계속 허탕침) 작성 코드(C) 1. BFS 이용 #include #include int N..

이진 탐색은 범위를 반으로 나눠가며 찾는 것이다. 선형 탐색보다 훨씬 빠르게 타겟을 찾을 수 있다. 시간 복잡도는 NlogN이다 주의할 점은, 이진 탐색에서 m의 왼쪽에 m보다 작은 요소가, 오른쪽에 m보다 큰 요소가 있는 걸 보장하기 위해, 이진 탐색 전에 배열은 반드시 정렬되어 있어야 한다. 예를 들어서, 9개의 요소를 가진 배열 arr가 있다고 가정하자. 1 2 3 4 5 6 7 8 9 이렇게 있을 때, 3을 찾는다고 하자. 일단 전체 arr[0] ~arr[8] 중 중간 요소가 3인지 확인한다. 타겟은 3보다 5가 크므로 5보다 아래에 있다는 소리이다. 그럼 다시 arr[0] ~ arr[3] 을 찾아본다. 중간((0+3)/2)은 arr[1] == 2 이다. 타겟 보다 작으므로 오른쪽에 있다는 소리다..

https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 문제 이해 일단 기본적으로 주어지는 입력 들의 수가 굉장히 크다. 사대가 최대 100,000개이고, 동물의 수가 최대 100,000 이기 때문에, 각 사대 별 동물 탐색, 혹은 동물별 사대 탐색을 하면 100,000 * 100,000 = 10,000,000,000번의 루프이므로 절대 시간 내에 문제를 풀 수 없다. 탐색의 시간을 줄이기 위해..

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=942&sca=50&sfl=wr_hit&stx=1669&sop=and JUNGOL www.jungol.co.kr 문제 이해 계속 DFS, BFS만 생각하다가 이 문제를 봐서 처음에 DFS를 해야하나? 생각했다. 근데 소시지가 5000개이다. 절대 불가능 Greedy를 사용해야 하는 문제이다. 공장을 한 번 정비할 때 최대한의 소시지를 만들고 다시 정비하고 최대한 만들고 정비하고... 를 반복해야 한다. 한 번 정비 후마다 남아있는 소시지 중에 가장 작은 소시지부터 만들면 된다. 루프를 돈다. (남은 소시지 개수 > 0 까지) 소시지 배열을 정렬한다. (길이를 기준으로 정렬한다. ) 루프를 돈다. 여기서는 자..

https://www.acmicpc.net/problem/2479 2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net 문제 이해 해밍거리가 1이란 주어진 두 개의 코드 중에 하나의 비트만 다른 관계를 뜻한다. 코드 A 부터 B 까지 가장 짧은 경로를 찾는다. 따라서 BFS를 이용한다. 움직이는 것은 해밍 거리가 1인 관계에서만 가능하다. 해밍 거리를 판단하는 것은 별도의 함수 (isHamming)로 구현해주었다. 단 BFS 를 이용할 때, 그 경로를 저장하는 것이 어렵다. 이를 위해 별도의 배열을 선언하여, ..