만약 RESTAPI로 작업을 하는경우(WEBservice)에는 OAuth2의 라이브러리를 server단에서 처리하는 로직이 가장 깔끔하다

만약 Android등의 application과 작업하는 경우에는 Library를 import할 필요가 없다. 이 경우는 KakaoDeveloper의 RESTAPI공식문서를 참조하여 Client단에서 Token을 받아서 서비스하는 것이 합당하다.

• WEBservice

  웹서비스는 우선, OAuth2의 client로 kakao를 등록해줘야 하는 작업이 필요함 -> 왜냐면 기존 library에는 google, facebook, twitter등의 글로벌 기업만 표준으로 잡혀 있기에.. 표준을 따른 Oauth2 client를 등록해줘야 한다.

• Library설치(build.gradle) 추후 RESTAPI호출 및 JWT생성

  implementation 'org.springframework.boot:spring-boot-starter-oauth2-client'
  //katalk access token을 가져오기 위한 Oauth 서버와의 통신을 위한 webclient
  implementation 'org.springframework.boot:spring-boot-starter-webflux'
  //jwt
  implementation 'io.jsonwebtoken:jjwt:0.9.1'

• application.properties에 등록

  #REST API KEY
  spring.security.oauth2.client.registration.kakao.client-id=<REST API KEY>
  #authorization code ?? ?? uri
  spring.security.oauth2.client.registration.kakao.redirect-uri=<REDIRECT URI>
  spring.security.oauth2.client.registration.kakao.client-authentication-method=POST
  #spring.security.oauth2.client.registration.kakao.client-secret=secret-key //카카오는 존재하지 않음
  spring.security.oauth2.client.registration.kakao.authorization-grant-type=authorization_code
  #spring.security.oauth2.client.registration.kakao.scope=profile_nickname, profile_image, account_email, gender, birthday
  spring.security.oauth2.client.registration.kakao.scope=profile_nickname
  

spring.security.oauth2.client.registration.kakao.client_name=kakao spring.security.oauth2.client.provider.kakao.authorization-uri=https://kauth.kakao.com/oauth/authorize spring.security.oauth2.client.provider.kakao.token-uri=https://kauth.kakao.com/oauth/token spring.security.oauth2.client.provider.kakao.user-info-uri=https://kapi.kakao.com/v2/user/me spring.security.oauth2.client.provider.kakao.user-name-attribute=id

- 이후, 해당 값들을 OAuth2라이브러리에 등록해줘야 한다.
해당 파일은 config > OAuth2ClientRegistrationRepositoryConfiguration

```java
@Configuration
@EnableConfigurationProperties(OAuth2ClientProperties.class)
@Conditional(ClientsConfiguredCondition.class)
@RequiredArgsConstructor
public class OAuth2ClientRegistrationRepositoryConfiguration {

    private final OAuth2ClientProperties properties;

    @Bean
    @ConditionalOnMissingBean(ClientsConfiguredCondition.class)
    public InMemoryClientRegistrationRepository clientRegistrationRepository(){
        List<ClientRegistration> registrations = new ArrayList<>(
                OAuth2ClientPropertiesRegistrationAdapter.getClientRegistrations(this.properties).values());
        return new InMemoryClientRegistrationRepository(registrations);
    }

}

• Jwt생성

  @Component
  @Slf4j
  public class JwtTokenProvider {
    @Value("${jwt.access-token.expire-length}")
    private long accessTokenValidityInMilliseconds;
    @Value("${jwt.refresh-token.expire-length}")
    private long refreshTokenValidityInMilliseconds;
    @Value("${jwt.token.secret-key}")
    private String secretKey;
  
    public String createAccessToken(String payload){
        return createToken(payload, accessTokenValidityInMilliseconds);
    }
  
    public String createRefreshToken(){
        byte[] array = new byte[7];
        new Random().nextBytes(array);
        String generatedString = new String(array, StandardCharsets.UTF_8);
        return createToken(generatedString, refreshTokenValidityInMilliseconds);
    }
  
    public String createToken(String payload, long expireLength){
        Claims claims = Jwts.claims().setSubject(payload);
        Date now = new Date();
        Date validity = new Date(now.getTime() + expireLength);
        return Jwts.builder()
                .setClaims(claims)
                .setIssuedAt(now)
                .setExpiration(validity)
                .signWith(SignatureAlgorithm.HS512,secretKey)
                .compact();
    }
  
    public String getPayload(String token){
        try{
            return Jwts.parser()
                    .setSigningKey(secretKey)
                    .parseClaimsJws(token)
                    .getBody()
                    .getSubject();
        }catch (ExpiredJwtException e){
            return e.getClaims().getSubject();
        }catch (JwtException e){
            throw new RuntimeException("유효하지 않은 토큰입니다.");
        }
    }
  
    public boolean validateToken(String token){
        try{
            Jws<Claims> claimsJws = Jwts.parser()
                    .setSigningKey(secretKey)
                    .parseClaimsJws(token);
            return !claimsJws.getBody().getExpiration().before(new Date());
        }catch (JwtException | IllegalArgumentException exception){
            return false;
        }
    }
  

}

- Oauth2UserInfo 생성 : Oauth2로 받아오는 정보에 대한 기본 뼈대라고 생각
```java
public abstract class Oauth2UserInfo {
    protected Map<String, Object> attributes;

    public Oauth2UserInfo(Map<String, Object> attributes){
        this.attributes = attributes;
    }

    public Map<String, Object> getAttributes(){
        return attributes;
    }

    public abstract Long getId();
    public abstract String getName();
    public abstract String getNickName();
}

• KakaoUserInfo로 구체화

  public class KakaoUserInfo extends Oauth2UserInfo {
    public KakaoUserInfo(Map<String, Object> attributes) {
        super(attributes);
    }
    @Override
    public Long getId() {
        return Long.parseLong(String.valueOf(attributes.get("id")));
    }
  
    @Override
    public String getName() {
        return (String) getKakaoAccount().get("name");
    }
  
    @Override
    public String getNickName() {
        return (String) getProfile().get("nickname");
    }
    public Map<String, Object> getKakaoAccount(){
        return(Map<String, Object>) attributes.get("kakao_account");
    }
  
    public Map<String, Object> getProfile(){
        return (Map<String, Object>) getKakaoAccount().get("profile");
    }
  
    public String getProvider(){
        return "kakao";
    }
  

}

