코테공부
1.[코테준비] c++ 코테에서 알아야하는것들
이제 취준할때가 오면서 코딩테스트를 슬슬 준비하고있다. 3학년때 전과를해서 수업을 닥치는대로 듣고 동아리를 마구마구 들어갔더니 코테준비가 확연히 딸린다...코딩테스트는 일반적인 자료구조나 알고리즘 수업 과제와 어떻게 다른지 모르겠어서 인터넷 서치한 결과를 간결히 정리해
2.[알고리즘] 이분 탐색
이분탐색
3.[알고리즘] 투포인터
투포인터 개념 / 투포인터 문제풀이
4.[알고리즘] DFS & BFS
그래프
5.[알고리즘] 최단 경로
최단 경로 알고리즘
6.[알고리즘] 역추적(DP & 최단거리)
이론정리 문제풀이 이전에는 이전에 검사했을때 가장 컸던 수보다 지금수가 더 크면 dp + 1하고, path를 찾는식으로 했었는데, 이러면 0번 index에서 시작하는 수열밖에 찾지못함 가장 긴 수열은 중간에서부터도 시작할 수 있기 때문에,매번 0~i-1번까지 돌면서 하나하나 i번째 끝수랑 비교해야함. 지금 j값이 i보다 작은게 맞는지(증가수열이...
7.[알고리즘] 트리
이론정리 문제풀이
8.[알고리즘] 유니온 파인드
이론정리 문제풀이 이거 풀다가 똥을 너무 많이 쌌다,,ㅋㅎ 일단 merge 함수에서 실수로, 합칠거면 A집합의 루트node의 parent값을 B집합의 루트node값으로 바꿔줘야하는데, 그냥 A집합의 일반node의 parent값만 홀라당 바꿔줘서 틀렸었다. 집합전체를 다 옮겨야지 왜 하나만 옮기니,,!!! 저걸 고친 후에는 메모리 초과가 발생했는데, 알고...
9.[알고리즘] 최소 신장 트리(MST)
이론정리
10.[알고리즘] 위상정렬
11.[BOJ] N과 M
문제설명 자연수 N과 M이 주어졌을때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오 > 1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열 풀이 백트래킹 문제 재귀함수로 백트래킹 구현했음 for문으로 i=1~n까지 돌면
12.[알고리즘] 백트래킹
이론정리 문제풀이
13.[BOJ] N-Queen
문제설명 > N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 퀸이 공격할 수 있는 위치는 같은 열, 같은 대각선 내에 존재할때 같은 대각선 내의 위치좌표들간의 공통점이 뭔지 알아내는게 중요 풀이
14.[BOJ] 스도쿠
스도쿠는 무조건 9x9 형태이고, 영역이 또 9칸으로 나뉘는 형태열과 행 뿐만 아니라, 영역이 같은지도 봐줘야함그래서 backtracking 외에 영역을 알아내는 함수가 별도로 필요!
15.[BOJ] 체스판 다시 칠하기
chessChange 설명 (row, col) 에서 시작하는 8 * 8 체스판 만드는 데 드는 최소 카운트를 리턴함. B로 시작하는 체스판을 기준으로 계산한 후, W로 시작하는 체스판 만드는 바꾸는 칸 수는 64에서 앞의 카운트 빼서 계산! 행 변화값 + 열 변화값이 짝수면 시작색(B)과 동일해야 함 -> 동일하지 않다면 카운트 행 변화값 + 열 변화...
16.[BOJ] 영화감독 숌
666관련 문제 ㅋㅋㅋ 종말의 숫자가 존재를 하면 cnt를 늘리는 문제!브루트포스로 풀면 되므로 그냥 되는대로 하나씩 훑으면서 체크하면된다 간단함
17.[BOJ] 분해합
\-이 문제도 브루트 포스분해합이 n인 경우를 그냥 쭉 돌면서 찾는방식임.
18.[BOJ] 바이러스, 국영수, 중복제거 정렬
바이러스 한 컴퓨터가 걸리면 연결돼있는 모든 컴퓨터가 걸린다는점에서 그래프 탐색을 해야함 그러므로 그 방법으로 dfs나 bfs가 있는건데, 공부를 위해서 두가지 방법 모두 짜봄 방식은 항상 똑같음 queue나 stack이 빌때까지 while문을 돌면서 pop을 해서 값을 빼고, 연결된 노드들을 하나하나 다 돌면서 방문한 곳이 아니면 pus...
19.[BOJ] 균형잡힌 세상
매우 간단한 괄호 체크 문제!이퍼에서도 몇번 나왔던거로 알고있다.스택에 왼쪽 괄호를 넣고, 닫는 괄호가 나오면 스택에서 괄호를 빼는식!만약 스택에 괄호가 남아있거나, 암것도 없는데 괄호를 빼려고 하는경우 잘못된거고,잘 비워진 경우에는 성공한거로 판단해서 출력하면 된다!