알고리즘_문제풀이
1.백준 - 1018 체스판 다시 칠하기
체스판 다시 칠하기 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 MN 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 88 크기의 체스판으로 만들려고 한다. 체스판은 검
2.프로그래머스 - lv1 크레인 인형뽑기 게임
크레인 인형뽑기 게임 문제는 프로그래머스에서 확인 할 수 있다. ✔ 접근방법 스택을 이용한다. 기계에서 인형을 선택한다. 선택한 인형을 스택에 넣는다. 스택의 맨 위 인형과 현재 들어올 인형이 같다면, pop() 후 count 한다. ✔ 코드 ☝ 팁 c스타일
3.프로그래머스 - lv1 두 개 뽑아서 더하기
문제는 프로그래머스에서 확인 할 수 있다.중복이 없는 자료구조를 사용하기위해 SET을 사용한다.서로 다른 인덱스의 값을 더한다.set에 넣는다. 이때 중복은 허용하지 않는다.중복을 허용하지 않는 자료구조 set을 활용iterator의 활용auto 키워드를 사용하면, 컴
4.백준 - 1436 영화감독 숌
영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스
5.백준 - 15649~15652 N과 M(1)~(4)
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열DFS와 백트래킹으로 해결DFS를 통해 수열을 출력하는 함수 작성탈출조건 cnt가 m가 같아지면 재귀호출에
6.프로그래머스 - lv1 완주하지 못한 선수
문제는 프로그래머스에서 확인 할 수 있다.multiset을 이용참가자를 multiset에 넣는다.완주자를 mutliset에서 지운다.남은 참가자를 출력한다.중복되는 원소값을 저장할 수 있는 자료구조를 선정. multiset을 이용multiset에서의 erase 방식er
7.프로그래머스 - lv1 모의고사
문제는 프로그래머스에서 확인 할 수 있다.모든 경우를 판단, 완전 탐색std1, std2, std3 의 정답을 비교맞은 갯수를 map<std번호, 정답개수>에 저장map을 value값을 기준으로 정렬3-1 map->vector로 전환3-2 비교함수 정의3-3 so
8.백준 - 9663 N-Queen
N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. ✔ 접근방법 DFS, 백트래킹 재귀호출를 이용한 DFS 구현 탈출조건 정의
9.프로그래머스 - lv1 K번째 수
문제는 프로그래머스에서 확인 할 수 있다.Vector를 이용하면 쉽게 문제를 해결할 수 있다.주어진 인덱스에 해당하는 새로운 벡터를 만든다.정렬한다.sort() 함수를 통해 정렬을 수행할 수 있다. 이때 인자로는 iterator를 넘겨준다.프로그래머스
10.프로그래머스 - lv1 2016년
문제는 프로그래머스에서 확인 할 수 있다.단순구현프로그래머스
11.프로그래머스 - lv1 비밀지도
문제는 프로그래머스에서 확인 할 수 있다.비트연산(OR)을 이용한다.비트를 쉽게 다룰 수 있게 도와주는 bitset 라이브러리가 있다.프로그래머스
12.프로그래머스 - lv1 다트 게임
문제는 프로그래머스에서 확인 할 수 있다.정규표현식을 사용하여 각 부분을 추출정규표현식 패턴 정의문자열에서 패턴 추출규칙에 따라 점수 계산캡처 그룹을 이용하면 패턴에서 부분을 가져올 수 있다.위 코드의 경우 match0은 패턴에 일치한 전체 문자열을 가리키고match1
13.프로그래머스 - lv2 조이스틱
문제는 프로그래머스에서 확인 할 수 있다.name 에서 가장 긴 A문자열 뭉치를 찾는다.좌/우 방향 이동에 따른 횟수를 구한다.2-1. 정방향으로 진행하였을 때의 이동횟수2-2. 정방향으로 진행하다 'A'를 만나고 역방향으로 진행하는 이동횟수상/하 방향 이동에 따른 횟
14.프로그래머스 - lv2 큰 수 만들기
문제는 프로그래머스에서 확인 할 수 있다.가장 큰 수를 만들기위해 k+1자리 중 가장 큰 수를 찾고, 그 앞의 숫자를 지운다.남은 문자 중 해당자리와 뒤에 자리 문자를 비교해서 해당 자리가 작으면 그 수를 제거한다.프로그래머스
15.프로그래머스 - lv2 카카오프렌즈 컬러링북
문제는 프로그래머스에서 확인 할 수 있다.BFS를 이용한 접근중복 좌표를 탐색하지 않도록 처리하는 것이 중요BFS문제라고 생각하지 못하고, 반복문을 이용하여 좌표들을 탐색하고 같은 색상별로 그룹을 만드는 풀이를 생각했다.문제에 주어진 테스트들은 통과했지만, 제출하였을때
16.프로그래머스 - lv2 주식가격
문제는 프로그래머스에서 확인 할 수 있다.이중포문을 이용한다.하나의 인덱스를 선택그 뒤에 나오는 원소 중 조건에 해당하는 인덱스를 찾는다.시간은 인덱스의 차이를 이용하여 계산한다.프로그래머스
17.프로그래머스 - lv2 기능개발
문제는 프로그래머스에서 확인 할 수 있다.스택을 이용. (아래 코드에서는 vector를 이용하여 스택처럼 사용)맨 앞 원소가 100보다 커지면, 앞에서부터 차례로 100이상인 수를 체크함프로그래머스
18.백준 1057 토너먼트
문제는 백준에서 확인 할 수 있다.name 에서 가장 긴 A문자열 뭉치를 찾는다.좌/우 방향 이동에 따른 횟수를 구한다.2-1. 정방향으로 진행하였을 때의 이동횟수2-2. 정방향으로 진행하다 'A'를 만나고 역방향으로 진행하는 이동횟수상/하 방향 이동에 따른 횟수를 구
19.백준 2458 키 순서
문제는 백준에서 확인 할 수 있다.자신의 키 순서를 정확하게 알기 위해서는 아래의 조건을 만족해야 한다.조건 : 자신을 제외한 모든 노드와의 연관관계가 있어야 한다.플로이드워셜 알고리즘을 이용자신을 제외한 모든 노드와의 연관관계를 확인한다.조건에 맞는 노드의 수를 세어
20.백준 1992 쿼드트리
문제는 백준에서 확인 할 수 있다.분할정복, 재귀로 풀이전체 배열을 4군데로 나눠 재귀적으로 처리압축이 가능한 상태라면 바로 압축압축이 불가능한 상태라면 재귀재귀 탈출조건을 먼저 정의하는게 빠른 재귀 설계에 도움을 주는 것 같음.
21.백준 1753 최단경로
문제는 백준에서 확인 할 수 있다.다익스트라 문제하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘그래프를 딕셔너리형태로 입력 받음1-1. 정점간 여러개의 간선이 있는 경우, 최솟값 하나만 입력받도록 갱신출발 정점에서부터 시작하여, 방문하지 않은
22.백준 15961 회전 초밥
문제는 백준에서 확인 할 수 있다.더블포인터 문제연속된 노드를 탐색할 때, 범위 내 양끝 노드만 추가,삭제하여 중복된 노드의 탐색비용을 줄인다.나온 노드들의 수를 딕셔너리를 이용하여 카운트한다.쿠폰 노드는 미리 딕셔너리에 반영한다.셋을 이용해서 중복체크를 할수도 있지만
23.백준 2665 미로만들기
문제는 백준에서 확인 할 수 있다.DFS(0,0)부터 (N,N)까지 탐색하며, 검은 블럭을 만날때마다 카운트하여 기록PQ를 이용하여 검은블럭을 가장 적게 만나는 순서로 탐색을 진행(N,N)에 도착하였을 때, 지나온 검은 블럭의 수를 결과로 리턴다익스트라 풀이도 가능함
24.백준 2293 동전 1
문제는 백준에서 확인 할 수 있다.DP(k+1)개의 인덱스를 가진 dp 배열 생성dpi는 숫자 i를 만들기위한 경우의 수점화식3-1. dp\[i] = dp\[i] + dp\[i-(사용하고자하는 동전)]입력받은 동전을 순회하면서 dp배열을 생성하면, 답을 얻을 수 있다.
25.백준 14502 연구소
문제는 백준에서 확인 할 수 있다.새로 세울 수 있는 벽이 3개이고, 반드시 3개를 세워야한다.벽은 조합으로 가능한 경우를 찾음BFS로 바이러스가 퍼질 수 있는 곳을 구함이후 BFS 함수를 빈칸의 조건을 조합의 결과에서 가져와 바꿔가면서 구함모든 경우를 탐색하는 브루트
26.백준 1051 숫자 정사각형
문제는 백준에서 확인 할 수 있다.기본적으로는 브루트포스를 이용하여 모든 경우의 수를 탐색하려 함.이미 찾은 정사각형이 있다면, 그것보다 작은 경우들은 탐색하지 않음.시간이 충분하여 모든 경우를 탐색할 수도 있을 것 같다.하지만 최대값을 구하는 문제의 경우, 현재 찾은
27.백준 1918 후위 표기식
문제는 백준에서 확인 할 수 있다.중위표현식 -> 후위표현식연산자별로 우선순위를 부여한다.중위표현식을 앞에서부터 탐색한다.피연산자는 출력하고, 연산자는 stack에 넣는다스택에 이전 연산자보다 우선순위가 작은 것이 온다면, 연산자를 스택에서 출력(pop)한다.스택을 이
28.백준 5637 가장 긴 단어
후위 표기식 문제는 백준에서 확인 할 수 있다. ✔ 접근방법 중위표현식 -> 후위표현식 연산자별로 우선순위를 부여한다. 중위표현식을 앞에서부터 탐색한다. 피연산자는 출력하고, 연산자는 stack에 넣는다 스택에 이전 연산자보다 우선순위가 작은 것이 온다면, 연산
29.백준 1759 암호 만들기
문제는 백준에서 확인 할 수 있다.가능한 조합을 구한 후, 조건에 맞는지 확인문제의 조건을 잘 확인하고, 검증하는 로직을 세우는 게 중요
30.백준 16236 아기 상어
문제는 백준에서 확인 할 수 있다.BFS 를 이용한 다소 복잡한 구현 문제상어의 처음 위치를 탐색BFS를 이용하여 최단거리에 있는 먹을 수 있는 물고기 탐색물고기들 중 조건에 맞는 물고기 하나 선별선별한 물고기까지의 거리 덧셈먹은 물고기 수를 체크하여 상어의 크기 결정
31.백준 1781 컵라면
문제는 백준에서 확인 할 수 있다.그리디 문제현재의 보상을 포기하고, 미래의 값을 취할 때, 더 큰 이득을 가지는 경우가 생김데드라인이 짧은 순서대로 값을 취하되,데드라인이 같은 문제들 중, 보상이 큰 문제가 들어온다면이전에 취했던 문제들 중 가장 작은 하나를 빼고,
32.백준 1654 랜선 자르기
문제는 백준에서 확인 할 수 있다.이분 탐색 문제만족하는 조건을 찾아 대상을 절반씩 나누어가며 탐색값의 범위를 확인하였을 때, 너무 크다 싶으면 이분탐색을 고려한다.테스트케이스2 7 (1~ 잘못된 값 나올때까지 해봄) 10 0 값 : 12 2 2
33.백준 5567 결혼식
문제는 백준에서 확인 할 수 있다.구현그래프 탐색, BFSBFS로 탐색하고, 뎁스를 고려하여 정답을 구해낸다.깊이 우선을 통해서도 답을 구해낼 수 있지만,일정한 뎁스에 해당하는 노드들을 찾기 위해서는 BFS가 효율적이다.
34.백준 15900 나무 탈출
문제는 백준에서 확인 할 수 있다.1번부터 모든 노드를 순회하는데,노드의 방문수가 짝수이면 No노드의 방문수가 홀수이면 Yes모든 리프 노드들의 뎁스의 합을 구함시간초과 발생 해결 팁visit의 여부를 array의 in으로 체크하면, O(n)만큼의 시간이 소요된다.vi
35.백준 11000 강의실 배정
문제는 백준에서 확인 할 수 있다.그리디수업은 시작 순서대로 정렬강의실은 우선순위큐를 이용하여 빨리 끝나는 순서대로 정렬만약 수업시작 시간이 현재 강의실 중 가장 먼저 끝나는 강의보다 빨리 시작한다면,새로운 강의실을 구해야함반례 참고 : 링크수업을 끝나는 시간 기준으로
36.백준 9935 문자열 폭발
문제는 백준에서 확인 할 수 있다.스택주어진 문자열에서 폭발문자열을 찾기위해, 폭발 문자열을 뒤에서부터 확인한다.위 방법 이외에도 여러가지 풀이가 있을 수 있음!
37.백준 11403 경로 찾기
문제는 백준에서 확인 할 수 있다.플루이드-워셜 알고리즘을 이용하여연결 관계를 계산하는 문제시간복잡도 : O(n^3)
38.백준 5212 지구 온난화
지구 온난화 문제는 백준에서 확인 할 수 있다. ✔ 접근방법 구현 인접한 세칸 또는 네칸이 바다(.)이면 잠긴다. 범위 밖의 공간은 다 바다이다. 출력하는 지도의 크기는 모든 섬을 포함하는 가장 작은 직사각형 다 잠겨도 하나는 출력해야함 ✔ 코드 ☝ 팁 가
39.백준 14503 로봇 청소기
문제는 백준에서 확인 할 수 있다.현재 바라보는 방향 기준으로 왼쪽으로 돌아가면서 탐색청소가 가능한 곳이면 그 방향으로 전진청소가 불가능한 곳이라면 왼쪽으로 회전구현 문제바라보고 있는 방향을 고려해야해서 조건이 까다로운 편하지만, 주어진 조건대로 천천히 구현하면 풀 수
40.백준 2469 사다리 타기
문제는 백준에서 확인 할 수 있다.구현???을 기준으로위에서의 결과를 계산아래에서의 결과를 계산계산 결과를 바탕으로 ???에 들어올 수 있는 경우를 계산문제를 보고 잘 접근하고 디버깅을 잘하는게 중요할 것 같다
41.백준 9375 패션왕 신해빈
문제는 백준에서 확인 할 수 있다.조합옷의 종류를 key로 하는 딕셔너리(해시테이블)을 만든 후,가능한 조합의 개수를 구함이전에 똑같은 문제를 프로그래머스에서 풀었었는데, 그럼에도 불구하고 또 틀렸던 문제각 카테고리별로 입지않는 경우를 포함해서 경우의 수를 구하고, 어
42.백준 3986 좋은 단어
문제는 백준에서 확인 할 수 있다.스택스택을 이용하여 같은 두 문자가 만나는지 체크입력 받은 문자열이 조건을 만족하면 좋은 단어주어진 상황에 어떠한 자료구조가 적합한지 판단하는 연습을 꾸준히 하자
43.백준 11652 카드
문제는 백준에서 확인 할 수 있다.해시테이블해시테이블을 이용하여 입력받은 수를 카운트 함입력된 키들의 값을 비교하여 정답을 도출key를 입력받을 때, 정수형으로 입력받는 것이 중요 key = int(sys.stdin.readline().rstrip()) 문자열로 받을
44.백준 2527 직사각형
문제는 백준에서 확인 할 수 있다.많은 조건 분기문제에서 제시하는 조건을 만족하기 위한 조건식을 잘 세워야함 가능한 상태를 미리 모두 정의해놓으면 좋음복잡하게 해놓을수록 디버깅하기 힘들고, 간단하게 할수록 디버깅하기 쉬움
45.백준 11723 집합
문제는 백준에서 확인 할 수 있다.set 자료구조 사용문제에 알고리즘 유형에는 비트마스킹이 들어가 있는데, set을 이용한 풀이도 가능한 것 같음