- Entity(USER)
```java
@Entity
@NoArgsConstructor(access = AccessLevel.PROTECTED)
@Table(name = "RTUSER")
@Getter
public class User extends BaseEntity{
    @Id
    @Column(name = "user_id")
    private Long id; //katalk PK 값으로 매핑하기
    private String name;
    private String nickName;
    private String kakaoAccessToken;
    private String kakaoRefreshToken;
    private String cloudEmail;
    private String calenderEmail;
    @Enumerated(EnumType.STRING)
    private Role role;

    @Column(name = "kakao_update")
    private LocalDateTime kakaoUpdate;
    @OneToMany(mappedBy = "user")
    private List<Calender> calenderList = new ArrayList<>();

    public User(Long id, String name, String nickName, String kakaoAccessToken, String kakaoRefreshToken, Role role){
        this.id = id;
        this.name = name;
        this.nickName = nickName;
        this.kakaoAccessToken = kakaoAccessToken;
        this.kakaoRefreshToken = kakaoRefreshToken;
        this.role = role;
    }


    public void setKakaoUpdate(){
        this.kakaoUpdate = LocalDateTime.now();
    }
    public void updateNickName(String nickName){
        this.nickName = nickName;
    }
    public void setKakaoToken(String kakaoAccessToken, String kakaoRefreshToken){
        this.kakaoAccessToken = kakaoAccessToken;
        this.kakaoRefreshToken = kakaoRefreshToken;
    }


}

• DTO(loginResponse)

  @Getter
  @NoArgsConstructor(access = AccessLevel.PROTECTED)
  public class LoginResponse {
    private Long id;
    private String name;
    private String nickName;
    private Role role;
    private String accessToken;
    private String refreshToken;
  
    public LoginResponse(User user, String accessToken, String refreshToken){
        this.id = user.getId();
        this.name = user.getName();
        this.nickName = user.getNickName();
        this.role = user.getRole();
        this.accessToken = accessToken;
        this.refreshToken = refreshToken;
  
    }
  }
  

- OauthService 생성
```java
@Service
@RequiredArgsConstructor
@Slf4j
@Transactional(readOnly = true)
public class OauthService {
    private static final String BEARER_TYPE = "Bearer";
    private final InMemoryClientRegistrationRepository inMemoryRepository;
    private final UserRepository userRepository;
    private final JwtTokenProvider jwtTokenProvider;

    /**
     * InMemoryRepo : oauth properties를 담고 있음.
     *
     * @getToken() 넘겨받은 code로 access토큰 요청
     * @getUserProfile 첫 로그인 시 회원가입 진행
     */
    @Transactional
    public LoginResponse login(String providerName, String code) {
        ClientRegistration provider = inMemoryRepository.findByRegistrationId(providerName);
        OAuth2AccessTokenResponse tokenResponse = getToken(code, provider);
        tokenResponse.getAccessToken(); // accesstoken
        tokenResponse.getRefreshToken(); // refreshtoken
        User user = getUserProfile(providerName, tokenResponse, provider);
        String accessToken = jwtTokenProvider.createAccessToken(String.valueOf(user.getId()));
        String refreshToken = jwtTokenProvider.createRefreshToken();

        return new LoginResponse(user, accessToken, refreshToken);
    }


    private OAuth2AccessTokenResponse getToken(String code, ClientRegistration provider) {
        return WebClient.create()
                .post()
                .uri(provider.getProviderDetails().getTokenUri())
                .headers(httpHeaders -> {
                    httpHeaders.setContentType(MediaType.APPLICATION_FORM_URLENCODED);
                    httpHeaders.setAcceptCharset(Collections.singletonList(StandardCharsets.UTF_8));
                })
                .bodyValue(tokenRequest(code, provider))
                .retrieve()
                .bodyToMono(OAuth2AccessTokenResponse.class)
                .block();
    }

    private MultiValueMap<String, String> tokenRequest(String code, ClientRegistration provider) {
        MultiValueMap<String, String> formData = new LinkedMultiValueMap<>();
        formData.add("code", code);
        formData.add("grant_type", "authorization_code");
        formData.add("redirect_uri", provider.getRedirectUri());
        formData.add("client_id", provider.getClientId());
        return formData;
    }

    private User getUserProfile(String providerName, OAuth2AccessTokenResponse tokenResponse, ClientRegistration provider) {
        Map<String, Object> userAttributes = getUserAttributes(provider, tokenResponse);
        //뭘가져올 수 있는지 알아야함.
        // id -> get('id')
        // nickname -> get('kakao_account) -> get("profile") -> get("nickname")
        // name -> get("kakao_account) -> get("name")
        if (providerName.equals("kakao")) {
            throw new IllegalArgumentException("잘못된 접근입니다.");
        }
        KakaoUserInfo kakaoUserInfo = new KakaoUserInfo(userAttributes);

        Long kakao_id = kakaoUserInfo.getId();
        String provide = kakaoUserInfo.getProvider();
        String name = kakaoUserInfo.getName();
        String nickName = kakaoUserInfo.getNickName();

        if (userRepository.findById(kakao_id).isPresent()) {
            throw new DuplicateSignInException();
        }
        User user = new User(kakao_id, name, nickName, tokenResponse.getAccessToken().getTokenValue(), tokenResponse.getRefreshToken().getTokenValue(), Role.ROLE_USER);
        User save = userRepository.save(user);

        return save;
    }

    private Map<String, Object> getUserAttributes(ClientRegistration provider, OAuth2AccessTokenResponse tokenResponse) {
        return WebClient.create()
                .get()
                .uri(provider.getProviderDetails().getUserInfoEndpoint().getUri())
                .headers(httpHeaders -> httpHeaders.setBearerAuth(tokenResponse.getAccessToken().getTokenValue()))
                .retrieve()
                .bodyToMono(new ParameterizedTypeReference<Map<String, Object>>() {
                })
                .block();
    }

}

• controller

  @RequiredArgsConstructor
  @Slf4j
  @RestController
  public class TestController {
    private final OauthService oauthService;
  
    @GetMapping("/login/oauth/{provider}")
    public ResponseEntity<LoginResponse> login(@PathVariable String provider, @RequestParam String code) {
        LoginResponse loginResponse = oauthService.login(provider, code);
        return ResponseEntity.ok().body(loginResponse);
    }
  }

Android와 통신하기 feat RESTAPI로 호출

• libary필요없음.

• 서비스 단만 바꾸면 된다(Oauth2와 의존성 있는 모든 것을 지우고)

  @Service
  @RequiredArgsConstructor
  @Slf4j
  @Transactional(readOnly = true)
  public class OauthService {
    private static final String BEARER_TYPE = "Bearer";
    private final UserRepository userRepository;
    private final JwtTokenProvider jwtTokenProvider;
  
    @Transactional
    public LoginResponse loginWithToken(String providerName, UserToken userToken) {
        User user = getUserProfileByToken(providerName, userToken);
        String accessToken = jwtTokenProvider.createAccessToken(String.valueOf(user.getId()));
        String refreshToken = jwtTokenProvider.createRefreshToken();
        return new LoginResponse(user, accessToken, refreshToken);
    }
  
    private Map<String, Object> getUserAttributesByToken(UserToken userToken){
        return WebClient.create()
                .get()
                .uri("https://kapi.kakao.com/v2/user/me")
                .headers(httpHeaders -> httpHeaders.setBearerAuth(userToken.getAccessToken()))
                .retrieve()
                .bodyToMono(new ParameterizedTypeReference<Map<String, Object>>() {})
                .block();
    }
  
    private User getUserProfileByToken(String providerName, UserToken userToken){
        if(!providerName.equals("kakao")){
            throw new IllegalArgumentException("잘못된 접근입니다.");
        }
        Map<String, Object> userAttributesByToken = getUserAttributesByToken(userToken);
        KakaoUserInfo kakaoUserInfo = new KakaoUserInfo(userAttributesByToken);
        Long kakao_id = kakaoUserInfo.getId();
        String name = kakaoUserInfo.getName();
        String nickName = kakaoUserInfo.getNickName();
        if(userRepository.findById(kakao_id).isPresent()){
            throw new DuplicateSignInException();
        }
        User user = new User(kakao_id, name, nickName, userToken.getAccessToken(), userToken.getRefreshToken(), Role.ROLE_USER);
        User save = userRepository.save(user);
        return save;
    }
  

}

