본문 바로가기

자료구조, 알고리즘6

[문제풀이] 백준 5427 불 🛎️ 문제 📢 틀린 이유불이 퍼지는 간격과 상근이가 움직이는 간격이 같으려면 BFS를 돌릴 때 불이 갈 곳을 탐색하고 que에 넣는 depth와 상근이가 이동하는 depth가 같아야 한다.그 부분을 구현하지 못해서 계속 모든 문제가 "IMPOSSIBLE"이 나왔다. 😀 제대로 된 코드제대로 문제를 풀려면 불을 넣는 큐 사이즈만큼만 다음 좌표를 탐색하고 상근이도 상근이의 큐 사이즈만큼만 다음 좌표를 탐색하고 이동시켜주어 둘이 움직이는 간격을 맞춰줘야 한다.주요 코드 while (!sangQ.isEmpty()){ int firesize = fireQ.size(); int sangsize = sangQ.size(); for (int i = 0; i ⚠️ for문에 큐의 size를.. 2025. 2. 14.

[문제풀이] 백준 1697 숨바꼭질 알고리즘은 안 풀면 까먹는 것 같다.BFS/DFS는 다른 유형에 비해 많이 풀어봤어서 손쉽게 풀 수 있을거라고 생각했는데한 번에 성공하지 못했다. ^-^ 머쓱 백준 1697 숨바꼭질 문제수빈이가 동생을 찾기 위해서 특정 이동 조건에 맞춰 탐색하는 문제이다.전형적인 BFS 문제인 듯 하다. X - 1X + 12 * X이동 조건이 규칙적이므로 탐색 위치가 반복될 수 있는데 처음에 방문체크를 빼먹은 이유는…..!그냥 잘못 생각했다.설명하기도 어렵게 생각의 오류를 범해서 적기가 어렵다..결론은특정 지점에 도착했을 때, 그 지점에서 이동할 수 있는 모든 경우의 수(3가지 이동 조건)는 한 번에 큐에 넣어서 다음 단계로 나아가기 때문에 한 번 방문한 곳에 다시 돌아올 필요가 없다.특히, 이 문제는 조건이 X-1 .. 2025. 2. 13.

[문제 풀이] SWEA 4615. 재미있는 오셀로 게임 SWEA 4615. 재미있는 오셀로 게임 시뮬레이션에서 8방향으로 탐색하는 경우와 간단한 시뮬레이션 유형을 연습해볼 수 있는 문제이다. 놓친 점1. 모든 칸이 검정돌, 흰색돌 두 가지로 채워지는 것이 아니다. (0,1,2 라는 경우가 있음)따라서, 돌의 개수를 셀 때 if 검정 -> 검정++ 와 else -> 흰색++ 가 아닌 if 와 else if 가 되어야 한다.=> 상황에 주어질 수 있는 경우의 수 놓치지 말기2. change 함수에서바로 다음 칸의 값만 보고 색을 변경할 수 있지 않음.그 너머의 칸들까지 보고나서야 어디까지 색을 변경할 수 있는지 알 수 있음!! ⭐⭐⭐⭐⭐즉, 조건은 너머의 칸들에게 걸어야겠징...=> 너머의 칸들을 보면서 (1) 같은 색인지 확인 (if문) (2) 어디까지인.. 2024. 8. 12.

[문제 풀이] 행복한 수열의 개수 (feat. 코드트리 조별과제 : 4주차) 문제 : 코드트리 행복한 수열의 개수 난이도는 쉬움이지만 테스트 케이스 생각을 못해서 꽤나 여러번 틀렸다..ㅎㅎ틀린 이유?테스트 케이스가 틀린 원인을 파악하기 보다 특정 테스트 케이스를 해결하기 위한 조건문을 작성함. 해결 방법!테스트 케이스가 틀린 원인을 파악하자!! 어려웠던 점 & 알게된 점!!🥲 수열이 같은 수가 반복되는지 확인하기 위해 배열의 앞 뒤 값을 비교하는 방법을 사용했다.그런데.. 배열의 인덱스 값을 넘어가면 안되니까 해당하는 조건을 걸었는데.. 해당 조건 때문에 cnt 가 증가하지 않고 넘어가는 경우가 생겼다.👏 배열의 크기를 크게 잡으면 된다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!진챠... 간단하잖아..?.. 2024. 8. 11.

[이론] 배열 (feat. 코드트리 조별과제 : 3주차) 정적 배열배열의 선언과 동시에 크기를 지정하며, 선언 이후에는 크기를 바꿀 수 없다.동적 배열길이가 자유자재로 변경될 수 있는 배열. 사용하고 싶은 만큼만 공간을 차지하고 사용할 수 있다. 정적 배열의 기본 연산삽입배열의 앞이나 가운데에 값이 삽입된다면, 새로운 값이 들어갈 자리를 확보하기 위해 다른 값들의 자리 이동이 필요하다. 따라서 일반적인(최악의 상황에서의) 시간복잡도는 O(N)이다.즉, 다른 값들의 자리 이동이 필요하지 않은 상황( 맨 뒤에 값이 삽입되는 경우)는 시간복잡도가 O(1)이다.삭제삽입과 마찬가지로 배열의 맨 뒤에 값이 삭제된다면 삭제 후 다른 값들의 자리 이동이 필요하지 않다.배열의 앞이나 가운데에서 값을 삭제한다면 삭제된 값의 빈 자리를 채워야 하므로 나머지 N-1 개의 값이 이동.. 2024. 8. 4.

[이론] 공간복잡도 (feat. 코드트리 조별과제 : 1주차) 공간복잡도란?메모리 사용량 (코드가 메모리에서 얼마나 차지하고 있는가?)공간복잡도가 왜 중요한가?컴퓨터의 메모리는 한정되어 있으므로 사용되는 메모리가 적을수록 효율이 좋음.메모리 사용을 미리 계산해보면 메모리 제한을 넘는 코드인지 확인 가능함. 공간복잡도 계산메모리 계산 기준- 메모리 계산 기준은 보통 C++ 기준자료형크기int4bytechar1bytedouble8byteshort2byte 계산 방법값이 생성 후 없어지는 경우도 있음특정 시점에 메모리를 차지하고 있는 값들이 가장 많은 경우를 고려함 int a[2천만] : 80MBint a[2백만] : 80 / 10 = 8MBchar a[2천만] : 80 / 4 = 20MBdouble a[2천만] : 80 * 2 = 160MB-- 공간복잡도 계산 예시 1.. 2024. 7. 19.

이전 1 다음

티스토리툴바