Kiki Devlog

코딩 테스트 보기 전에 C++ 손풀기로 매번 푸는 dfs문제. 매번 풀 때마다 풀이가 달라지는걸 보는것도 재미있다. 풀고 비교해 보니 이전에 풀었던 코드는 visited vector를 손수 for문으로 초기화했었다. vector 초기화 방법을 몰랐나보다. 이번에는 재 그래도 조금씩 발전하면서 깔끔해지는 중. #include #include #include using namespace std; int dx[4] = { 0,0,-1,1 }; int dy[4] = { 1,-1,0,0 }; queue q; int bfs(vector &picture,vector & visited, int x,int y,int m,int n){ int count = 1; int curColor = picture[x][y]; int..

푸는 방법을 알고도 long long int 를 넘어버리는 계산 결과 때문에 에러가 나는 걸 못찾아서 한참 걸렸다. 이틀 전에도 이랬는데 overflow 꼭 주의하자 풀이방법 아래 표에서 dp 계산 식을 도출한다. 내 코드 #include const long long flowDefender = 1000000000; const int maxNum = 201; using namespace std; int main() { long long dp[maxNum][maxNum] = { 0 }; int N;//n까지, 합 int K;//갯수 cin >> N >> K; for (int i = 0; i

문제 2178번: 미로 탐색 (acmicpc.net) 주의할 점(내가 틀렸던 부분) 1 . 현재 칸이 미로를 벗어나는지 확인 2. 입력받은 string에서 한글자는 char 인데 char을 int로 바꾸지 않고 바로 int형 이차원 벡터에 넣어서 벡터에 아스키코드 값이 들어간 것 3. 최단 경로 찾기를 DFS로 푼것(DFS는 시간 초과 남) BFS 로 푼 코드 queue를 사용한 bfs를 사용. #include #include #include #include using namespace std; queue q; int visited[100][100] = { false }; int dist[100][100] = {0}; int dx[4] = { 0,0,-1,1 }; int dy[4] = { 1,-1,0,0..

문제 1260번: DFS와 BFS (acmicpc.net) 풀이 dfs는 재귀를 사용했고 bfs 는 queue를 사용하여 구현했다. 주의할 점은 한 노드에 노드가 여러개 연결돼있다면 작은 번호 순으로 방문한다는 조건을 잊지 않는 것이다. (이 조건 때문에 첫,두번째 제출이 틀렸음. 그래서 sort 함수를 사용하여 노드를 정렬하고 bfs,dfs를 실행했다.) 코드 #include #include #include #include using namespace std; vector graph(1001);//각node에 연결된 node들 bool nodeVisit[1001] = {false}; vector answer; queue q; void dfs(int curNode) { nodeVisit[curNode] ..

문제 2606번: 바이러스 (acmicpc.net) 후기 메모리 초과가 걸려서 vector을 모두 전역변수로 바꾸고 dfs를 중복으로 돌리지 않게 현재 번호의 컴퓨터가 이미 dfs를 실행했는지 bool값을 확인하고, 만약 bool 이 true(이미 실행함) 인 컴퓨터는 dfs를 돌리지 않도록 했다. (첫 if문) 틀렸던 점 반례를 생각하지 못함. 코드 32번 줄은 아래 반례와 같은 상황을 위해 추가하였다. 더보기 반례: 10 7 1 2 2 3 3 4 5 6 7 8 8 9 9 1 -->여기서 9도 바이러스에 걸리며 앞선 7,8이 바이러스에 걸림 정답: 6 내 코드 #include #include #include using namespace std; vector v(101);//각 번호에 연결된 comput..

문제 코딩테스트 연습 - [1차] 다트 게임 | 프로그래머스 스쿨 (programmers.co.kr) 후기 처음에 string을 for(char c: dartResult) 로 했더니 안돼서 잘못 푼 줄 알았는데 stoi() 쓸 때 함수 인자가 null인 경우를 처리해주지 않아서 core dump가 난 것이었다. 이것만 빼면 에러는 딱히 없었다. 나는 숫자/ S,D,T / *,# 세가지 경우를 나누기 위해 각 stage에 해당된 계산이 끝나면 continue를 써서 다음 스테이지는 굳이 검사하지 않도록했는데, 아래처럼 각 스테이지를 if문 3개로 크게 나누는 방법도 있었다. if(숫자라면) else if(s,d,t라면) else{ --*,# 라면 } 내 코드 #include #include #include..

문제 17478번: 재귀함수가 뭔가요? (acmicpc.net) 후기 백준 다시 공부해야지! 오랜만에 푼 재귀함순데 난이도가 높지 않아서 딱 재귀함수 오랜만에 푸는 나에게 좋았던 문제. 금방 풀었다. 그리고 출력할 글이 많은 문제는 내가 타자치지 말고 무조건 문제에서 복붙해서 쓰자. 그래서 계속 오답 나왔음. 내 코드 #include using namespace std; void printbar(int num) { for (int i = 0; i < num; i++) { cout

문제 링크 코딩테스트 연습 - 신규 아이디 추천 | 프로그래머스 스쿨 (programmers.co.kr) 후기 푸는 로직은 어렵지 않아서 풀긴 했는데, 코드를 깔끔하게 줄이는게 어려운 것 같다. 다른사람 풀이를 보니까 string 자체에서 pop_back() 같은 함수를 쓰는데 string 에 저런 함수를 쓸 수 있다는걸 처음 알았다. 새로운 정보 알아서 문제 푼 보람이 있다 (string class가 제공하는 기능들이 더 궁금하다면 string - C++ Reference (cplusplus.com) ) 내 코드 #include #include #include #include using namespace std; string solution(string new_id) { string answer = "..

오랜만에 코딩문제를 풀어야겠다 싶었다. 인턴한다고 너무 공부 안했다. Lv1이라해서 얕봤다가 은근 시간 오래걸렸다. 풀이법 숫자패드를 이차원 배열로 보고 손가락의 위치를 배열로 저장해서 다음번에 누를 숫자(이것도 이차원 배열로 표현)와의 거리(손가락과 숫자가 이차원 배열에서 떨어진 칸 수)를 계산. #include #include #include using namespace std; string solution(vector numbers, string hand) { string answer = ""; pair curLPos = make_pair(3,0); pair curRPos = make_pair(3,2); for(auto num : numbers){ if (num == 0) num = 11; // 원..

1699번: 제곱수의 합 (acmicpc.net) 식을 어떻게 세워야 할지 고민하다가 세웠는데 시간초과 떴음. 근데 내가 세운것보다 훨씬 간단한 식을 써도 됐다. 시간 초과될 줄 알고 안했었는데 시간복잡도를 조금 더 생각해 볼 걸 싶었다. 그리고 배열에 negative index를 쓰면 0이 나온다. 쓰레기 값이 나올 줄 알았는데 다 0이 나와서 궅이 j를 root 까지 계산해 줄 필요 없이 root자리에 i를 써도 될것같다. 내 코드 #include #include using namespace std; const int MAX = 100001; int dp[MAX]; int main() { int n; cin >> n; int root; for (int i = 1; i