```

• column이 정해져 있는 것들..!!
• 데이터는 최종적으로 표(TABLE)로 구성되어진다.
• 서로 연관되어 있는 표(TABLE)들을 GROUP으로 묶은것이 DATABASE == SCHEMA이다.
• 이러한 SCHEMA가 모여있는 곳이 DATABASE SERVER라고 한다.
• 보안관리가 쉬워짐.
• root사용자는 모든 접근이 가능함.

SQL이란

• Structured Query Language
• row == record == 행
• column == data_type == 열

문법

• DATA_BASE(SCHEMA) 생성하기 CREATE DATABASE 'db_name'

• DATA_BASE(SCHEMA) 삭제하기 DROP DATABASE 'db_name'

• DATA_BASE(SCHEMA) 출력하기 SHOW DATABASES

• TABLE(표) 사용하기 USE 'table_name'

DATA TYPE(m)

• m : data를 얼만큼 노출시킬 것인가 | 얼만큼 반영할 것인가
• 숫자 : INT, BIGINT,
• 조건 지정 : NULL(값이 없어도 OK), NOT NULL(값이 없으면 추가 X)
• 자동 증가 : AUTO_INCREMNET
• 문자 : VARCHAR, TEXT, LONGTEXT
• 시간 : DATE, DATETIME (데이터 삽입 시 NOW()함수와 자주 사용) -HOUR(DATETIME) -> 시간 -YEAR(DATETIME) -> 년도 -MONTH(DATETIME) -DAY(DATETIME) -MINUTE(DATETIME) -SECOND(DATETIME)
• PK(Primary Key) : 테이블의 데이터를 구별할 수 있는 key(식별자)

CRUD

• Create, Read, Update, Delete

• TABLE Column 만들기 CREATE TABLE 'table_name'('col_name' col_type Default(NULL_condition) Extra(AUTO_INCREMENT_데이터 추가시 자동으로 ++), PRIMARY KEY(id) ex) CREATE TABLE topic( id INT(11) NOT NULL AUTO_INCREMENT, title VARCHAR(100) NOT NULL, description TEXT NULL, created DATETIME NOT NULL, PRIMARY KEY(id));

• column 확인하기 DESC table_name

• column 추가하기 ALTER TABLE 'table_name' ADD 'new_col' col_type Extra(FIRST, AFTER 'col_name', default = 맨뒤)

• row(data) 추가하기 INSERT INTO 'table_name' (col1, col2, col3) VALUES (data1, data2, data3);

• 전체 데이터 확인하기 SELECT * FROM 'table_name;

• 특정 데이터만 확인하기 (projection) SELECT 'col1', 'col2' FROM 'table_name';

• 조건 설정하기

  • 조건 WHERE 'condition(col == col_name)' -> AND OR NOT 연산가능
    • 부분 조건 LIKE 'col' LIKE '문자%'
  • 정렬 ORDER BY 'col_name' DESC|ASC
    • 정렬이 여러개일 경우,, SELECT 'col1', 'col2' From 'table_name' ORDER BY 'col1' DESC, 'col2'(DEFAULT)
    • 제한 LIMIT 'Number'
  • 제한 범위 LIMIT 3,10; -> 인덱스 시작이 0임 (4번째부터~11번째까지)

• 최대값/최솟값 SELECT MAX('col') FROM 'table';

• 별칭 AS 로 바꾸기..

• UPDATE 하기(수정하기) UPDATE 'table_name' SET 'col_id' = "수정사항", 'col_id2' = "수정사항2" WHERE 'condition'

• DELETE 하기 DELETE FROM table_name WHERE 'condition';

• 중복제거하기 (컬럼에 중복되는 데이터들을 묶어준다) 주로 COUNT와 사용하여 Column에 나타냄 GROUP BY 'col_name'

• 집계함수 조건비교 HAVING '집계결과' condition

중복되는 TABLE 분리하기

• 별도로 테이블을 나누게되면, 인덱스(KEY)를 활용하여 중복/동명이인을 막을 수 있지만 데이터를 참조할 때, 관계가 생기기 때문에 한눈에 보기 어려움 -> JOIN으로 해결

• JOIN 하기 SELECT * FROM 'table1' LEFT JOIN 'table2' ON 'table1.col_id = table2.col_id';

• join시 col명이 겹치면 ambiguous하므로, table1.col_name으로 명시하여 projection하면 된다.

• Table 이름 변경하기 RENAME TABLE 'table_name' TO 'table_rename';

https://infinitt.tistory.com/186

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

• 0ms 시점에 3ms가 소요되는 A작업 요청
• 1ms 시점에 9ms가 소요되는 B작업 요청
• 2ms 시점에 6ms가 소요되는 C작업 요청 와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.
  한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

• A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
• B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
• C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms) 이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.
  하지만 A → C → B 순서대로 처리하면

• A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
• C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
• B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms) 이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.
  각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력 예

jobs	return
[[0, 3], [1, 9], [2, 6]]	9

입출력 예 설명

문제에 주어진 예와 같습니다.

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

Concept

• SJF : shortest job first - 실행시간이 낮은 순서대로 실행시켜버리기 -> 그러면 뒤에 기다리는 아이들이 기다리는 시간을 최소화할 수 있음.
• 실행시간을 기준으로 정렬을 해야하므로, 시작시간에 대한 정보를 따로 다뤄줘야함
• 실행시간이 낮으면서, 실행이 가능해야함(시작시간이 현재 시간보다 빨라야한다..)

Code

def solution(jobs):
    answer = 0
    n=len(jobs)
    #실행시간이 짧은 놈부터 먼저 처리한다.
    jobs.sort(key = lambda x:x[1])
    curr = 0
    while(jobs):
        flag = 0
        for job in jobs:
            #실행이 가능한 프로세스면
            if(job[0] <= curr):
                flag+=1
                #실행 가능 시간 갱신
                curr += job[1]
                print(curr)
                #대기시간을 넣어준다..
                answer += curr - job[0]
                print(job)
                jobs.remove(job)
                break
        #실행 가능한 프로세스가 없으면 시간을 진행한다..
        if(flag == 0):
            curr+=1
    return answer//n

참고

• 대기시간을 구하는 식을 세우는데 오랜 시간이 걸림..
• 대기시간 = 현재까지 진행한시간(여기서는 진행시간에 실행시간을 더해줬으므로,,) - 해당 프로세스 시작시간

문제 설명

카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.

용어의 정의 '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다. 그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다. 예를 들어, "(()))("와 같은 문자열은 "균형잡힌 괄호 문자열" 이지만 "올바른 괄호 문자열"은 아닙니다. 반면에 "(())()"와 같은 문자열은 "균형잡힌 괄호 문자열" 이면서 동시에 "올바른 괄호 문자열" 입니다.

'(' 와 ')' 로만 이루어진 문자열 w가 "균형잡힌 괄호 문자열" 이라면 다음과 같은 과정을 통해 "올바른 괄호 문자열"로 변환할 수 있습니다.

알고리즘

• 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
• 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
• 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
  • 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
• 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
  • 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
  • 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
  • 4-3. ')'를 다시 붙입니다.
  • 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
  • 4-5. 생성된 문자열을 반환합니다. "균형잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.

매개변수 설명

p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다. 문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다. 만약 p가 이미 "올바른 괄호 문자열"이라면 그대로 return 하면 됩니다.

입출력 예

p	result
"(()())()"	"(()())()"
")("	"()"
"()))((()"	"()(())()"

Concept

• 문제에서 알고리즘이 주어짐
• 이해하지 못했음
• 그냥 하라는대로 코딩했더니 답이 나옴..
• 나중에 이해해보자,, 사실 이해하기 어려우니깐 로직을 미리 준 것 아닐까,,

Code

def slicing(p):
    #종료조건..개수가 서로 일치할 때 !
    left = 0
    right = 0
    u = ''
    for ch in p:
        if(ch == '('):
            left += 1
            u += ch
        else:
            right += 1
            u += ch
        #종료
        if(left == right):
            #왼쪽부터 시작했다면 무조건 True
            #v배열은 u를 p에서 떼어낸 부분
            return u, p[left+right:], u[0] == '('
    #일어나지 않을 예외처리..
    return 0,0,False

def solution(p):
    answer = ''
    #1
    if(not len(p)):
        return p
    #2 더이상 분리할 수 없는 균형잡힌 문자열
    u,v,what = slicing(p)
    #3 
    if(what):
        #3-1
        return u + solution(v)
    #4
    answer = '(' + solution(v) +')'
    for ch in u[1:-1]:
        if(ch == '('):
            answer+=')'
        else:
            answer+='('

    return answer

참고

• 음... solution함수를 재귀적으로 구현한다는 것이 참.. 신박하다...

문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

s	result
"aabbaccc"	7
"ababcdcdababcdcd"	9
"abcabcdede"	8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"	17

Concept

• 몇개의 범위로 압축해야 최소값이 나오는지 정해져 있지 않음
• 최대 압축 가능 길이 = 문자열/2

Code

def solution(s):
    #압축 못하는 경우
    answer = len(s)
    #압축의 경우의 수 : 어떤 문자열이 얼만큼 반복되냐에 따라 다르므로 모든 경우
    #그래도 절반넘는 범위까지 볼 필요 없음(절반까지는 봐야함)
    for i in range(1, len(s)//2 + 1):
        #문자열 줄이기 전 길이
        length = len(s)
        #찾는 위치는 처음부터
        curr = 0
        #뒤에 얼마나 반복되는지 확인하기(끝까지)
        while(curr + i <= len(s)):
            #반복되는 문자열
            check = s[curr:curr+i]
            #다음 위치로
            curr += i
            #뒤에 해당 문자열이 몇개 있는지
            cnt = 1
            while(curr+i <= len(s)):
                if(check == s[curr:curr+i]):
                    cnt+=1
                    curr += i
                else:
                    break
            #반복된 횟수만큼 문자열이 줄었다.(반복횟수만큼은 증가)
            if(cnt>1):
                length = length - i*(cnt-1) + len(str(cnt))
        answer = min(answer, length)

    return answer

참고

• 음,, 슬라이싱을 잘하자!

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.
• 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

예제 입력 1

3 3 101 010 101

예제 출력 1

303 050 303

Concept

• bfs,,,bfs!!bfs!!bfs!!!!!!!!! (틀렸다...ㅋㅋ)
• 실행시간 초과..
• 실행시간 초과 이유 : 모든 원소? 해당하는 벽? '1'인 원소에서 계속 BFS탐색을 시도하니,, 상당히 오래걸리는 작업이 된다.
• 그렇다면,, BFS를 최소한으로 사용하려면?
• 관점을 뒤바꾸어 생각하도록한다.
• 통과되어 있는 벽들이 연결되어 있는 개수를 저장...
• 연결되어 있는 벽들마다 연결되어 있는 개수가 다르므로, 서로 구별하여 저장을 하여야 하고, 이를 dictionary형태로 저장한다.
• 이렇게 되면 BFS탐색을 많이 할 필요가 없음..(방문한 정보를 저장하므로 이전에 방문했던 곳을 skip하므로)
• FloodFill algorithm 이라고 함.
• 이 후, '1'이라는 벽에서 자기 주변에 연결되어 있는 벽들의 정보를 모두 더하면 됨.

Code

def bfs(i,j,num):
    cnt = 1
    graph[i][j] = num
    Q = []
    Q.append((i,j))
    while(Q):
        curr = Q.pop()
        for i in range(4):
            new_x, new_y = curr[0]+move[i][0], curr[1]+move[i][1]
            if((0<= new_x <n) and (0<= new_y <m) and visit[new_x][new_y]==False and graph[new_x][new_y]==0):
                visit[new_x][new_y] = True
                graph[new_x][new_y] = num
                Q.append((new_x,new_y))
                cnt += 1
    return cnt



def check(row,col, dic):
    what = set()
    for i in range(4):
        new_row, new_col = row+move[i][0], col+move[i][1]
        if((0<= new_row < n) and (0<= new_col<m) and graph[new_row][new_col]!= 1):
            what.add(graph[new_row][new_col])
    cnt = 1
    for i in what:
        cnt += dic[i]
    return cnt


n, m = map(int,input().split())
graph = [[]for _ in range(n)]
for i in range(n):
    graph[i] = list(map(int, input()))

move = ((-1,0),(1,0),(0,-1),(0,1))
dic = {}
visit = [[False for _ in range(m)] for _ in range(n)]
num = 2
for i in range(n):
    for j in range(m):
        if(not visit[i][j] and not graph[i][j]):
            dic[num] = bfs(i,j,num)
            num+=1

answer = [[0]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if(graph[i][j] == 1):
            answer[i][j] = check(i,j, dic)%10

for i in range(n):
    for j in range(m):
        print(answer[i][j],end = '')
    print()

참고

• 파이썬은,, 음.. 굳이 global선언을 안해도, 전역변수를 잘 가져와서 사용함. 아마 함수 밖에서 작성하는것은 다 global로 처리하는 듯..
• 왜 입장을 바꿔 사용하는 BFS탐색이 조금 더 빠른지 고민할 수 있었던 문제..

문제 설명

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼

아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

대기실은 5개이며, 각 대기실은 5x5 크기입니다. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다. 예를 들어,

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• places의 행 길이(대기실 개수) = 5
• places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
• places 원소의 길이(대기실 가로 길이) = 5
• P는 응시자가 앉아있는 자리를 의미합니다.
• O는 빈 테이블을 의미합니다.
• X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
• 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
• places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
• 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

입출력 예

places	result
[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]	[1, 0, 1, 1, 1]

입출력 예 설명 입출력 예 #1

첫 번째 대기실

No.    0    1    2    3    4
0    P    O    O    O    P
1    O    X    X    O    X
2    O    P    X    P    X
3    O    O    X    O    X
4    P    O    X    X    P

모든 응시자가 거리두기를 지키고 있습니다.

Concept

• 앉아있는 사람 'P'를 기준으로 맨해튼(?)거리만큼만 탐색
• 넓혀가며 찾는게 BFS탐색이 딱 좋아보임..
• 조건에 맞게 코딩하자.

Code

from collections import deque
#상 하 좌 우
move = ((-1,0),(1,0),(0,-1),(0,1))

def bfs(place, row, col):
    Q = deque()
    visit = [[False for _ in range(5)] for _ in range(5)]
    visit[row][col] = True
    Q.append((row, col, 0))
    while Q:
        curr = Q.popleft()
        if(curr[2]>2):
            continue
        if(place[curr[0]][curr[1]] == 'X'):
            continue
        if(curr[2] != 0 and place[curr[0]][curr[1]] == 'P'):
            return False
        for i in range(4):
            new_row, new_col = curr[0] + move[i][0] , curr[1] + move[i][1]
            if(0 <= new_row < 5) and (0<= new_col < 5) and (visit[new_row][new_col] == False):
                visit[new_row][new_col] = True
                Q.append((new_row, new_col, curr[2]+1))
    return True

def Check(place):
    for i in range(5):
        for j in range(5):
            if(place[i][j] == 'P'):
                if(bfs(place, i, j) == False):
                    return False
    return True


def solution(places):
    answer = []
    for place in places:
        if(Check(place)):
            answer.append(1)
        else:
            answer.append(0)
    return answer

참고

• 흠.. BFS탐색시 queue를 쓸까, deque를 쓸까, stack을 쓸까,,, 사실 다 차이 없지 않나..?
• visit array를 설정하여,, 갔던곳은 또 안가도록 막아준다....
• 사실 2칸씩만 움직일거라서,, 뭐 상관은 없을 것 같다...흠.....
• 이 부분에 대한 고민을 해보도록..! 숙제!

-> 숙제!!

• 사실 그것은,, 방문순서에 관심이 있는것!
• 스택을 쓰면,, DFS! 깊이 우선 탐색이 되는 것이고
• 큐를 쓰면,, BFS! 넓이 우선 탐색이 되는 것이다.. 이런 멍청한 고민을 왜 한거지..

• 사실 어렴풋이 알아서 그래..

[문제]

지점의 개수 n, 출발지점을 나타내는 s, A의 도착지점을 나타내는 a, B의 도착지점을 나타내는 b, 지점 사이의 예상 택시요금을 나타내는 fares가 매개변수로 주어집니다. 이때, A, B 두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 return 하도록 solution 함수를 완성해 주세요. 만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 됩니다.

[제한사항]

• 지점갯수 n은 3 이상 200 이하인 자연수입니다.
• 지점 s, a, b는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
• 즉, 출발지점, A의 도착지점, B의 도착지점은 서로 겹치지 않습니다.
• fares는 2차원 정수 배열입니다.
• fares 배열의 크기는 2 이상 n x (n-1) / 2 이하입니다.
• 예를들어, n = 6이라면 fares 배열의 크기는 2 이상 15 이하입니다. (6 x 5 / 2 = 15) fares 배열의 각 행은 [c, d, f] 형태입니다.
• c지점과 d지점 사이의 예상 택시요금이 f원이라는 뜻입니다.
• 지점 c, d는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
• 요금 f는 1 이상 100,000 이하인 자연수입니다.
• fares 배열에 두 지점 간 예상 택시요금은 1개만 주어집니다. 즉, [c, d, f]가 있다면 [d, c, f]는 주어지지 않습니다.
• 출발지점 s에서 도착지점 a와 b로 가는 경로가 존재하는 경우만 입력으로 주어집니다.

[입출력 예]

n	s	a	b	fares	result
6	4	6	2	[[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]]	82
7	3	4	1	[[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]]	14
6	4	5	6	[[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4,8], [4,3,9]]	18

concept

• 어느 구간에서 합승을 해야할 지 골라야 한다.(floyd warshall)
• 각각의 합승 구간에서 도착 지점까지 최소경로로 이동해야 한다. (floyd warshall을 이용하여 각각의 경로를 거쳐 가는 최소 비용을 미리 구해놓기)
• 그래프의 정보를 간선의 정보로 저장x -> floydwarshall은 그래프로 표현하는 것이 편함
• 완전탐색

Code

INF = 987654321

def solution(n, s, a, b, fares):
    answer = INF
    #그래프 선언 -> 최소비용을 구해야하므로 INF로 설정후 갱신
    graph = [[INF for _ in range(n+1)] for _ in range(n+1)]
    #0번째 노드는 사실상 필요 없음.
    for i in range(1, n+1):
        graph[i][i] = 0
    #양방향 그래프
    for fare in fares:
        graph[fare[0]][fare[1]] = graph[fare[1]][fare[0]] = fare[2]
    #floyd warshall
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
    #경유지 (k까지 같이 갔다가 최소비용으로 각자의 목적지로 이동)
    for k in range(1,n+1):
        answer = min(answer, graph[s][k]+graph[k][a]+graph[k][b])
    return answer

참고

• floyd warshall 시작점과 도착점의 최소 비용을 구하는 알고리즘.
• 어찌보면 하나의 경로만 거쳐 지나가는 최소비용을 구하는 것처럼 보이지만,, 잘 생각해보면 ex) 1->2->3->4의 이동 경로 1->4로의 최소 비용이라면, 1->3으로 도착하는 경로의 최솟값은 1->2->3으로 설정될 것이다..
• 다익스트라로도 구현해볼것 나중에..^^
• 만약, 최소한의 이동경로를 구하라고 한다면..?

[문제]

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

• info 배열의 크기는 1 이상 50,000 이하입니다.
• info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
• 개발언어는 cpp, java, python 중 하나입니다.
• 직군은 backend, frontend 중 하나입니다.
• 경력은 junior, senior 중 하나입니다.
• 소울푸드는 chicken, pizza 중 하나입니다.
• 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
• 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
• query 배열의 크기는 1 이상 100,000 이하입니다.
• query의 각 문자열은 "[조건] X" 형식입니다.
• [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
• 언어는 cpp, java, python, - 중 하나입니다.
• 직군은 backend, frontend, - 중 하나입니다.
• 경력은 junior, senior, - 중 하나입니다.
• 소울푸드는 chicken, pizza, - 중 하나입니다.
• '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
• X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
• 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
• 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

[입출력 예]

info	query	result
["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"]	["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"]	[1,1,1,1,2,4]

concept

• 4가지 query가 나옴.. and로 구분되어 있음(추후에 인덱스설정으로 and로 구분x)

• 해당하는 query에 만족하는 인원을 뽑아내야하는데,, 효율성 문제가 있으므로.. 바로 찾을 수 있어야함.

• 각 쿼리의 경우에 지원자의 점수를 (중복으로) 저장하여 찾는다.

• 각 쿼리로 나올 수 있는 경우의 수 = 4(개발언어+'-') * 3(직군+'-') * 3(경력+'-') * 3(푸드+'-') = 108가지..

• 108가지의 배열에 해당 점수들을 저장해서 질의에 해당하는 인원수를 찾아야 한다.

• 각각의 배열에 개별 query로 인덱스 접근이 가능해야하므로,, 인덱싱을 위하여 개별 번호를 부여해줘야함. ex) python(2)(3x3x3) and backend(1)(3x3) and senior(2)x3 and pizza(1) ex) 모든 조건이 없는 경우 = 0 + 0 + 0 + 0 = 0 인덱스.. ex) 모든 조건이 있는 경우 = 3x(3x3x3) + 2x(3x3) + 2x3 + 2 = 107인덱스..

• 각각의 질문에,, 해당 안되는 사항들을 저장해줘야하기때문에, 부분집합을 활용한다.

• 하나씩 포함이 안되는 경우로,, bit연산 활용 (부분집합이므로..)

Code

#이분법 탐색
from bisect import bisect_left
def solution(info, query):
    answer = []
    hashmap={'-':0, 
             'cpp':1, 'java':2,'python':3,
            'backend':1, 'frontend':2,
             'junior':1, 'senior':2,
            'chicken':1, 'pizza':2}
    #점수가 들어갈 배열..
    scores = [[] for _ in range(4*3*3*3)]
    for data in info:
        st = data.split()
        #해당 데이터는 '-'의 상황도 저장해야하므로, 부분집합..!
        arr = (hashmap[st[0]]*3*3*3,
              hashmap[st[1]]*3*3,
              hashmap[st[2]]*3,
              hashmap[st[3]])
        score = int(st[4])
        #부분집합의 원소의 개수 4개 -> 16가지 경우
        for i in range(1<<4):
            idx = 0
            # 부분집합에 불이 켜진 경우
            for j in range(4):
                if i & (1 << j):
                    idx += arr[j]
            scores[idx].append(score)

    for i in range(4*3*3*3):
        scores[i].sort()

    for string in query:
        q = string.split()
        idx = hashmap[q[0]]*3*3*3 + hashmap[q[2]]*3*3 +hashmap[q[4]]*3 + hashmap[q[6]]
        score = int(q[7])
        #score보다 크거나 같은 원소가 몇개 있는지..!
        answer.append(len(scores[idx]) - bisect_left(scores[idx],score))
    return answer

참고

• 예전, quickSorting에서 피벗을 기준으로 몇번째 큰 수 인지 확인하는 방법이 있었는데 파이썬에서는 bisect라는 라이브러리가 있었다..!
• bisect_left -> 같은 값일 때, 왼쪽으로,,
• bisect_right -> "" , 오른쪽으로,,
• 효율성을 고려하여 매번 해당하는 원소들을 반복순회하여 찾기보단,, 메모리를 조금 더 사용하여 데이터에 접근하는 것이 더 효율적이다
• 약간 hashing처럼 접근하여 사용하므로 탐색시간은 굉장히 빠를 것.
• 포함이 안되는 경우의 hashing값을 0 으로 설정하여 부분집합으로 탐색..!

문제 설명

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면, (각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

[문제]

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

• orders 배열의 크기는 2 이상 20 이하입니다.
• orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
• 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
• course 배열의 크기는 1 이상 10 이하입니다.
• course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
• course 배열에는 같은 값이 중복해서 들어있지 않습니다.
• 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
• 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
• 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
• orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.

[입출력 예]

orders	course	result
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]	[2,3,4]	["AC", "ACDE", "BCFG", "CDE"]
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"]	[2,3,5]	["ACD", "AD", "ADE", "CD", "XYZ"]
["XYZ", "XWY", "WXA"]	[2,3,4]	["WX", "XY"]

concept

• 주어진 문자열?의 원소로 구성할 수 있는 모든 조합을 탐색
• 해당 정보들을 어떤 자료형으로 저장해야할지..
• 길이별로 저장하고, 해당 길이에 해당하는 문자열들을 저장해야됨.
• 모든 조합의 정보가 필요한 것이 아닌 course에서 명시하는 조합의 크기만 필요함.
• 해봤는데,, course에서는 3까지 불렀는데 abcdefg시킨에 있으면 outofrange..
• combination을 활용..(from itertools import combinations)
• 저장되어 있는 자료형은 길이별로 저장될 것이니, 길이별 최대값을 따로 저장하여 탐색 시간을 줄임.

Code

from itertools import combinations
def solution(orders, course):
    answer = []
    #'AD' == 'DA'이므로 정렬하여 사용
    course.sort()
    orders.sort()
    mini, maxi = course[0], course[-1]
    #인덱스를 길이로 활용해야 하므로 +1, 저장 자료는 딕셔너리 형태로 저장.
    data = [{}for _ in range(11)]
    maximum = [0 for _ in range(11)]
    for order in orders:
        #조합의 개수는 2개부터(주어진 조건의 최소값부터..),,해당 문자열의 개수까지..
        #문자열은 정렬 안돼... str.sort() ->X
        for num in range(mini, len(order)+1):
            #조합의 반환은 튜플,,형태의 리스트 이므로,,
            for i in combinations(order, num):
                #('a','b') -> ab
                #문자열 정렬 안되니깐,, 여기서 정렬
                key = ''.join(sorted(i))
                if(key in data[num]):
                    # 데이터 추가 후 max갱신
                    data[num][key] += 1
                    maximum[num] = max(maximum[num],data[num][key])
                else:
                    data[num][key] = 1
    #print(data)
    for num in course:
        for key, val in data[num].items():
            if(val == maximum[num]):
                answer.append(key)
    answer.sort()
    return answer

참고

• 문자열은 정렬 안됨.. -> 조합으로 받은 튜플을 정렬해서 사용
• 리스트.join('')이 아니라 -> ''.join(리스트) ㅋㅋ
• 딕셔너리와 리스트를 활용하여 자료형을 설정.. -> 약간 json형식같기도.

신규아이디 추천

• 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
• 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
• 3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
• 4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
• 5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
• 6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다. 만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
• 7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.

[입출력 예]

no	new_id	result
예1	"...!@BaT#*..y.abcdefghijklm"	"bat.y.abcdefghi"
예2	"z-+.^."	"z--"
예3	"=.="	"aaa"
예4	"123_.def"	"123_.def"
예5	"abcdefghijklmn.p"	"abcdefghijklmn"

입출력 예에 대한 설명

• 입출력 예 #1 문제의 예시와 같습니다.

• 입출력 예 #2 7단계를 거치는 동안 new_id가 변화하는 과정은 아래와 같습니다.
  1단계 변화 없습니다. 2단계 "z-+.^." → "z-.." 3단계 "z-.." → "z-." 4단계 "z-." → "z-" 5단계 변화 없습니다. 6단계 변화 없습니다. 7단계 "z-" → "z--"

• 입출력 예 #3 7단계를 거치는 동안 new_id가 변화하는 과정은 아래와 같습니다.
  1단계 변화 없습니다. 2단계 "=.=" → "." 3단계 변화 없습니다. 4단계 "." → "" (new_id가 빈 문자열이 되었습니다.) 5단계 "" → "a" 6단계 변화 없습니다. 7단계 "a" → "aaa"

• 입출력 예 #4 1단계에서 7단계까지 거치는 동안 new_id("123_.def")는 변하지 않습니다. 즉, new_id가 처음부터 카카오의 아이디 규칙에 맞습니다.

• 입출력 예 #5 1단계 변화 없습니다. 2단계 변화 없습니다. 3단계 변화 없습니다. 4단계 변화 없습니다. 5단계 변화 없습니다. 6단계 "abcdefghijklmn.p" → "abcdefghijklmn." → "abcdefghijklmn" 7단계 변화 없습니다.

concept

• just do it! 하라는대로 코딩한다.

Code

def isValid(ch):
    if(ch.isalnum()):
        return True
    if(ch == '-' or ch == '_' or ch == '.'):
        return True
    return False

def solution(new_id):
    answer = ''
    lastDot = False
    for ch in new_id:
        if(isValid(ch) == False):
            continue

        if ch == '.':
            if(len(answer)==0 or lastDot):
                continue
            lastDot = True
        else:
            lastDot = False

        ch = ch.lower()
        answer += ch
    # 3단계 '..' -> '.' 으로 치환
    # while '..' in answer:
    #    answer = answer.replace('..','.')

    if(len(answer) >= 16):
        answer = answer[:15]
    # 중복 '.'을 해결했으므로 한번만 잘라주면 된다.
    if(answer.endswith('.')):
        answer = answer[:-1]

    if(len(answer)==0):
        answer+='a'

    if(len(answer)<=2):
        ch = answer[-1]
        while len(answer)<3:
            answer += ch

    return answer

참고

• 문자와 숫자를 판별하는 isalpha() 와 isnum()이 존재하지만 둘 다 판별하는 isalnum()이 존재한다.

• 3단계의 중복 '.'과정을 replace구문을 활용하여 제거할 수도 있음.

concept

• 다양한 차의 종류들에 대한 정보들을 제공하고, 키워드 검색을 통하여 차를 추천해주는 사이트
• 유저 정보들을 DB로 관리하여 찜목록에 대한 데이터를 별도로 저장

소통 Tool

• figma: 개인적으로 굉장히 맘에들었던 tool.. 사용하는 유저들끼리 화면을 공유하면 디자인 아이디어를 나눌 수 있어서 너무 좋았다. 공유화면에는 개발에 유리하게 css스타일 및 px크기 등.. 굉장히 여러가지 효능들이 존재하였고, 나중에 이 tool을 이용하여 ppt제작 및 프레임워크 구상하는데 사용함.. (새벽만 되면 낙서판으로 사용했는데 이게 젤 재밌었다) 참조 : https://haningya.tistory.com/259

• Discord : 유튜브에서 게임방송하는 사람들이 게임할때 쓰는 건 줄 알았는데,, 한 그룹안에 다양한 채팅채널을 설정하여 소통을 원할하게 진행할 수 있어서 좋았다. 화면공유도 간편하며 우리는 작업할 당시 항상 마이크로 소통하며 작업을 해서, 늘 함께하는 기분을 느낄 수 있었다.. 짱좋았음

협업 Tool

• github - https://github.com/spartaT4chacha/front-back

디자인 및 이미지 참조

Font

• https://noonnu.cc/ (한글)
• https://fonts.google.com/ (구글)
• https://befonts.com/

design

• https://www.pinterest.co.kr/
• http://awwards.com/
• https://fribly.com/
• https://unsplash.com/

Design

• 어디선가 본듯한 모션 js를 통한 전체 페이지 보여주기
• 메인 화면에 fullPage를 적용하여 이미지 및 다양한 정보를 제공

메인 페이지

메인 페이지2

소개 페이지_모션JS

소개 페이지

리스트 페이지_정렬가능

로그인 페이지

회원가입 페이지_모달기법

내정보 페이지_slick

정보수정 페이지

찜목록 페이지

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

입출력 예

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다. 5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

concept

• 구글링함. 이건 생각을 전혀전혀전혀전혀 하지 못하였다..
• 가장 많이 이긴 놈이 제일 쎈게 아니다..! 이긴수가 같더라도 상대한테 졌을 수도 있기 때문..
• 그래서 구글링함..

Code

def solution(n, results):
    answer = 0
    #정확하게...?
    #가장 많이 이긴 놈이 제일 쎈게 아니다...
    #이긴수가 비슷하더라도.. 상대 녀석에게 졌을 수 있기 때문..!
    #그렇담 제일 많이 진 녀석으로 생각해도..?
    graph = [ [0]*(n+1) for _ in range(n+1)]
    for win, los in results:
        graph[win][los] = -1
        graph[los][win] = 1

    #floyd warshall
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                #자기 자신을 제외하고 승패 여부를 알 수 없는 경우
                if(i!=j and graph[i][j] == 0):
                    if (graph[i][k] == 1 and graph[k][j] == 1):
                        #삼단논법 마냥 가능하다면
                        graph[i][j] = 1
                    elif(graph[i][k] == -1 and graph[k][j] == -1):
                        graph[i][j] = -1
    #승패를 확연하게 알 수 있는 것이 왜 이기고 지기고 모두 명확해야하는지 아직 이해하지 못함
    for i in range(1,n+1):
        if graph[i][1:].count(0) == 1:
            answer+=1
    return answer

참고

• 지나가는 경로를 탐색
• 모든 경로의 최소비용을 구할 수 있음..
• 더 공부할 것..

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

concept

• dp문제같다..! 1번에 연결된 3, 2는 1의 값을 3, 2에 연결된 6, 4, 5는 3, 2의 값 +1을 ... 전에 있던 노드의 정보를 가져온다..

• dfs나 bfs로 탐색해서 진행하면 될 듯..?

code

• bfs (시간초과)

  from collections import deque
  def solution(n, edge):
    answer = 0
    #거리 정보.
    distance = [0 for _ in range(n+1)]
    #그래프 정보.
    graph = [[0]*(n+1) for _ in range(n+1)]
    for s, t in edge:
        #무방향 그래프
        graph[s][t] = graph[t][s] = 1
    #bfs탐색 시작
    queue = deque()
    queue.append(1)
    while(queue):
        now = queue.popleft()
        for i in range(1, n+1):
            if(now == i):
                continue
            if(graph[now][i] != 0 and distance[i]==0):
                queue.append(i)
                distance[i] = distance[now] + 1
    distance[1] = 0
    answer = distance.count(max(distance))
    return answer

• 간선정보이용

  from collections import deque
  def solution(n, edge):
    answer = 0
    #1번 노드에서 도달할 수 있는 거리
    distance = [0 for _ in range(n+1)]
    #queue사용.
    queue = deque()
    #그래프 연결 정보
    graph = [[]for _ in range(n+1)]
    edge.sort()
    for e in edge:
        #연결 되어 있는 정보를 리스트로 가져감
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
    #1번 노드부터 탐색
    queue.append(1)
  
    while queue:
        #큐에 가장 앞에 있는 원소를 가져온다.
        now = queue.popleft()
        #연결되어 있는 다음 노드들을 탐색
        for next in graph[now]:
            #1번 노드는 내가 미리 넣어줬으므로 탐색할 필요가 없다.
            if next == 1:
                continue
            #한번도 방문한 적 없는 노드라면 다시 그 지점부터 탐색해야하므로 삽입
            if(distance[next] == 0):
                queue.append(next)
                #다음 방문 거리는 현재 보다 한칸씩 더 증가해야 하므로..
                distance[next] = distance[now]+1
  
    answer = distance.count(max(distance))
  
    return answer

참고

• 시간초과가 난 이유 = 연결된 노드들을 for문을 이용해 모두 확인하기 때문
• 연결된 간선들을 확인하는 것으로 탐색 시간을 낮출 수 있다.
• 효율적인 측면에서 그래프(배열)를 이용하는 것보다 간선의 정보로 탐색하는것이 효율적으로 보임

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

tickets	return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

concept

• 처음에는 각 공항을 노드로 설정하고 그래프 연결처럼 풀려고 했다.. 이 방법을 사용하지 않은 이유 : 중복으로 거처갈 수 있다..

• 이후, 생각해보니 노드 도착 정보에 몇번 왔던 곳인지 cnt를 해서 탐색해도 가능할 것 같은데,, 나중에 작성해보겠음..(언제가 될 지는 모르겠다..)

• 각 공항에 연결된 간선의 정보들을 저장하여 dfs(로 보는게 맞을듯..)탐색을 시행한다.

code

def solution(tickets):
    answer = []
    graph = {}

    #간선 정보 저장
    for start, end in tickets:
        if(start not in graph):
            graph[start] = [end]
        else:
            graph[start].append(end)

    #pop()으로 간선을 빼면서 진행할 것이기에 정렬은 내림차순으로..
    for val in graph.values():
        val.sort(reverse = True)

    #초기 탐색값 설정
    st = ['ICN']

    while(st):
        #현재 도착 공항_가장 위에 있는 원소(bfs가 아니고 st에 쌓으며 진행할 것이므로 popx)
        now = st[-1]
        #graph에 정보가 있고, 연결된 간선이 존재한다면
        if (now in graph and len(graph[now]) != 0):
            st.append(graph[now].pop())
        #모든 간선들이 사라지면 탐색이 끝난것인데,, 그것을 굳이 확인하지 말고 answer에 집어넣자
        else:
            answer.append(st.pop())
    answer.reverse()
    return answer

참고

• 노드가 중복으로 표현된다면 그래프에 cnt값을 설정하여 풀 수도 있을 듯.
• 간선의 정보를 저장해서 탐색하는 방법도 좋음
• 스택으로 이동경로를 저장하는 것.

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

입출력 예 설명

예제 #1 아래와 같이 2개의 네트워크가 있습니다.

예제 #2 아래와 같이 1개의 네트워크가 있습니다.

concept

• 그래프가 몇개 연결되어 있는지 확인하면 됨.
• dfs나 bfs로 탐색하면서 visit배열을 만들어 탐색 진행

code

• DFS

  def DFS(start, n, map, visit):
    #노드 방문
    visit[start] = True
    for i in range(n):
        #연결되어 있는 맵중 방문 아직 안 했고, 갈 수 있는 길이라면 탐색 시작
        if(visit[i] == False and map[start][i]):
            DFS(i, n, map, visit)
  

def solution(n, computers): answer = 0 #얕은 복사 map = computers visit = [False for _ in range(n)] for i in range(n): if(visit[i] == False): DFS(i, n, map, visit) answer+=1 return answer

- BFS
```py
from collections import deque

