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

백준 2661번: 좋은수열 (Python)

접근 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 백트래킹 문제였습니다. 문제에서 주어지는 N 길이의 좋은 수열 중 가장 작은 좋은 수열을 구하는 문제입니다. 이 수열은 숫자 1, 2, 3 으로만 이루어져 있으므로 첫번째 항부터 한개씩 채워가며 길이가 N 이 될 때까지 채워갑니다. 이때 숫자를 하나 채울때마다 지금까지의 수열이 좋은 수열인지 아닌지를 계속 체크해나가면서 진행하면 되고, 문제에서 가장 작은 좋은 수열을 구하라고 하였기 때문에 각 칸에 작은..

2022. 9. 19. 22:09
코딩/백준 (Python)

백준 14889번: 스타트와 링크 (Python)

접근 각 팀에 N/2명씩 나누었을 때 사람들 끼리 가지는 시너지를 계산하여 팀 사이의 능력치 차이가 가장 적도록 하는 문제이다. 예를 들어 1번 선수와 4번 선수가 같은 팀일 경우 table[1][4] 와 table[4][1]을 팀 능력치에 더해주면 된다. 처음에는 각 팀에 선수 한명씩을 배정해주고, 새로운 팀원이 들어올 때마다 기존 팀을 순환하면서 table[i][j]와 table[j][i]를 더해주는 방식으로 코드를 짰는데 시간도 오래걸릴 뿐더러 중복되는 경우를 구분하기 어려웠다. 따라서 방법을 바꾸어 첫번째 선수(아래 코드에서는 0번 선수)가 포함되는 N/2명의 선수 명단을 모두 구하고(0번 선수가 두번째 팀에 가서 순환해도 모두 기존 구한 팀 명단과 중복된다.), 각 경우에 팀이 가지는 능력치를 ..

2022. 9. 19. 21:40
코딩/백준 (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
코딩/백준 (Python)

백준 9252번: LCS 2 (Python, C++)

접근 이전에 풀었던 LCS 문제는 공통 수열의 길이만 필요했다면, 이번 문제에서는 그 수열을 저장해야 한다. 최장 공통 수열(LCS) 기본 문제: 2021.03.30 - [코딩/백준 (Python)] - 백준 9251번: LCS (Python) 백준 9251번: LCS (Python) 접근 몇 번 코드를 작성해보다가 전혀 답에 근접해지지 않아 다른 분들의 풀이를 참고하여 풀게 되었다. 다음과 같은 표를 작성해보자. 문자 0 C A P C A K 0 0 0 0 0 0 0 0 A 0 C 0 A 0 Y 0 K 0 P 0 표시된 칸 ca.ramel.be 이전에 풀었던 코드와 유사하게 작성하되 dp에 그 길이만을 저장하는 것이 아니라 해당 시점의 공통 수열 그 자체를 저장하도록 코드를 작성하였다. 이전에 파이썬으..

2022. 5. 14. 14:30
코딩/백준 (Python)

백준 11779번: 최소비용 구하기 2 (Python, C++)

접근 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 백준 사이트의 알고리즘 문제집을 순서대로 하나씩 풀어보는 방식으로 C++ 를 이용한 풀이를 하고있는데, 아직 안풀었는데 실패인 문제가 있어 보니 이전에 python으로 통과하였는데 재채점으로 시간초과가 된 문제였다. C++로 다시 풀어보고, 비슷한 방법으로 Python 코드도 수정하여 둘다 풀이 완료하여 코드를 수정했다. 전에 문제들과 비슷하게 DP와 BFS ..

2022. 5. 10. 23:59
코딩/백준 (Python)

백준 6087번: 레이저 통신 (Python)

접근 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 처음에는 BFS 알고리즘을 이용하여 visited 배열 (r, c) 에 해당 위치에 도달할 수 있는 최소 거울 수를 저장해가면서 탐색하면 아주 쉽게 풀 수 있을 것이라고 생각했다. 하지만 그 생각이 틀렸다는 것을 알 때까지는 오래 걸리지 않았고, 이후에는 꺾은 수가 적은 경우를 먼저 탐색하는 0 1 BFS 방법을 이용도 해봤지만 잘 되지 않았다. 결론적으로는 BFS 알고리즘을 변형하..

2022. 4. 20. 01:36
반응형