코딩테스트
1.[백준] 1991 트리 순회
[문제] 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 1991.jpg 예를 들어 위와 같은 이진 트리가
2.[백준] 1181번 단어정렬
문제링크 백준단어정렬 백준단어정렬.PNG string형태의 문자열을 입력받고 문자열을 길이가 짧은 순으로 정렬하는 문제이다. 길이가 같을 경우는 사전 순으로 정렬한다. 벡터를 이용해 데이터 저장하고, sort 함수를 이용해 정렬하였다. compare 함수를 정의하
3.[백준] 1431번 시리얼번호
문제링크 백준 1431 백준시리얼번호.PNG 백준시리얼번호2.PNG 문제를 풀기위해 시리얼번호의 길이와, 자리수의 합을 저장해야한다. 그러므로 serialNum 클래스를 만들어 문자열을 받으면 길이롸 자리수의 합을 갖고 있도록 하고, sort 함수를 이용해 조건에
4.[백준] 2579 계단 오르기
백준2574 계단오르기 바로가기 이 문제에는 규칙이 있는데, 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점
5.[백준] 1260 DFS와 BFS
백준 1260 DFS와 BFS 바로가기 그래프로 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램이다. 단, 방문할 수 있는 정점이 여러개 인 경우에는 정점 번호가 작은 것을 먼저 방문한다. C++ 구현
6.[백준] 2178 미로탐색
백준 2178 미로탐색 바로가기 C++ 코드
7.[백준] 1182 부분 수열의 합
[백준 1182]부분수열의 합 1182.PNG 재귀를 이용해 해결하였다. 모든 가능한 부분 수열을 구해 합과 같으면 카운트를 올렸다. C++ 코드 아래 방법은 비트마스크를 사용한 방법이다. 부분집합을 '하나의 수'로 나타내는 개념인데, 만약 {1,2,3,4,5}
8.[백준] 2565 전깃줄
백준2565두 전봇대 사이의 전깃줄이 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 문제이다.전깃줄이 교차하지 않으려면 연결된 번호가 순차적으로 증가하거나, 감소해야한다.LIS(Longest Increasing Subsequence) 관련 문제인데라
9.[백준] 1149 RGB거리
백준1149점화식dpi = \_min(dpi - 1, dpi - 1) + ai;dpi = \_min(dpi - 1, dpi - 1) + ai;dpi = \_min(dpi - 1, dpi - 1) + ai;dpi => i번째 집을 j색으로 칠한 경우
10.[백준] 16935 배열 돌리기 3
백준16935예시 보면서 직관으로 푸는게 더 쉬운 것 같다.3,4번 연산은 N,M이 바뀌므로 주의할 것.
11.[백준] 2267 단지번호붙이기
백준2267dfs(재귀),bfs를 이용하여 구현해 보았다.
12.[백준] 2206 벽 부수고 이동하기
백준2206큐에 (x,y),벽을 부쉈는지 여부의 정보를 포함한다.벽을 1번은 뚫을 수 있으므로,벽인 경우인데 벽을 뚫지 않고 지나온 경우 뚫고 진행하는 경로벽인 경우인데 벽을 뚫고온 경우는 더이상 진행할 수 없으므로 pop통로인 경우는 그냥 진행, 벽을 뚫은 정보도 그
13.[백준] 13460 구슬탈출 2
\[백준13460] 구슬탈출2입력을 받아 현재 각 구슬의 위치와, 구멍의 위치를 기록한다BFS 시작한다각 구슬을 이동시킬때 구멍에 도달했거나 다음 이동할 장소가 벽이면 반복을 중단한다.고려해야할 경우는 다음과 같다.빨간 구슬과 파란 구슬이 겹쳐 있을 경우 (일직성 상에
14.[백준] 3190 뱀
\[백준 3190] 뱀<풀이 과정>1.(0,0)에서 시작하여 우측으로 진행하고 시간은 1초부터 시작한다.2\. 현 위치에서 이동할 방향으로 머리를 1칸 이동2-1. 이때 이동할 수 있는 위치(map 혹은 사과)라면 이동한다.3\. 이동한 자리가 사과가 아니면 꼬리
15.[백준] 13458 시험감독
\[백준13458]시험감독간단한 산술을 이용한 문제다.출력을 long long int 형식, 형식 지정자 %lld로 받아야 올바른 결과가 나온다.각 강의실 인원에서 총 감독관이 담당할 수 있는 학생의 수를 빼고,나머지 인원에 대해 부 감독관이 몇명 필요한지 계산하면 된
16.[백준] 7576 토마토
\[백준7576]토마토전형적인 BFS 문제였다.단, 익은 토마토가 1개 이상일 수 있기 때문에 동시다발적으로 진행되어야 한다는 점이 약간 까다로웠다.그래서 큐에 토마토의 좌표와 익는데 걸리는 시간을 포함해주고, bfs 시작 전에 익은 토마토는 모두 큐에 넣었다.종료 조
17.[백준] 1012 유기농배추
\[백준1012]유기농배추\[백준2267]단지번호붙이기 문제와 유사한 문제였다.오탈자를 줄이고 모듈화 시켜서 푸는 방식으로 가야겠다...ㅠㅠ오타때문에 계속 런타임 에러나서 뭘까 뭘까 하다가디버깅 하면서 보니까 dy\[]={0,0 -1,1}로 했다는....
18.[백준] 11047 동전0
\[백준11047]동전0간단한 산술 연산을 통해 풀수 있었다.남은 금액을 동전의 단위로 나누었을때 0보다 커지는 경우만 동전 갯수에 포함시키고 그 금액을 뺀다.이를 반복하면 된다.
19.[백준] 14502 연구소
\[백준14502]연구소브루트포스와 BFS를 이용하여 해결하였다.풀이 방법은 1\. 모든 빈칸에 무작위로 3가지 벽을 세울수 있는 경우를 모두 조사한다.2\. 각 경우마다 바이러스가 퍼졌을 때의 안전구역의 갯수를 조사한다.(BFS)3\. 안전구역의 개수가 최대가 되는
20.[백준] 14503 로봇청소기
\[백준14503]로봇청소기재귀함수의 return 시점을 생각하느라 까다로웠다.빈 공간을 청소한 후, 4 방향을 검사한다.차례대로 검사하는데 빈칸이 나오면 청소하고 남은 나머지 방향은 검사 할 필요가 없다.조건대로 청소했거나 벽이라면 그 방향으로 방향을 바꿔주고 계속
21.[백준] 14889 스타트와 링크
\[백준14889]스타트와 링크백트래킹과 bfs를 이용하여 풀었다.완전탐색을 해야하는 문제이다.가능한 모든 팀 조합을 구해서 각각의 능력치를 계산해 비교해야한다.1\. 스타트팀으로 정할 선수를 뽑는다. (n이 짝수이므로 스타트팀만 정해주고, 나머지는 자동으로 링크팀으로
22.[백준] 14889 스타트와 링크
\[백준14889]스타트와 링크백트래킹과 bfs를 이용하여 풀었다.완전탐색을 해야하는 문제이다.가능한 모든 팀 조합을 구해서 각각의 능력치를 계산해 비교해야한다.1\. 스타트팀으로 정할 선수를 뽑는다. (n이 짝수이므로 스타트팀만 정해주고, 나머지는 자동으로 링크팀으로
23.[백준] 10610 30
\[백준10610]30그리디 알고리즘에 있었던 문제.숫자를 입력받고, 가능한 수 조합 중 30의 배수가 되는 수 중 가장 큰 수를 출력한다.처음에는 가능한 수 조합을 모두 구하려고 했는데, 30의 배수를 찾는다는게 단서였다.1) 마지막 수가 0이 되어야 하고2) 나머지
24.[백준] 2156 포도주 시식
\[백준2156] 포도주 시식효주가 포도주 시식을 하려고 한다.테이블 위에는 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여있다.다음과 같은 규칙을 지켜야한다.1\. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓
25.[백준] 1110 더하기 사이클
백준\[1110번] 더하기 사이클처음에 조건대로 문자열 연산으로 했다가, 시간초과가 났다.그래서 산술 연산으로 바꾸어보았다.파이썬 코드
26.[백준] 4963 섬의 개수
\[백준4936번]섬의 개수간단한 bfs 문제.대각선도 체크해줘야 하는것이 베리에이션.
27.[백준] 11404 플로이드
\[백준11404]플로이드제목부터 플로이드.
28.[프로그래머스] 완주하지 못한 선수
근 2년만에 다시 코딩테스트 연습을 하려고 프로그래머스에 들어갔다... 코테 푸는 방법을 다 까먹어서 1단계부터 애먹었다 ㅠ^ㅠ그때는 C++ 로만 풀었었는데 졸업하고 잘 안쓰다보니ㅋㅋ 메서드들 까먹...ㅠ 대학생때 매일 백준 풀때는 이렇게 돌머리는 아니였던 것 같은데.
29.[백준] 1991 트리 순회
[문제] 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 1991.jpg 예를 들어 위와 같은 이진 트리가