def BFS(start, n, map, visit):
    queue = deque()
    queue.append(start)

    while(queue):
        curr = queue.popleft()
        visit[curr] = True
        for i in range(n):
            if(visit[i] == False and map[curr][i]):
                queue.append(i)

def solution(n, computers):
    answer = 0
    #얕은 복사
    map = computers
    visit = [False for _ in range(n)]
    for i in range(n):
        if(visit[i] == False):
            BFS(i, n, map, visit)
            answer+=1
    return answer

참고

• 연결되어 있는 노드들의 정보는 확실히 배열로 표현하는게 편하다

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

  입출력 예 #2

• 4+1-2+1 = 4
• 4-1+2-1 = 4 총 2가지 방법이 있으므로, 2를 return 합니다.

concept

• 주어진 숫자 배열을 모두 활용해야한다.
• target이 되면 answer값을 증가한다..
• 모든 방법 +, - 를 시행하며 가지치듯이 나아가고, 정해진 횟수가 되면 종료해야하므로 완전탐색(bfs, dfs로 구현한다.

Code

• DFS

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    def dfs(id, result):
        if id == n:
            if(result == target):
                nonlocal answer
                answer+=1
            return
        else:
            dfs(id+1,result+numbers[id])
            dfs(id+1,result-numbers[id])
    dfs(0,0)
    return answer

• BFS

from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    #시행 횟수
    length = len(numbers)
    queue.append((numbers[0], 1))
    queue.append((-numbers[0],1))

    while queue:
        num, cnt = queue.popleft()
        if(cnt == length):
            if(num == target):
                answer+=1
        else:
            queue.append((num+numbers[cnt], cnt+1))
            queue.append((num-numbers[cnt], cnt+1))

    return answer

참고

• import 귀찮아서 pop(0)으로 하면 시간초과 뜸..
• bfs는 확실히 들어온 순서대로 나가서 다시 확인해야 하기 때문에, deque를 쓰는것이 효율적임
• dfs는 스택을 쓰거나, 재귀적으로 구현이 가능하다

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
• m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

m| n |puddles |return --|--|--| 4 |3 |[[2, 2]]| 4

입출력 예 설명

concept

• 옛날 고등학교때 배우던 숫자세기..
• 원래 이 최소 경로 문제는 같은 것을 포함한 순열 문제이다.. -> 장애물 나오면 case분류해서 풀어야함.

code

def solution(m, n, puddles):
    answer = 0
    #bumper 설정
    map = [[0]*(m+1) for _ in range(n+1)]
    #시작점
    map[1][1] = 1

    for i in range(1,n+1):
        for j in range(1,m+1):
            if([j,i] in puddles):
                continue
            if(i==1 and j== 1):
                continue
            map[i][j] = map[i-1][j] + map[i][j-1]
    print(map)
    return map[-1][-1]%1000000007

참고

• 인덱스 error를 방지하기 위해 0인 배열을 범퍼로 설정하느라 배열을 하나 더 썻음..
• 조건문을 추가하면 배열의 크기를 넓힐 필요는 없음.
• 배열을 탐색하면서 이전 값을 더한다는 개념이 dp로 적용된 것.

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

concept

• 마지막에 어떤 큰 값(변수)가 있을지 모르므로 마지막까지 모두 탐색을 해봐야한다.

• 진행하면서 항상 최적의 값을 찾을 수가 없다는 이야기..

• dfs로 탐색하여 최솟값을 구할 수도 있음

• bfs로 탐색하기에는,, 위와 같은 케이스때문에 효율적으로 보이진 않음..

• 진행하면서 누적값을 저장하여 가장 마지막까지 진행한 후 마지막에서 최솟값을 뽑아내는것이 효율적

• 누적값을 저장하면서 진행하기에 dp의 대표적 예제..

code

def solution(triangle):
    answer = 0
    parent = triangle[0]
    for row in triangle:
        #꼭대기 스킵
        length = len(row)
        if(length==1):
            continue
        for i in range(length):
            if(not i):
                row[i] += parent[i]
            elif(i == length-1):
                row[i] += parent[i-1]
            else:
                row[i] += max(parent[i], parent[i-1])
        parent = row

    return max(triangle[-1])

참고

• 인덱스로 접근하여 0번째 인덱스를 Skip할 수도 있음..

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

입출력 예 설명

예제 #1 문제에 나온 예와 같습니다.

예제 #2 11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

concept

동적 계획법 -> 전에 사용했던 데이터를 저장하여 이후에 재사용하는 알고리즘.

이 문제에서는 case1 주어진 숫자를 한 개 사용하여 만들 수 있는 경우 [5] case2 주어진 숫자를 두 개 사용하여 만들 수 있는 경우 [55, 5/5, 55, 5+5, 5-5] case3 주어진 숫자를 세 개 사용하여 만들 수 있는 경우 [555, 55/5, 555, 55+5, 55-5, 5/55, 555, 5+55, 5-55, 5+5+5, 5-5-5, 55*5, 5/5/5 .. ] 등등..

case1 = case1 case2 = case1 & case1 case3 = case1 & case2 | case2 & case1 로 생각할 수 있다..

주의점 : case3 = case1 & case1 & case1 아닌가라는 생각은 case1 & case2(case1+case1)으로 이미 포함되어 있다

...

한 단계씩 증가할 때마다 이전 단계의 결과값을 재사용하는 것을 확인할 수 있다.. like 점화식

code

def solution(N, number):
    answer = -1
    dp = []
    #1~8개의 케이스
    for i in range(1,9):
        #중복인 경우 제외 처리
        all_case = set()
        duple_number = int(str(N)*i)
        all_case.add(duple_number)
        #dp에 저장되어 있는 값들을 활용
        #i = 2 -> 1+1
        #ex) i=4 -> 1+3(0,2), 2+2(1,1), 1+1+2(0,0,1)
        #i = 5 -> 1+4(0,3), 2+3(1,2)
        #i = 6 -> 1+5(0,4), 2+4(1,3), 3+3(2,2)
        for j in range(i-1):
            for num1 in dp[j]:
                for num2 in dp[i-j-2]:
                    all_case.add(num1 + num2)
                    all_case.add(num1 - num2)
                    all_case.add(num1 * num2)
                    if(num2 != 0):
                        all_case.add(num1 // num2)
        if(number in all_case):
            return i

        dp.append(all_case)

    return answer

참고

• 전에 사용된 결과를 담을 dp배열이 필요
• 중복을 제거하기 위하여 set()처리
• '*', '+'연산은 상관없지만, '/' '-'연산은 순서에 따라 결과 값이 바뀌기 때문에 대칭적으로 모두 돌아야한다.
• 코딩을 시작하기전에 사용된 값이 재사용된다면 점화식을 먼저 세워보는것도 좋을듯..!