링크 https://www.acmicpc.net/problem/11501 난이도(solved.ac 참고) 실버3 풀이 뒤에서부터 보자! b_max라는 변수에 리스트의 마지막 값으로 일단 두고 마지막에서 처음까지 도는 반복문에서 더 큰 것이 있으면 바꿔주고, 없으면 마지막 값에서 인덱스의 값을 빼준 만큼 이익에 더해주면 된다.

링크 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 난이도(solved.ac 참고) 골드5 풀이 메모리 제한이 없다면, 걍 실버급도 안되는 문제라고 생각했다. 처음에 그냥 input값 받은 것들 전부 하나로 합친 다음에 거기서 n-1번째 인덱스를 추출하면 되지 않나? 라고 생각해서 바로 제출했는데 역시 메모리 초과가 떴다. 하기야 그렇게 풀 수 있으면 이게 골드 5일수가 없지.. 메모리가 초과된다는 건, 결국 저장되는? 값이 많다는 얘기라고 생각한다..

링크 https://www.acmicpc.net/problem/11497 난이도(solved.ac 참고) 실버1 풀이 이 문제는 결국 가장 큰 게 중앙에 오고, 다음으로 큰 값들이 왼쪽오른쪽에 차례차례 들어오게 한 뒤에 max값과 양 옆 인덱스와의 차이 중 큰 값을 출력하면 되는 것이다. 예를 들면 9 -> 7 9 -> 7 9 5 -> 4 7 9 5 -> 4 7 9 5 2 이런 식으로 말이다. 이렇게 만든 뒤에 (9-7)과 (9-5)를 비교해서 더 큰 4가 출력되는 것이다. 아이디어 자체는 보자마자 떠올렸는데, 오히려 구현에 시간이 좀 들었다;; 근데 .. 풀고 나서 다른 사람들 코드를 보니까, 너무 쉽게 풀었던데..? 역시 효율성은 개나줘버린 코드답다 나의 코드(오답) 최대값 인덱스를 구해서, 양 옆의..

링크 https://www.acmicpc.net/problem/18870 난이도(solved.ac 참고) 실버2 풀이 set 자료형(집합)은 중복된 값을 제거한다. 제거한 값을 리스트로 변환한 뒤에 그 값을 key(a2[i]):value(i)의 형태로 for문을 돌면서 딕셔너리 형태로 만들었다. 이렇게 되면 결과값은 예제 입력을 넣었을 때 {-10: 0, -9: 1, 2: 2, 4: 3} 가 된다. 여기서 우리가 뽑아내야 할 값은 0, 1, 2, 3이다. 우리가 input 값으로 받은 a 배열에 대해 딕셔너리에서 해당하는 부분의 value를 리턴하면 되는 문제였다. set과 딕셔너리에 대한 개념이 없다면 못푸는 문제였다.

링크 https://www.acmicpc.net/problem/10026 난이도(solved.ac 참고) 골드5 풀이 색약자가 아닌 경우에 일반적인 BFS를 진행하여 visited를 사용하고, 그다음 색약자에 대한 조건을 설정한 후(R을 G로 바꾸기) visited를 다시 초기화한 뒤 BFS를 진행했다. BFS에서 x,y좌표를 움직였을 때 그 부분이 방문되지 않았고(not visited) 이전 값과 같은 경우(둘다 R이거나 둘다 G이거나 둘다 B이거나) 큐에 넣고 방문처리를 한 뒤(visited[nx][ny] = True) 다시 반복문을 돌았다.

링크 https://www.acmicpc.net/problem/7576 난이도(solved.ac 참고) 실버1 풀이 음 .. IndexError가 계속 떠서 무엇이 문제인가 했는데, 위 코드는 정답 코드지만 내가 계속 제출했다가 틀린 코드는 마지막 행에서 bfs(m, n)이 아니라 bfs(queue[0][0], queue[0][1])로 넣었었다. 이렇게 되면 상자 내에 토마토가 없을 때, 즉 리스트의 값이 전부 -1 또는 0만 있을 때 -1을 출력할 수 없고 IndexError가 뜨게 된다. 풀이 과정 함수 바깥에서 일단 이중 for문으로 input값을 받아서 만든 리스트(a) 내에 1이 있으면 큐에 그 좌표를 넣는다. 큐가 있다는 건 결국 1로 바뀐 무엇인가가 존재한다는 뜻이므로, while queue..

링크 https://www.acmicpc.net/problem/1697 난이도(solved.ac 참고) 실버1 풀이 BFS 활용했고, 다음 큐가 비어있을 때까지 계속 진행하는데, 우선 popleft를 한 뒤에 그 값에 대해 1을 뺀 값, 1을 더한 값, 2를 곱한 값 중에 10만보다 작거나 같고, visited의 값이 0인 경우(그러니까, 방문하지 않은 경우) 그 값을 큐에 넣은 뒤 그 인덱스에 해당하는 visited의 값을 1 더해줬다. 여기서 visited는 방문 여부로도 판단할 수 있지만, 이동한 횟수로도 그 기능을 한다. 그 값이 0이라면 한번도 방문한 적이 없는 것이고, 0이 아니면 방문한 적이 있는 것이다. 시간 없어서 일단 여기까지 풀었는데, 이따 밤에 다시 풀어봐야겠다 ㅠㅠ 풀었는데, 통과..

링크 https://www.acmicpc.net/problem/18234 난이도(solved.ac 참고) 골드4 풀이 여기서 느낀 건, 시간 복잡도의 중요성이었다. 풀이(시간초과) 기존에 내가 풀었던, 시간 초과한 코드를 보면 min과 remove를 같이 썼다. 사실 min 하나만 들어가더라도 이미 이중 반복문과 다를 바가 없었는데, 예제는 다 맞아서 제출했더니 하나도 진행을 하지 못하고 오류가 났다. 다시 곰곰이 생각을 해보니까, t에 대한 for문을 전개할 게 아니라 n에 대한 for문을 전개해야 시간복잡도 선에서 발생하는 문제를 해결할 수 있을 것이라는 생각이 들었다. n(날짜)에 대해서 for문을 전개하려면.. for문 내부에서 가장 나중에 먹을 당근에 투여된 영양제의 횟수를 한번에 구해야했다. ..

링크 https://www.acmicpc.net/problem/1012 난이도(solved.ac 참고) 실버2 풀이 이렇게 좌표 형태로 나타난 문제는, dfs에서 x좌표와 y좌표를 구해준 뒤에 재귀 형태로 둔다. 그 다음, 테스트 케이스 횟수인 t회 도는 반복문 내부에서 input 받고 빈 행렬 만들고, a, b 입력받은 뒤에 넣어주고, 2중 for문을 통해 전체 행렬을 돌면서 값이 1인 부분을 조사한 뒤에 1이면 dfs 처리한다.

링크 https://www.acmicpc.net/problem/1260 난이도(solved.ac 참고) 실버2 풀이 걍 뭐.. 설명할 것도 없다. 이거 못풀면 다른 모든 그래프 탐색 문제도 못 푼다.. 일반적인 DFS와 BFS 구현에서 아주 살짝 달랐던 점은, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 점이다. 이 부분은, v 지점을 방문 표시한 뒤에 인접 리스트의 인덱스 v를 기준으로 연결된 여러 정점 중 가장 작은 것부터 방문해야 된다는 뜻이다. 따라서, graph에 대한 for문을 돌 때 sorted() 처리를 해주면 된다. 아 그리고, 인접 리스트의 총 길이는 n과 m 중 큰 값 + 1만큼 되어야 한다는 점도 고려해야 한다. 예를 들어 정점은 1000개지만 ..