백준56 [백준 1158] 알고리즘 92일차 : 요세푸스 문제 www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net C++ 큐 이번주 후반부는 쉬어갑시다 접근 방법 K번째 사람을 큐에 순서대로 넣고 마지막에 큐에서 빼면서 출력했다. 아직 큐에 넣지 않은 사람(방문하지 않은 인덱스)이 나올때마다 cnt++을 해주고 cnt가 k가 되면 그 사람을 큐에 넣고 cnt를 0으로 초기화했다 인덱스가 n의 범위를 넘어가면 안되므로 i = (i+1)%n으로 해줬다. 오답노트 i를 증가시키는 코드를 if문 안에 넣어놔서 무한루프가 돌았었다. 소스코드 #include #include using namespace std; bool vi.. 2021. 2. 25. [백준 13305] 알고리즘 91일차 : 주유소 www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net C++ 그리디 알고리즘 좀 쉬어가려고 그리디 풀었는데 그리디 무려 5개월만에 풀어서 좀 낯설었다. 접근방법 지금까지의 최저가를 갖고 가다가 그 최저가 보다 더 적은 값을 만나면 거기까지는 지금까지의 최저가로 주유해서 간 다음 그 이후부턴 그 주유소에서 주유하는 식 오답노트 거리랑 금액이 모두 최대가 int최대범위여서 total금액과 중간중간 거리를 더하는 변수는 long long 타입을 써줘야한다.. 2021. 2. 24. [백준 1753] 알고리즘 90일차 : 최단경로 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net C++ 다익스트라 문제가 간결한 것에 비해 걸린 시간이 매우 김. 역시 골드는 만만하게 봐선 안돼 우선순위큐를 사용해서 다익스트라로 풀이하는 문제입니다. 접근방법 인접행렬을 사용했고, 우선순위큐를 사용했습니다. 방문 여부는 큐에서 뽑은 거리가 이미 그 노드까지의 최단경로와 같다면 그 노드에 대해서는 처리하지 않고 넘어가는 식 오답노트 우선순위 큐 안써서 시간초과 났었음 근데 우선순위 .. 2021. 2. 23. [백준 1707] 알고리즘 89일차 : 이분 그래프 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net C++ BFS 그래프 문제 접근방법 일단 정점을 담는 두 집합이 있다고 가정하고, 처음엔 그래프를 탐색하면서 인접한 노드는 다른 집합에 넣고 마지막에 두 집합의 교집합이 공집합이 아닌지 확인해서 결과를 출력했다. 근데 이렇게 하면 우선 이 문제에서 그래프는 모든 경우 연결그래프라고 가정하고 있지 않고, 무엇보다 시간초과가 났다. 그래서 갈아엎었다 ^_^ 방문여부를 저장하는 배열에 0,-1,1을 저장.. 2021. 2. 22. [백준 7562] 알고리즘 88일차 : 나이트의 이동 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net C++ BFS 나이트가 있는 칸, 도달하려는 칸 인덱스가 주어지고 나이트가 도달하려는 칸까지 가는 최단거리를 구하는 문제 나이트가 이동할 수 있는 칸은 위의 사진과 같다. 접근방법 나이트가 현 위치에서 갈 수 있는 칸(8개)을 인접한 노드라고 생각하고 그래프 BFS 최단거리 문제로 풀었다. 숨바꼭질 문제랑 유사하다. distances배열과 visit배열을 사용한다. 오답노트 제출전에 디버깅에서 런타임에러가 걸렸었.. 2021. 2. 19. [백준 1697] 알고리즘 87일차 : 숨바꼭질 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net C++ BFS 수빈이가 동생이 있는 좌표까지 가는데 걸리는 최단시간을 구하는 문제이다. 수빈이는 1초에 앞,뒤,2배만큼 이동할 수 있고 최소한 몇초만에 찾는지 구하는 문제 접근방법 인접한 노드를 현위치에서 -1, +1, *2 위치로 생각하고 distances배열에 최단거리를 저장하면서 BFS 최단거리 문제로 풀었다. 오답노트 큐에 push할때 배열의 최대 범위를 넘어나서 런타임에러가 .. 2021. 2. 18. [백준 7569] 알고리즘 86일차 : 토마토(3차원) www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net C++ BFS 토마토 농장주가 된 기분이네요. 어제에 이어 오늘도 토마토를 익혔답니다. 다음문제가 토마토인것을 보자마자 소스라치게 놀랐어요. 하지만 어제 풀었던 거니까..하면서 풀었는데 다행히 3차원으로만 늘리는 설정만 하면 되는 코드였어요. 접근방법 2차원 토마토 문제에서 3차원배열로 늘려주고, 인접 토마토 확인할 때에도 dh를 추가해서 위 아래 토마토를 확인할 수 있도록 고쳐준다. 소.. 2021. 2. 17. [백준 7576] 알고리즘 85일차 : 토마토 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net C++ BFS 토마토 농장에 갇혔다가 겨우 탈출함. 진짜. ...세상 기쁘다 문제를 설명할 기력은 없네요. 대충 토마토 빨리 익히는 게임이라고 생각하면 됩니다. 접근방법 BFS .. 과연.. 익은 토마토를 큐에 넣습니다. 다 익었는지 체크 -> 익었으면 0 출력 반복문 들어감(큐가 비어있지 않으면 계속 돌아가는 반복문) -> 큐에서 팝하고 방문했다고 체크, 인접한 토마토들 큐에 넣기 전날 큐에 .. 2021. 2. 16. [백준 2178] 알고리즘 84일차 : 미로탐색 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net C++ BFS 즐거운 미로탐색 갈수있는 길이 2차원 배열로 주어지고 0,0에서 n-1,m-1까지의 최단'거리'를 구하는 문제 경로가 아니라 인덱스를 저장할 필요는 없다 (parent배열 안갖고 있어도 된다는 소리) 접근방법 여느 BFS와 같이 큐에 인접한 노드를 저장하고 (여기서는 인접한 노드가 길이 있으며(maze배열에서 1), 아직 방문하지 않음(distances가 -1)) 동시에 인접한 노드들의 distances를 갱신하고 또 큐에서 인.. 2021. 2. 15. 이전 1 2 3 4 5 6 7 다음 728x90
