코딩 검색 결과
271 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 2206번: 벽 부수고 이동하기 (Python, C++)

접근 재채점 후 시간초과 되어 실패 뜬 문제를 C++로 다시 풀면서 Python 코드도 다시 확인하였다. 지금 확인해보니 왜 그때는 그렇게 풀었는지 모르겠는데 deque 대신에 그냥 리스트를 쓰고 popleft 대신에 pop(0)을 썼었다. 이 부분에서 시간이 초과된 것 같았다. 이 부분만 고쳐주니 시간 안에 들어왔고, 또 풀이 방법이 틀린 방법은 아니어서 그대로 두기로 했다. 최단 경로를 따라가는 BFS 알고리즘의 특성을 이용한 미로찾기와 비슷하지만, 벽 부수기라는 새로운 요소가 추가된 문제였다. 미로찾기 문제와 비슷하게 visited를 만들되, 각 칸이 요소를 2개씩 가진 3차원 배열을 만들어주었다. visited[x][y][w] 에서 w가 0이라면 벽을 한번 뚫은 상태이고, 1이라면 아직 벽을 한번..

2022. 5. 17. 17:44
코딩/백준 (C++)

백준 1701번: Cubeditor (C++)

접근 https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net kmp 알고리즘에 대해서 다시 한 번 공부하여 풀었다. kmp 알고리즘에 대해서는 아래 링크의 글이 가장 자세히 설명된 것 같아 참고차 링크 걸어두었다. https://bowbowbow.tistory.com/6 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축..

2022. 5. 17. 00:41
코딩/백준 (C++)

백준 12781번: PIZZA ALVOLOC (C++)

접근 https://www.acmicpc.net/problem/12781 12781번: PIZZA ALVOLOC 입력의 첫 줄에는 도윤이와 친구들이 선택한 점의 좌표 x, y(-10,000 ≤ x, y ≤ 10,000)가 순서대로 4개 주어진다. x, y값은 항상 정수이다. www.acmicpc.net 기하 관련 알고리즘 문제를 풀 때 자주 쓰이는 CCW 알고리즘을 이용한 문제이다. 벡터의 외적을 이용한 문제로, 두개의 벡터를 외적하였을 때 그 방향에 따라 외적 값이 양수인지 음수인지를 확인하여 두 벡터의 관계를 알 수 있다. 1 -> 2 로 가는 벡터와 1 -> 3 으로 가는 벡터를 외적했을 때 1 -> 3 으로 가는 벡터가 1 -> 2 벡터보다 반시계 방향에 있다면 두 벡터의 외적 값은 양수가 나오게..

2022. 5. 16. 16:16
코딩/백준 (C++)

백준 16933번: 벽 부수고 이동하기 3 (C++)

접근 https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net bfs 알고리즘을 이용하는 문제였다. 문제를 해결하기 위해 큐에 4가지 정보를 저장하였다. {r, c, night: 밤이면 1, cnt: 부순 벽의 갯수} 총 4개의 요소를 가진 구조체를 작성해주고, 이를 저장할 수 있는 큐에 가장 처음 위치인 {0, 0, 0, 0} 을 추가해주었다. 중복 탐색을 막기 위한 배열인 visited 배열은 visited[N][..

2022. 5. 15. 22:59
코딩/백준 (C++)

백준 10282번: 해킹 (C++)

접근 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 전형적인 다익스트라 알고리즘 문제였다. 이번 문제에서는 우선순위 큐를 쓰지 않고 그냥 bfs 방식으로 풀었다. 감염된 지점부터 의존성이 있는 주변의 지점들을 방문하면서 해당하는 감염 시간을 저장해주고, 큐에 추가해준다. 그리고 다음 위치에서도 같은 작업을 해주되, 방문한 곳을 또 방문하게 된다면 (현재 위치 감염까지 걸린 시간 + 다음 위치 감염에 걸리는 시간) 과 (기존에 저장된 다음 위치 감..

2022. 5. 15. 17:36
코딩/백준 (C++)

백준 7682번: 틱택토 (C++)

접근 https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 탐색의 복잡함도 크지 않았고, 틱택토 게임판이 유효한 경우도 비교적 명확하여 쉽게 구현이 가능했다. X가 이기는 경우: X가 먼저 시작하고 마지막으로 놓고 이기기 때문에 X의 갯수가 1개 더 많아야 하고, O가 연속 3개가 있으면 안된다. O가 이기는 경우: O가 늦게 시작하고 마지막으로 놓고 이기기 때문에 X와 O의 갯수가 동일해야 하고, X가 연속 3개 있으면 안된다. 비기는 경우: X..

2022. 5. 15. 16:37
반응형