Study/Algorithm (36) 썸네일형 리스트형 코딩테스트를 할 땐 함수에 주석을 써두자 코딩테스트를 할 때 정신을 빼놓지 말자 점화식은 "dp[n,m] : s[n]을 포함하는 그룹의 시작 인덱스" 로 세워두고 코드에 짠건 "s[n]을 포함하는 그룹의 길이" 를 리턴하도록 짰다. 심지어 중간에는 인덱스로 잘 짜놓고 base case를 그룹의 길이를 리턴하도록 짜다니... 정신이 없다고 함수에 주석을 써두지 않았기 때문에 이런 실수가 발생했다. 함수를 작성할땐, 그리고 점화식을 작성할 땐 주석으로 잘 써두자. base case로 리턴하는 값도 주의해서 작성하자! 코테 끝나니까 바로 눈으로도 디버깅이 되더라. 무엇보다 제일 중요한건 당황하지 않는것. 첫번째 문제도 찬찬히 훑어보니 어디서 예외가 발생했는지 알 수 있었다. 첫번째 문제처럼 앞으로도 차분하게 해결하자. 과숙체락이니, 너무 코테 하나에.. [프로그래머스] 더 맵게 개요 programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같�� programmers.co.kr 힙이다. 그냥 우선순위 큐를 이용해서 풀었다. while(int temp = q.front() < K)라고 했다가 temp에 1 아니면 0이 저장되는 바람에 헤맸다. 주의하자. 우선순위 큐 관련 포스팅 : koosaga.com/9 STL priority queue 활용법 모든 nlgn들의 영웅(?) 같은 priority_queue 존재 그 자체로 멋지지만.. [프로그래머스] 다리를 지나가는 트럭 개요 programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이�� programmers.co.kr 기본적인 큐 문제 순서대로 큐에 넣고 빼면 된다. 코드(정답, 100/100점) [백준 #2251] 물통 unordered_set에는 pair가 안 들어가는구나. 코드(정답, 1984KB, 0ms) /** * @name: 물통 * @link: https://www.acmicpc.net/problem/2251 * @date 2020-05-07 * @author sunmon * TIP: **/ #define MAX(a,b) (a>b)? a:b #define MIN(a,b) (a [백준 #2580] 스토쿠 개요 무조건 +1, -1이 능사는 아니라는 것을 배웠다. +1, -1했다가 틀림 ㅂㄷㅂㄷ 중복으로 사용하는게 아니면 +,-하지말자 www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 코드 (정답, 1984.. [백준 #14391] 종이조각 개요 완탐으로 풀었다. 크기가 N, M 1) ok = false; i += di; j += dj; } return ok; } int getVal(int i, int j, int len, int dir){ string str; if(dir ==0) str = paper[i].substr(j, len); //가로 else{ //세로 for(int k = 0; k str; paper.push_back(str); } cout [백준 #1525] 퍼즐 개요 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net bfs로 풀었다. 비트마스크로도 풀 수 있다고 한다. 나중에 비트마스크 공부하면서 다시 봐야지! 메모리가 엄청 빡빡하더라. 36MB? 이런건 처음봤다. 보통 256MB이렇게 주는데. 상태공간을 벡터로 넣으면 그정도 쓰나? 그냥 int로해도 876543210 (약 8억) < 2^31-1 (약 20억)이라서, int범위 안에 들어가길래 그냥 int로 바꿔서 넣었다. visited도 vector로 하면 느려서 unordered_set을 넣었다. 일반 set은 O(logn)인.. [백준 #9663] N-Queen 개요 백트래킹. 가지치기를 이용한다. dfs를 끝까지 갈 필요 없이 중간 가지를 자르면 된다. board라는 2차원 벡터에다 퀸을 놓을 수 있는지 여부를 저장한다. 퀸을 자리를 바꿔가면서 놔야하는데, 그때마다 [놓고 -> 다음 dfs돌고 -> 놓은거 다시 빼고] 과정을 거쳐야 함. 이 때 이전 상태를 복구하는 과정(빼는 과정)때 bool로 true/false힘들게 할 필요 ㄴㄴ 그냥 상태 변화시킬때 +=1(놓기), -=1(빼기) 해주기. 종만북 boardcover했던거처럼. 그리고 어차피 계속 행은 아래로 증가시키기때문에 상태를 변화시킬때 같은행~그 이전행들은 신경쓸 필요가 없다. 나는 퀸이 영향을 주는 자리를 기준으로 코드를 짰는데 다른 사람들은 퀸의 위치를 기준으로 코드를 짰다. board[][]대신.. 이전 1 2 3 4 5 다음
