본문 바로가기

코딩테스트90

[Swift][BFS] 백준 9376번 (탈옥) 요구능력 : 0-1 BFS알고리즘 코드설명 : 이 문제는 다익스트라로도 풀린다고 하고 0-1 BFS알고리즘 으로도 문제가 풀린다. 나는 0-1 BFS알고리즘으로 공부하고 여러군데를 참고해서 문제를 풀어봤다. 나는 처음에 죄수 2명으로 BFS를 해서 문을 최소로 구하고 탈출시켜봤는데, 예제 입력 5 9에서는 성공했지만 예제 입력 5 11에서는 성공못했다. 답은 0 이지만 내 출력은 1이 나와서인데, 내 출력이 1이 나온이유는 위에 있는 문을 부수면 가장자리(x == 0 or y == 0 or x == h or y == h)로 올경우 종료조건을 줬기 때문이다. 문을 부수더라도 가장최소한으로 움직이는 방법이 되버린것이다. 예제 입력 5 11에서 성공하려면 무조건 가장자리에 간다고해서 종료조건이라는걸 만들면 안.. 2022. 2. 28.
[Swift][백트래킹][LV_3] 양과 늑대 요구능력 : 2진트리, 백트래킹 코드설명 : 처음에 배열로 edges를 연결리스트식으로 만들어서 방문했던곳을 다시 들리는(위로다시올라오는) 대참사가 발생했다. dictionary로 아래와 같이 넣으면 한방향(본인 위치의 아래방향)으로 방문하기 편하므로 dictionary를 사용했다. 백트래킹이라고 생각한이유는 모든경우를 다 세어봐야 하기 때문이다. dfs(현재노드, 다음에 방문할 수 있는 노드, 양의 카운트, 늑대의 카운트)로 구성했다. 이렇게 구성한 이유는 양과 늑대의 카운트같은 경우 dfs()함수가 리턴되면 따로 -처리를 해주지 않아도 되기 때문이고(전역으로 선언 시 따로 -처리를 해줘야함), 현재노드 같은 경우에는 시작노드로 0을 전달해줘야 하는것도있고 굳이 0을 전달 안해주고 0으로 시작하더라도 .. 2022. 2. 26.
[Swift][소수][LV_2] K진수에서 소수개수 구하기 요구능력 : 소수판별 코드설명 : 처음에 에라토스테네스의 체를 100만으로 설정하고 풀었는데, 두 개의 테스트케이스에서 coreDumped가 나왔다. 인덱스 문제인것같아서 n = 1000000으로 설정하고 k = 6으로 설정해봤는데, 에라토스테네스의 체에 들어간 수가 100만 보다 큰 수가 나와버려서 coreDumped된것이었다. 그래서 4천만으로 설정하고 해봤는데 당연히 시간초과 ^^ 에라토스테네스가 더 빠른건줄알고 100만으로 두고 그보다 큰수가 나오면 아래에 isPrime함수를 사용했는데, 이렇게 사용한 시간보다 isPrime만 사용한 시간이 더 짧았다. 사실 이 문제에서 소수를 판별해봤자 몇개나 판별하겠나.. 이 문제를 통해서 에라토스테네스의 체를 소수구한다고 아무때나 사용하는게 아니라는것을 알았.. 2022. 2. 25.
[Swift][프로그래머스][LV_2] 위장 요구능력 : Dictionary 코드설명 : 옷 입는 경우의수다. 상의 반팔티, 후드티, 맨투맨 하의 청바지, 슬렉스, 조거팬츠 위와 같이 있으면 옷을 입는 총 경우의 수는 9가지이다. 하지만 이 문제에서는 하나만 입는 경우의 수도 셌으므로 상의 반팔티, 후드티, 맨투맨, 안입음 하의 청바지, 슬렉스, 조거팬츠, 안입음 안입음까지 포함시켜줘야하고, 둘다 안입는 경우는 포함안시키기에 -1을 해줘야한다. 나는 dictionary를 활용해서 dictionary가 비어있지 않으면 1을 더해줬고 비어있으면 2로 초기화했다. 2로 초기화 한 이유는 dict[바지] 이면 현재 for문을 돌고있는 clothes의 원소중 바지하나가 도는것이기 때문에 현재바지 1개 + 안입음 1개 해서 2로 초기화했다. 그리고 결과값을 .. 2022. 2. 22.

티스토리툴바