본문 바로가기

분류 전체보기

 (88)
swea 2105 <디저트 카페> swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu&categoryId=AV5VwAr6APYDFAWu&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이전에 풀었던 게리맨더링 2오 비슷한 문제이다 이문제를 풀어보게 된다면 이 문제도 같이 풀어보는 것이 좋다. skygood95.tistory.com/25 백준 17779 게리맨더링 주어진 방법보다 어렵게 푼 방식이기 때문에 참고!! 만 하자! 이 문제는 DFS 즉 백트래킹으로 가능한 꼭지점 4개를 구하고 최소의 차이가 나는 값을 출..
백준 17281 <야구공> 이문제는 1번 선수를 4번 타자로 배정하고 나머지 인원으로 어떻게 순서를 배정하면 되는지 순열 문제이다. 풀이 단계 0번 선수를 4번 타자에 넣고 나머지 인원을 순열로 구성한다. 순서가 구성이 완료되었다면 이닝수만큼 진행한다. 각각의 타자가 수행한만큼 전체 타석의 인원을 이동을 해주고 out이 3이 되면 다음 이닝으로 진행한다 choice라는 배열에 타자의 순서를 넣도록 한다. 순열을 구성하는 함수이다. i가 3일 경우에 이미 1번 타자가 4번째로 와있으므로 다음 타자로 넘어간다. 각각의 이닝마다 타석에 위치한 선수들은 다 나가기 때문에 이닝마다 타석을 초기화시켜준다! 이 부분에서 약간의 실수가 있었다.ㅠㅠ out이 3이 될 때까지 각 이닝을 진행한다. 타석이 이렇게 생겼기 때문에 2번 타자부터 나가야지..
백준 17472 <다리 만들기 2 > 섬을 연결하는 최소 거리를 찾는 게 가장 어려웠던 문제... 알고리즘 순서를 말하자면 BFS를 이용해서 각지점마다 연결돼있는 섬을 만들어주고 섬의 개수 파악 각 지점에서 다른 섬 까지 이동할 수 있는 2를 넘는 최소거리 구해주기 크루스칼 또는 프림 알고리즘을 이용하여 총길이 구하기 (미니엄 스패닝 트리 MST)! 이렇게 총 3단계로 구성이 된다. 여러 알고리즘을 혼합했기 때문에 생각하기 좀 까다로웠던 시뮬레이션 문제! 1번을 구하는데 N*M 의 시간 총 100 2번을 구하는데 N*M*많이 해도 N*M을 한 번 더 곱한 수 3번을 하는데 섬의 개수가 최대 6이기 때문에 21... 절대 시간 초과는 날 수 없는 문제... 1번 구성 맵을 1에서 바꿔줬기 때문에 visit 배열을 따로 선언할 필요가 없다. 2..
정올 1681 <해밀턴 순환회로> www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030 JUNGOL www.jungol.co.kr 정 올의 해밀턴 순환 회로이다. 이문제는 기본적으로 백트래킹 문제이기 때문에 최대 12개의 배달 지를 순열로 놓으면서 거리를 계산하는 문제이다. 그러나 나는 새롭게 접근하기 위해 다익스트라 알고리즘을 응용하면서 비트 연산자를 더해 BFS로 문제를 접근해보았다. dis 클래스는 next는 다음 좌표이고 d는 다음 좌표까지의 총 이동거리를 나타내고 f는 비트 연산자로 visit을 나타낸다고 보면 된다. 이렇게 총 3가지로 구성된다고 보면 된다. 모든 곳을 다 탐색하고 다시 1로 돌아온 경우이고 최소의 거리를 출력하기 때문에 답을 입력하고 return을..
백준 2933 <미네랄> 조건이 많아서 처리해야 될 부분이 많은 시뮬레이션 문제였다. 문제의 단계는 왼,오 순서대로 그 위치에 가장 가까운 미네랄을 사라지게 하는 것. 제거한 위치를 중심으로 4 방형을 검사해 미네랄 이 있으면 그 부분이 떨어져 있는 것인지 확인! 떨어져 있다면 얼마나 내려갈 수 있는지 체크! 이 순서로 진행되는 것이다. 이 부분에서 내가 헷갈렸던 부분이 2번에서 왜 4방향으로 해야 하는가 였다. 위 , 오른쪽, 왼쪽 이렇게 해주면 된다고 생각했는데 예외인 부분이 있었다. 그림처럼 화살표 부분을 부수게 되면 아래의 미네랄 뭉치가 동 떨어져 자유 낙하하게 되는 것이다. 이러한 실수를 고쳐야 문제를 빨리 풀 수 있을 텐데 ㅠㅠ 문제에 수행되는 총 시간 복잡도는 부수는 횟수를 수행하는 게 최대 100*총 BFS를 하기..
백준 17471 <게리맨더링> 2가지 선거구로 나누고 선거구가 연결되어있는지 확인하는 문제! 즉 부분집합을 구하고 각각의 선거구에서 BFS를 실행해서 연결되어 있는지 확인하는 것!! 반대로 생각을 하면 복잡하기도하고... 풀리지 않는 문제 ㅜㅜ 즉 문제를 많이 풀어봐야 한다. 선거구를 두 개로 나눈 것이다. 이 cal 부분은 선거구가 두 개로 나뉘어서 연결되어 있는지 확인하는 코드이다. 두 개가 연결되었다면 count는 2가 될 것이고 값을 비교해서 넣어주게 된다. 인접 리스트를 이용해서 다음 노드가 같은 팀인지 확인하게 되고 같은 팀이라면 큐에 넣고 BFS를 실해해 주는 것이다. 이렇게 총 3단계를 이용해서 문제를 해결할 수 있다. 이 방법이 생각이 어떻게 나냐? 하는 사람들은 문제를 많이 풀어보길 권한다. 전체 코드 더보기 imp..
백준 17779 <게리멘더링2> 게리맨더링 주어진 방법보다 어렵게 푼 방식이기 때문에 참고!! 만 하자! 이 문제는 DFS 즉 백트래킹으로 가능한 꼭지점 4개를 구하고 최소의 차이가 나는 값을 출력하는 것이다. 문제에서 처럼 푼다면 4중 포문으로 꼭지점의 좌표 d1, d2, 이렇게 구해서 계산을 하면 되겠지만 문제를 이해하고 계산하는 방법이 없다면 푸는 방법이다. DFS를 3번 돌려서 가능하다면 최솟값을 비교해주도록 했다. 이 그림으로 설명하자면 1의 꼭지점을 잡고 오른쪽 아래로 이동 꼭지점이 가능하다면 왼쪽 아래 대각선으로 이동이 가능하다면 1에서 2까지 온 거리만큼 3위 치에서 좌상 대각선으로 이동하는 문제이다. 이렇게 총 3번의 DFS로 문제를 해결할 수 있다. 1번에서 빨간방향으로 한번 이동해서 계산해주고 다시 돌아와 파란색 동..
백준 1753 <최단 경로> 더보기 이 문제를 풀면서 두 가지 방법으로 문제를 풀어 볼 것이다. 우선순위 큐를 사용하지 않은 최단 경로 우선순위 큐를 사용한 최단 경로 이렇게 두가지 방법으로 풀어 본 이유는 우선순위 큐를 사용하는 것이 과연 빠른가? 하는 마음에서 사용하기로 했다. 차이가 있는 부분은 가장 작은 최소를 어떻게 찾을 수 있을까 부분이다. 전체 정점을 돌면서 방문하지 않았고 최소 거리인 점을 찾는 부분이다. 우선 순위 큐를 사용하게 되면 방문했던 곳이면 넘어가 주면 되고 그렇지 않은 경우에 가장 작은 경로를 반환해 주기 때문에 쉽게 구현을 할 수 있다. 즉 우선 순위큐를 사용하지 않으면 v^2를 요구하게 된다면 사용하게 된다면 vlogv+ elogv 시간이 걸려 시간을 단축할 수 있다. 이런 식으로 흐름이 진행되게 된다..
백준 18513 <샘터> 치킨 집의 위치에서부터 BFS를 하는 문제! 생각보다 어렵지는 않았지만.. 그놈의 실수.. 실수.. ㅠ 접근 방법만 알게된다면 쉽게 풀 수 있는 문제였다. 문제를 먼저 이해하자고 하면 치킨집에서 가까운 순서대로 집을 놓고 개수를 구하는 것이다. 즉 가까운 곳부터 집을 놓는다 --> 너비 탐색 이렇게 되는 것이다. 이 문제에서 주요하게 생각해야 하는 점은 범위!! 총 거리의 합이 int형이 아니고 long 형의 범위가 된다는 것을 주의해야 한다! 이것 이외에도.. 메모리... 초과를 주의하자.. 이놈의 습관 때문에 방문처리를 해주는 visit함수를 boolean 형이 아닌 int 형으로 사용한다면... 메모리 펑... 펑... 초과를 하게 된다. 위에 num을 저렇게 크게 잡아준 이유는 음수에도 위치가 놓..
백준 2206 <벽 부수고 이동하기> 이전의 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있�� www.acmicpc.net 이 문제를 풀기 전에 추천했던 문제이다. 이 문제의 중점은 1번 뚫은 지점과 그렇지 않은 지점 방문처리를 어떻게 해주냐?이다. 이 중점의 답은 방문처리하는 vistit 2차원 배열을 안 뚫은 것을 체크하기 위한 하나, 뚫은 것을 체크하기 위한 하나 총 2개로 3차원 배열을 만드는 것이다. 이 클래스는 x,y 좌표와 시간을 담은 t , 벽을 뚫은 횟수를 담은 num으로 구..

티스토리툴바